# Coverage details for edu.uci.ics.jung.algorithms.blockmodel.StructurallyEquivalent

Line | Hits | Source
--- | --- | ---
1 |  | `/*`
2 |  | `* Copyright (c) 2003, the JUNG Project and the Regents of the University`
3 |  | `* of California`
4 |  | `* All rights reserved.`
5 |  | `*`
6 |  | `* This software is open-source under the BSD license; see either`
7 |  | `* "license.txt" or`
8 |  | `* http://jung.sourceforge.net/license.txt for a description.`
9 |  | `*/`
10 |  | `/*`
11 |  | `* Created on Jan 28, 2004`
12 |  | `*/`
13 |  | `package edu.uci.ics.jung.algorithms.blockmodel;`
14 |  | ``
15 |  | `import java.util.ArrayList;`
16 |  | `import java.util.HashMap;`
17 |  | `import java.util.HashSet;`
18 |  | `import java.util.Iterator;`
19 |  | `import java.util.List;`
20 |  | `import java.util.Map;`
21 |  | `import java.util.Set;`
22 |  | ``
23 |  | `import edu.uci.ics.jung.graph.Graph;`
24 |  | `import edu.uci.ics.jung.graph.Vertex;`
25 |  | `import edu.uci.ics.jung.utils.Pair;`
26 |  | ``
27 |  | `/**`
28 |  | `* Checks a graph for sets of structurally equivalent vertices: vertices that`
29 |  | `* share all the same edges. Specifically, In order for a pair of vertices <i>`
30 |  | `* i</i> and <i>j</i> to be structurally equivalent, the set of <i>i</i>'s`
31 |  | `* neighbors must be identical to the set of <i>j</i>'s neighbors, with the`
32 |  | `* exception of <i>i</i> and <i>j</i> themselves. This algorithm finds all`
33 |  | `* sets of equivalent vertices in O(V^2) time.`
34 |  | `*`
35 |  | `* You can extend this class to have a different definition of equivalence (by`
36 |  | `* overriding "isStructurallyEquivalent"), and may give it hints for`
37 |  | `* accelerating the process by overriding canpossiblycompare. (For example, in`
38 |  | `* a bipartitegraph, canPossiblyCompare may return false for vertices in`
39 |  | `* different partitions. This function should be fast.)`
40 |  | `*`
41 |  | `* @author danyelf`
42 |  | `*/`
43 |  | `public class StructurallyEquivalent implements EquivalenceAlgorithm {`
44 |  | ``
45 | 2 | `static StructurallyEquivalent instance = null;`
46 |  | ``
47 |  | `public static StructurallyEquivalent getInstance() {`
48 | 3 | `if ( instance == null ) {`
49 | 1 | `instance = new StructurallyEquivalent();`
50 |  | `}`
51 | 3 | `return instance;`
52 |  | `}`
53 |  | ``
54 | 2 | `public StructurallyEquivalent() {`
55 |  | ``
56 | 2 | `}`
57 |  | ``
58 |  | `public EquivalenceRelation getEquivalences(Graph g) {`
59 | 8 | `return createEquivalenceClasses(g, checkEquivalent(g));`
60 |  | `}`
61 |  | ``
62 |  | `/**`
63 |  | `* Takes in a Set of Pairs (as in the resutls of checkEquivalent) and`
64 |  | `* massages into a Set of Sets, where each Set is an equivalence class.`
65 |  | `*/`
66 |  | `protected EquivalenceRelation createEquivalenceClasses(Graph g, Set s) {`
67 | 8 | `Set rv = new HashSet();`
68 | 8 | `Map intermediate = new HashMap();`
69 | 8 | `for (Iterator iter = s.iterator(); iter.hasNext();) {`
70 | 20 | `Pair p = (Pair) iter.next();`
71 | 20 | `Set res = (Set) intermediate.get(p.getFirst());`
72 | 20 | `if (res == null)`
73 | 12 | `res = (Set) intermediate.get(p.getSecond());`
74 | 20 | `if (res == null) {`
75 |  | `// we haven't seen this one before`
76 | 12 | `res = new HashSet();`
77 |  | `}`
78 | 20 | `res.add(p.getFirst());`
79 | 20 | `res.add(p.getSecond());`
80 | 20 | `intermediate.put(p.getFirst(), res);`
81 | 20 | `intermediate.put(p.getSecond(), res);`
82 |  | ``
83 |  | `}`
84 | 8 | `rv.addAll(intermediate.values());`
85 | 8 | `return new EquivalenceRelation(rv, g);`
86 |  | `}`
87 |  | ``
88 |  | `/**`
89 |  | `* For each vertex pair v, v1 in G, checks whether v and v1 are fully`
90 |  | `* equivalent: meaning that they connect to the exact same vertices. (Is`
91 |  | `* this regular equivalence, or whathaveyou?)`
92 |  | `*`
93 |  | `* Returns a Set of Pairs of vertices, where all the vertices in the inner`
94 |  | `* Pairs are equivalent.`
95 |  | `*`
96 |  | `* @param g`
97 |  | `*/`
98 |  | `public Set checkEquivalent(Graph g) {`
99 |  | ``
100 | 3 | `Set rv = new HashSet();`
101 | 3 | `Set alreadyEquivalent = new HashSet();`
102 |  | ``
103 | 3 | `List l = new ArrayList(g.getVertices());`
104 |  | ``
105 | 3 | `for (Iterator iter = l.iterator(); iter.hasNext();) {`
106 | 20 | `Vertex v1 = (Vertex) iter.next();`
107 |  | ``
108 | 20 | `if (alreadyEquivalent.contains(v1))`
109 | 10 | `continue;`
110 |  | ``
111 | 10 | `for (Iterator iterator = l.listIterator(l.indexOf(v1) + 1); iterator.hasNext();) {`
112 | 40 | `Vertex v2 = (Vertex) iterator.next();`
113 |  | ``
114 | 40 | `if (alreadyEquivalent.contains(v2))`
115 | 16 | `continue;`
116 |  | ``
117 | 24 | `if (!canpossiblycompare(v1, v2))`
118 | 0 | `continue;`
119 |  | ``
120 | 24 | `if (isStructurallyEquivalent(v1, v2)) {`
121 | 10 | `Pair p = new Pair(v1, v2);`
122 | 10 | `alreadyEquivalent.add(v2);`
123 | 10 | `rv.add(p);`
124 |  | `}`
125 |  | ``
126 |  | `}`
127 |  | `}`
128 |  | ``
129 | 3 | `return rv;`
130 |  | ``
131 |  | `}`
132 |  | ``
133 |  | `/**`
134 |  | `* Checks whether a pair of vertices are structurally equivalent.`
135 |  | `* Specifically, whether v1's predecessors are equal to v2's predecessors,`
136 |  | `* and same for successors.`
137 |  | `*`
138 |  | `* @param v1`
139 |  | `* @param v2`
140 |  | `*/`
141 |  | `protected boolean isStructurallyEquivalent(Vertex v1, Vertex v2) {`
142 |  | ``
143 | 62 | `count ++;`
144 |  | ``
145 | 62 | `if( v1.degree() != v2.degree()) {`
146 | 37 | `return false;`
147 |  | `}`
148 |  | ``
149 | 25 | `Set n1 = new HashSet(v1.getPredecessors());`
150 | 25 | `n1.remove(v2);`
151 | 25 | `n1.remove(v1);`
152 | 25 | `Set n2 = new HashSet(v2.getPredecessors());`
153 | 25 | `n2.remove(v1);`
154 | 25 | `n2.remove(v2);`
155 |  | ``
156 | 25 | `Set o1 = new HashSet(v1.getSuccessors());`
157 | 25 | `Set o2 = new HashSet(v2.getSuccessors());`
158 | 25 | `o1.remove(v1);`
159 | 25 | `o1.remove(v2);`
160 | 25 | `o2.remove(v1);`
161 | 25 | `o2.remove(v2);`
162 |  | ``
163 |  | `// this neglects self-loops and directed edges from 1 to other`
164 | 25 | `boolean b = (n1.equals(n2) && o1.equals(o2));`
165 | 25 | `if (!b)`
166 | 3 | `return b;`
167 |  | ``
168 |  | `// if there's a directed edge v1->v2 then there's a directed edge v2->v1`
169 | 22 | `b &= ( v1.isSuccessorOf(v2) == v1.isSuccessorOf(v2));`
170 |  | ``
171 |  | `// self-loop check`
172 | 22 | `b &= ( v1.isSuccessorOf(v1) == v2.isSuccessorOf(v2));`
173 |  | ``
174 | 22 | `return b;`
175 |  | ``
176 |  | `}`
177 |  | ``
178 | 2 | `public static int count = 0;`
179 |  | ``
180 |  | `/**`
181 |  | `* This is a space for optimizations. For example, for a bipartitegraph,`
182 |  | `* vertices from class_A and class_B cannot possibly be compared.`
183 |  | `*`
184 |  | `* @param v1`
185 |  | `* @param v2`
186 |  | `*/`
187 |  | `protected boolean canpossiblycompare(Vertex v1, Vertex v2) {`
188 | 62 | `return true;`
189 |  | `}`
190 |  | ``
191 |  | `}`

this report was generated by version 1.0.5 of jcoverage. visit www.jcoverage.com for updates. | copyright © 2003, jcoverage ltd. all rights reserved. Java is a trademark of Sun Microsystems, Inc. in the United States and other countries.