Package edu.uci.ics.jung.algorithms.blockmodel

Class StructurallyEquivalent<V,E>

java.lang.Object
edu.uci.ics.jung.algorithms.blockmodel.StructurallyEquivalent<V,E>
All Implemented Interfaces:
com.google.common.base.Function<Graph<V,E>,VertexPartition<V,E>>, Function<Graph<V,E>,VertexPartition<V,E>>
public class StructurallyEquivalent<V,E> extends Object implements com.google.common.base.Function<Graph<V,E>,VertexPartition<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.)

Author:
Danyel Fisher

  • Constructor Details

    • StructurallyEquivalent

      public StructurallyEquivalent()

  • Method Details

    • apply

      public VertexPartition<V,E> apply(Graph<V,E> g)
      Specified by:
      apply in interface com.google.common.base.Function<V,E>
      Specified by:
      apply in interface Function<V,E>

    • getEquivalentPairs

      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. (Is this regular equivalence, or whathaveyou?)
      Parameters:
      g - the graph whose equivalent pairs are to be generated
      Returns:
      a Set of Pairs of vertices, where all the vertices in the inner Pairs are equivalent.

    • isStructurallyEquivalent

      protected boolean isStructurallyEquivalent(Graph<V,?> g, V v1, V v2)
      Parameters:
      g - the graph in which the structural equivalence comparison is to take place
      v1 - the vertex to check for structural equivalence to v2
      v2 - the vertex to check for structural equivalence to v1
      Returns:
      true if v1's predecessors/successors are equal to v2's predecessors/successors

    • canBeEquivalent

      protected boolean canBeEquivalent(V v1, V v2)
      This is a space for optimizations. For example, for a bipartite graph, vertices from different partitions cannot possibly be equivalent.
      Parameters:
      v1 - the first vertex to compare
      v2 - the second vertex to compare
      Returns:
      true if the vertices can be equivalent