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