edu.uci.ics.jung.algorithms.blockmodel

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>>

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 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

Constructor and Description
StructurallyEquivalent()

Method Summary

Modifier and Type	Method and Description
VertexPartition<V,E>	apply(Graph<V,E> g)

Methods inherited from class java.lang.Object

equals, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Methods inherited from interface com.google.common.base.Function

equals

Constructor Detail

StructurallyEquivalent

public StructurallyEquivalent()

Method Detail

apply

public VertexPartition<V,E> apply(Graph<V,E> g)

Specified by:

apply in interface com.google.common.base.Function<Graph<V,E>,VertexPartition<V,E>>