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. |
copyright © 2003, jcoverage ltd. all rights reserved. |