Class StructurallyEquivalent<V,E>
java.lang.Object
edu.uci.ics.jung.algorithms.blockmodel.StructurallyEquivalent<V,E>
- All Implemented Interfaces:
com.google.common.base.Function<Graph<V,
,E>, VertexPartition<V, E>> Function<Graph<V,
E>, VertexPartition<V, E>>
public class StructurallyEquivalent<V,E>
extends Object
implements com.google.common.base.Function<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 overriding canPossiblyCompare
.
(For example, in a bipartite graph, canPossiblyCompare
may
return false
for vertices in
different partitions. This function should be fast.)
-
Constructor Summary
Constructors -
Method Summary
Modifier and TypeMethodDescriptionprotected boolean
canBeEquivalent
(V v1, V v2) This is a space for optimizations.getEquivalentPairs
(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
(Graph<V, ?> g, V v1, V v2) Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
Methods inherited from interface com.google.common.base.Function
equals
-
Constructor Details
-
StructurallyEquivalent
public StructurallyEquivalent()
-
-
Method Details
-
apply
-
getEquivalentPairs
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?)- Parameters:
g
- the graph whose equivalent pairs are to be generated- Returns:
- a Set of Pairs of vertices, where all the vertices in the inner Pairs are equivalent.
-
isStructurallyEquivalent
- 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- Returns:
true
ifv1
's predecessors/successors are equal tov2
's predecessors/successors
-
canBeEquivalent
This is a space for optimizations. For example, for a bipartite graph, vertices from different partitions cannot possibly be equivalent.- Parameters:
v1
- the first vertex to comparev2
- the second vertex to compare- Returns:
true
if the vertices can be equivalent
-