edu.uci.ics.jung.algorithms.blockmodel
Class StructurallyEquivalentII

java.lang.Object
  edu.uci.ics.jung.algorithms.blockmodel.StructurallyEquivalent
      edu.uci.ics.jung.algorithms.blockmodel.StructurallyEquivalentII

All Implemented Interfaces:

EquivalenceAlgorithm

public class StructurallyEquivalentII

extends StructurallyEquivalent

Checks a graph for sets of structurally equivalent vertices: vertices that share all the same edges. Specifically, In order for a pair of vertices i and j to be structurally equivalent, the set of i 's neighbors must be 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 bipartitegraph, canPossiblyCompare may return false for vertices in different partitions. This function should be fast.)

Author:

danyelf

Field Summary

Fields inherited from class edu.uci.ics.jung.algorithms.blockmodel.StructurallyEquivalent

count

Constructor Summary

StructurallyEquivalentII()

Method Summary

java.util.Set	checkEquivalent(Graph 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.
static StructurallyEquivalent	getInstance()

Methods inherited from class edu.uci.ics.jung.algorithms.blockmodel.StructurallyEquivalent

getEquivalences

Methods inherited from class java.lang.Object

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

Constructor Detail

StructurallyEquivalentII

public StructurallyEquivalentII()

Method Detail

getInstance

public static StructurallyEquivalent getInstance()

checkEquivalent

public java.util.Set checkEquivalent(Graph 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.

Overrides:

checkEquivalent in class StructurallyEquivalent

Parameters:

g -