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:

org.apache.commons.collections15.Transformer<Graph<V,E>,VertexPartition<V,E>>

public class StructurallyEquivalent<V,E>
extends Object
implements org.apache.commons.collections15.Transformer<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.)

Author:

Danyel Fisher

Constructor Summary

StructurallyEquivalent()

Method Summary

protected boolean	canPossiblyCompare(V v1, V v2) This is a space for optimizations.
protected 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) Checks whether a pair of vertices are structurally equivalent.
VertexPartition<V,E>	transform(Graph<V,E> g)

Methods inherited from class java.lang.Object

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

Constructor Detail

StructurallyEquivalent

public StructurallyEquivalent()

Method Detail

transform

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

Specified by:

transform in interface org.apache.commons.collections15.Transformer<Graph<V,E>,VertexPartition<V,E>>

getEquivalentPairs

protected 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?) Returns a Set of Pairs of vertices, where all the vertices in the inner Pairs are equivalent.

Parameters:

g -

isStructurallyEquivalent

protected boolean isStructurallyEquivalent(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 place

v1 - the vertex to check for structural equivalence to v2

v2 - the vertex to check for structural equivalence to v1

canPossiblyCompare

protected boolean canPossiblyCompare(V v1,
                                     V v2)

This is a space for optimizations. For example, for a bipartite graph, vertices from different partitions cannot possibly be compared.

Parameters:

v1 -

v2 -