Class StructurallyEquivalent<V,E>
- java.lang.Object
-
- edu.uci.ics.jung.algorithms.blockmodel.StructurallyEquivalent<V,E>
-
- All Implemented Interfaces:
org.apache.commons.collections4.Transformer<edu.uci.ics.jung.graph.Graph<V,E>,VertexPartition<V,E>>
public class StructurallyEquivalent<V,E> extends java.lang.Object implements org.apache.commons.collections4.Transformer<edu.uci.ics.jung.graph.Graph<V,E>,VertexPartition<V,E>>
Identifies sets of structurally equivalent vertices in a graph. Vertices i and j are structurally equivalent iff the set of i's neighbors is identical to the set of j's neighbors, with the exception of i and j themselves. This algorithm finds all sets of equivalent vertices in O(V^2) time.You can extend this class to have a different definition of equivalence (by overriding
isStructurallyEquivalent
), and may give it hints for accelerating the process by overridingcanPossiblyCompare
. (For example, in a bipartite graph,canPossiblyCompare
may returnfalse
for vertices in different partitions. This function should be fast.)
-
-
Constructor Summary
Constructors Constructor Description StructurallyEquivalent()
-
Method Summary
All Methods Instance Methods Concrete Methods Modifier and Type Method Description protected boolean
canPossiblyCompare(V v1, V v2)
This is a space for optimizations.protected java.util.Set<edu.uci.ics.jung.graph.util.Pair<V>>
getEquivalentPairs(edu.uci.ics.jung.graph.Graph<V,?> g)
For each vertex pair v, v1 in G, checks whether v and v1 are fully equivalent: meaning that they connect to the exact same vertices.protected boolean
isStructurallyEquivalent(edu.uci.ics.jung.graph.Graph<V,?> g, V v1, V v2)
Checks whether a pair of vertices are structurally equivalent.VertexPartition<V,E>
transform(edu.uci.ics.jung.graph.Graph<V,E> g)
-
-
-
Method Detail
-
transform
public VertexPartition<V,E> transform(edu.uci.ics.jung.graph.Graph<V,E> g)
-
getEquivalentPairs
protected java.util.Set<edu.uci.ics.jung.graph.util.Pair<V>> getEquivalentPairs(edu.uci.ics.jung.graph.Graph<V,?> g)
For each vertex pair v, v1 in G, checks whether v and v1 are fully equivalent: meaning that they connect to the exact same vertices. (Is this regular equivalence, or whathaveyou?) Returns a Set of Pairs of vertices, where all the vertices in the inner Pairs are equivalent.- Parameters:
g
-
-
isStructurallyEquivalent
protected boolean isStructurallyEquivalent(edu.uci.ics.jung.graph.Graph<V,?> g, V v1, V v2)
Checks whether a pair of vertices are structurally equivalent. Specifically, whether v1's predecessors are equal to v2's predecessors, and same for successors.- Parameters:
g
- the graph in which the structural equivalence comparison is to take placev1
- the vertex to check for structural equivalence to v2v2
- the vertex to check for structural equivalence to v1
-
-