Class VF2State<V,​E>

  • Type Parameters:
    V - the type of the vertices
    E - the type of the edges
    Direct Known Subclasses:
    VF2GraphIsomorphismState, VF2SubgraphIsomorphismState

    abstract class VF2State<V,​E>
    extends java.lang.Object
    controls the matching between two graphs according to the VF2 algorithm.
    • Field Detail

      • core1

        protected int[] core1
      • core2

        protected int[] core2
      • in1

        protected int[] in1
      • in2

        protected int[] in2
      • out1

        protected int[] out1
      • out2

        protected int[] out2
      • coreLen

        protected int coreLen
      • n1

        protected int n1
      • n2

        protected int n2
      • t1BothLen

        protected int t1BothLen
      • t2BothLen

        protected int t2BothLen
      • t1InLen

        protected int t1InLen
      • t2InLen

        protected int t2InLen
      • t1OutLen

        protected int t1OutLen
      • t2OutLen

        protected int t2OutLen
      • addedVertex1

        protected int addedVertex1
      • addVertex1

        protected int addVertex1
      • addVertex2

        protected int addVertex2
      • vertexComparator

        protected java.util.Comparator<V> vertexComparator
      • edgeComparator

        protected java.util.Comparator<E> edgeComparator
    • Constructor Detail

      • VF2State

        public VF2State​(GraphOrdering<V,​E> g1,
                        GraphOrdering<V,​E> g2,
                        java.util.Comparator<V> vertexComparator,
                        java.util.Comparator<E> edgeComparator)
        Parameters:
        g1 - GraphOrdering on first graph
        g2 - GraphOrdering on second graph (possible subgraph)
        vertexComparator - comparator for semantic equality of vertices
        edgeComparator - comparator for semantic equality of edges
      • VF2State

        public VF2State​(VF2State<V,​E> s)
        copy constructor
        Parameters:
        s -
    • Method Detail

      • nextPair

        public boolean nextPair()
        calculates a pair of nodes which may be added to the current matching, according to the VF2 algorithm.
        Returns:
        false, if there are no more pairs left
      • addPair

        public void addPair()
        adds the pair to the current matching.
      • isGoal

        public boolean isGoal()
        Returns:
        is the matching already complete?
      • isFeasiblePair

        public abstract boolean isFeasiblePair()
        Returns:
        true, if the already matched vertices of graph1 plus the first vertex of nextPair are isomorphic to the already matched vertices of graph2 and the second one vertex of nextPair.
      • backtrack

        public void backtrack()
        removes the last added pair from the matching
      • areCompatibleVertexes

        protected boolean areCompatibleVertexes​(int v1,
                                                int v2)
        checks the vertices v1 and v2 for semantic equivalence
        Parameters:
        v1 -
        v2 -
        Returns:
        v1 and v2 are equivalent
      • areCompatibleEdges

        protected boolean areCompatibleEdges​(int v1,
                                             int v2,
                                             int u1,
                                             int u2)
        checks the edges from v1 to v2 and from u1 to u2 for semantic equivalence
        Parameters:
        v1 -
        v2 -
        u1 -
        u2 -
        Returns:
        edges are equivalent
      • resetAddVertexes

        public void resetAddVertexes()
      • showLog

        protected void showLog​(java.lang.String method,
                               java.lang.String str)
        creates the debug output only if DEBUG is true.
        Parameters:
        method -
        str -