Overview | Package | Class | Use | Tree | Deprecated | Index | Help
PREV CLASS NEXT CLASS | FRAMES NO FRAMES
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD

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

Overview | Package | Class | Use | Tree | Deprecated | Index | Help
PREV CLASS NEXT CLASS | FRAMES NO FRAMES
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD