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