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

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

All Implemented Interfaces:

EquivalenceAlgorithm

Direct Known Subclasses:

StructurallyEquivalentII

public class StructurallyEquivalent

extends java.lang.Object

implements EquivalenceAlgorithm

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

static int

count

Constructor Summary

StructurallyEquivalent()

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.
EquivalenceRelation	getEquivalences(Graph g) Runs the equivalence algorithm on the given graph, and returns an equivalence relation.
static StructurallyEquivalent	getInstance()

Methods inherited from class java.lang.Object

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

Field Detail

count

public static int count

Constructor Detail

StructurallyEquivalent

public StructurallyEquivalent()

Method Detail

getInstance

public static StructurallyEquivalent getInstance()

getEquivalences

public EquivalenceRelation getEquivalences(Graph g)

Description copied from interface: EquivalenceAlgorithm

Runs the equivalence algorithm on the given graph, and returns an equivalence relation.

Specified by:

getEquivalences in interface EquivalenceAlgorithm

Parameters:

g - the graph to be checked for equivalence

Returns:

an EquivalenceRelation

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.

Parameters:

g -