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

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 |  | `import java.util.*;`
15 |  | ``
16 |  | `import edu.uci.ics.jung.graph.Graph;`
17 |  | `import edu.uci.ics.jung.graph.Vertex;`
18 |  | `import edu.uci.ics.jung.utils.Pair;`
19 |  | `/**`
20 |  | `* Checks a graph for sets of structurally equivalent vertices: vertices that`
21 |  | `* share all the same edges. Specifically, In order for a pair of vertices <i>`
22 |  | `* i </i> and <i>j </i> to be structurally equivalent, the set of <i>i </i>'s`
23 |  | `* neighbors must be identical to the set of <i>j </i>'s neighbors, with the`
24 |  | `* exception of <i>i </i> and <i>j </i> themselves. This algorithm finds all`
25 |  | `* sets of equivalent vertices in O(V^2) time.`
26 |  | `*`
27 |  | `* You can extend this class to have a different definition of equivalence (by`
28 |  | `* overriding "isStructurallyEquivalent"), and may give it hints for`
29 |  | `* accelerating the process by overriding canpossiblycompare. (For example, in`
30 |  | `* a bipartitegraph, canPossiblyCompare may return false for vertices in`
31 |  | `* different partitions. This function should be fast.)`
32 |  | `*`
33 |  | `* @author danyelf`
34 |  | `*/`
35 |  | `public class StructurallyEquivalentII extends StructurallyEquivalent {`
36 |  | ``
37 |  | `public static StructurallyEquivalent getInstance() {`
38 | 4 | `if (instance == null) {`
39 | 1 | `instance = new StructurallyEquivalentII();`
40 |  | `}`
41 | 4 | `return instance;`
42 |  | `}`
43 |  | ``
44 | 1 | `public StructurallyEquivalentII() {`
45 | 1 | `}`
46 |  | ``
47 |  | `/**`
48 |  | `* For each vertex pair v, v1 in G, checks whether v and v1 are fully`
49 |  | `* equivalent: meaning that they connect to the exact same vertices. (Is`
50 |  | `* this regular equivalence, or whathaveyou?)`
51 |  | `*`
52 |  | `* Returns a Set of Pairs of vertices, where all the vertices in the inner`
53 |  | `* Pairs are equivalent.`
54 |  | `*`
55 |  | `* @param g`
56 |  | `*/`
57 |  | `public Set checkEquivalent(Graph g) {`
58 | 6 | `Set rv = new HashSet();`
59 |  | `/*`
60 |  | `* this is kind of subtle. if a vertex is equivalent to any other`
61 |  | `* vertex, then all the equivalences will be found on the first pass.`
62 |  | `* That is : if A is equivalent to B, then there are no neighbors of B`
63 |  | `* that are equivalent to it that are not also neighbors of A.`
64 |  | `*/`
65 | 6 | `Set alreadyEquivalent = new HashSet();`
66 |  | `/*`
67 |  | `* Tracks all vertices that we've used as an origin point.`
68 |  | `*/`
69 | 6 | `Set alreadyChecked = new HashSet();`
70 | 6 | `List l = new ArrayList(g.getVertices());`
71 | 6 | `for (Iterator iter = l.iterator(); iter.hasNext();) {`
72 | 28 | `Vertex v1 = (Vertex) iter.next();`
73 | 28 | `alreadyChecked.add(v1);`
74 | 28 | `if (alreadyEquivalent.contains(v1))`
75 | 12 | `continue;`
76 | 16 | `boolean haveHitOne = false;`
77 | 16 | `Set neighbors = new HashSet( v1.getNeighbors() );`
78 | 16 | `neighbors.removeAll( alreadyChecked );`
79 |  | `// check if we're equivalent to any neighbor`
80 | 16 | `for (Iterator iterator = neighbors.iterator(); iterator.hasNext();) {`
81 | 18 | `Vertex v2 = (Vertex) iterator.next();`
82 | 18 | `haveHitOne |= checkEquivalence(v1, v2, alreadyEquivalent, rv );`
83 |  | `}`
84 |  | ``
85 |  | `// if we aren't, then we might be equivalent to one or another 2nd`
86 |  | `// remove neighbor`
87 |  | `// NOTE: v1 can only be equiv to a second-neighbor if it is not`
88 |  | `// equivalnt to a first neighbor`
89 | 16 | `if (!haveHitOne) {`
90 | 16 | `Set secondNeighbors = getSecondNeighbors(v1);`
91 | 16 | `secondNeighbors.removeAll(alreadyChecked);`
92 | 16 | `for (Iterator iterator = secondNeighbors.iterator(); iterator`
93 | 41 | `.hasNext();) {`
94 | 25 | `Vertex v2 = (Vertex) iterator.next();`
95 | 25 | `checkEquivalence(v1, v2, alreadyEquivalent, rv );`
96 |  | `}`
97 |  | ``
98 |  | `}`
99 |  | `}`
100 | 6 | `return rv;`
101 |  | `}`
102 |  | ``
103 |  | ``
104 |  | `boolean checkEquivalence( Vertex v1, Vertex v2, Set alreadyEquivalent, Set rv ) {`
105 | 43 | `if (alreadyEquivalent.contains(v2))`
106 | 5 | `return false;`
107 | 38 | `if (!canpossiblycompare(v1, v2))`
108 | 0 | `return false;`
109 | 38 | `if (isStructurallyEquivalent(v1, v2)) {`
110 | 12 | `Pair p = new Pair(v1, v2);`
111 | 12 | `alreadyEquivalent.add(v2);`
112 | 12 | `rv.add(p);`
113 | 12 | `return true;`
114 |  | `}`
115 | 26 | `return false;`
116 |  | `}`
117 |  | ``
118 |  | `private Set getSecondNeighbors(Vertex v1) {`
119 | 16 | `Set secondNeighbors = new HashSet();`
120 | 16 | `for (Iterator iterator = v1.getNeighbors().iterator(); iterator`
121 | 55 | `.hasNext();) {`
122 | 39 | `Vertex intermediate = (Vertex) iterator.next();`
123 | 39 | `secondNeighbors.addAll(intermediate.getNeighbors());`
124 |  | `}`
125 | 16 | `return secondNeighbors;`
126 |  | `}`
127 |  | ``
128 |  | `}`

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.