|
||||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | |||||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |
java.lang.Objectedu.uci.ics.jung.algorithms.blockmodel.StructurallyEquivalent
public class 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.)
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 |
---|
public static int count
Constructor Detail |
---|
public StructurallyEquivalent()
Method Detail |
---|
public static StructurallyEquivalent getInstance()
public EquivalenceRelation getEquivalences(Graph g)
EquivalenceAlgorithm
getEquivalences
in interface EquivalenceAlgorithm
g
- the graph to be checked for equivalence
protected EquivalenceRelation createEquivalenceClasses(Graph g, Set s)
public Set checkEquivalent(Graph g)
g
- protected boolean isStructurallyEquivalent(Vertex v1, Vertex v2)
v1
- v2
- protected boolean canpossiblycompare(Vertex v1, Vertex v2)
v1
- v2
-
|
||||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | |||||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |