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

java.lang.Object
  extended by edu.uci.ics.jung.algorithms.blockmodel.StructurallyEquivalent
All Implemented Interfaces:
EquivalenceAlgorithm
Direct Known Subclasses:
StructurallyEquivalentII

public class StructurallyEquivalent
extends 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
protected  boolean canpossiblycompare(Vertex v1, Vertex v2)
          This is a space for optimizations.
 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.
protected  EquivalenceRelation createEquivalenceClasses(Graph g, Set s)
          Takes in a Set of Pairs (as in the resutls of checkEquivalent) and massages into a Set of Sets, where each Set is an equivalence class.
 EquivalenceRelation getEquivalences(Graph g)
          Runs the equivalence algorithm on the given graph, and returns an equivalence relation.
static StructurallyEquivalent getInstance()
           
protected  boolean isStructurallyEquivalent(Vertex v1, Vertex v2)
          Checks whether a pair of vertices are structurally equivalent.
 
Methods inherited from class java.lang.Object
clone, equals, finalize, 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

createEquivalenceClasses

protected EquivalenceRelation createEquivalenceClasses(Graph g,
                                                       Set s)
Takes in a Set of Pairs (as in the resutls of checkEquivalent) and massages into a Set of Sets, where each Set is an equivalence class.


checkEquivalent

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

isStructurallyEquivalent

protected boolean isStructurallyEquivalent(Vertex v1,
                                           Vertex 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:
v1 -
v2 -

canpossiblycompare

protected boolean canpossiblycompare(Vertex v1,
                                     Vertex v2)
This is a space for optimizations. For example, for a bipartitegraph, vertices from class_A and class_B cannot possibly be compared.

Parameters:
v1 -
v2 -