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>>
,java.util.function.Function<Graph<V,E>,VertexPartition<V,E>>
public class StructurallyEquivalent<V,E> extends java.lang.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 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 VertexPartition<V,E>
apply(Graph<V,E> g)
protected boolean
canBeEquivalent(V v1, V v2)
This is a space for optimizations.protected java.util.Set<Pair<V>>
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)
-
-
-
Method Detail
-
getEquivalentPairs
protected java.util.Set<Pair<V>> 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. (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
protected boolean isStructurallyEquivalent(Graph<V,?> g, V v1, V v2)
- 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
protected boolean canBeEquivalent(V v1, V v2)
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
-
-