|
||||||||||
| 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<V,E>
public class StructurallyEquivalent<V,E>
Identifies sets of structurally equivalent vertices in a graph. Vertices i and j are structurally equivalent iff the set of i's neighbors is 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 bipartite graph, canPossiblyCompare may
return false for vertices in
different partitions. This function should be fast.)
| Constructor Summary | |
|---|---|
StructurallyEquivalent()
|
|
| Method Summary | |
|---|---|
protected boolean |
canPossiblyCompare(V v1,
V v2)
This is a space for optimizations. |
protected Set<Pair<V>> |
getEquivalentPairs(Graph<V,?> 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 boolean |
isStructurallyEquivalent(Graph<V,?> g,
V v1,
V v2)
Checks whether a pair of vertices are structurally equivalent. |
VertexPartition<V,E> |
transform(Graph<V,E> g)
|
| Methods inherited from class java.lang.Object |
|---|
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait |
| Constructor Detail |
|---|
public StructurallyEquivalent()
| Method Detail |
|---|
public VertexPartition<V,E> transform(Graph<V,E> g)
protected Set<Pair<V>> getEquivalentPairs(Graph<V,?> g)
g -
protected boolean isStructurallyEquivalent(Graph<V,?> g,
V v1,
V v2)
g - the graph in which the structural equivalence comparison is to take placev1 - the vertex to check for structural equivalence to v2v2 - the vertex to check for structural equivalence to v1
protected boolean canPossiblyCompare(V v1,
V v2)
v1 - v2 -
|
||||||||||
| PREV CLASS NEXT CLASS | FRAMES NO FRAMES | |||||||||
| SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD | |||||||||