Class StructurallyEquivalent<V,​E>

  • All Implemented Interfaces:
    org.apache.commons.collections4.Transformer<edu.uci.ics.jung.graph.Graph<V,​E>,​VertexPartition<V,​E>>

    public class StructurallyEquivalent<V,​E>
    extends java.lang.Object
    implements org.apache.commons.collections4.Transformer<edu.uci.ics.jung.graph.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.)

    • Method Summary

      All Methods Instance Methods Concrete Methods 
      Modifier and Type Method Description
      protected boolean canPossiblyCompare​(V v1, V v2)
      This is a space for optimizations.
      protected java.util.Set<edu.uci.ics.jung.graph.util.Pair<V>> getEquivalentPairs​(edu.uci.ics.jung.graph.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​(edu.uci.ics.jung.graph.Graph<V,​?> g, V v1, V v2)
      Checks whether a pair of vertices are structurally equivalent.
      VertexPartition<V,​E> transform​(edu.uci.ics.jung.graph.Graph<V,​E> g)  
      • Methods inherited from class java.lang.Object

        clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
    • Constructor Detail

      • StructurallyEquivalent

        public StructurallyEquivalent()
    • Method Detail

      • transform

        public VertexPartition<V,​E> transform​(edu.uci.ics.jung.graph.Graph<V,​E> g)
        Specified by:
        transform in interface org.apache.commons.collections4.Transformer<V,​E>
      • getEquivalentPairs

        protected java.util.Set<edu.uci.ics.jung.graph.util.Pair<V>> getEquivalentPairs​(edu.uci.ics.jung.graph.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?) Returns a Set of Pairs of vertices, where all the vertices in the inner Pairs are equivalent.
        Parameters:
        g -
      • isStructurallyEquivalent

        protected boolean isStructurallyEquivalent​(edu.uci.ics.jung.graph.Graph<V,​?> g,
                                                   V v1,
                                                   V 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:
        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
      • canPossiblyCompare

        protected boolean canPossiblyCompare​(V v1,
                                             V v2)
        This is a space for optimizations. For example, for a bipartite graph, vertices from different partitions cannot possibly be compared.
        Parameters:
        v1 -
        v2 -