Class VF2State<V,E>

java.lang.Object
org.jgrapht.alg.isomorphism.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 Object
controls the matching between two graphs according to the VF2 algorithm.
  • Field Details

    • NULL_NODE

      public static final int NULL_NODE
      See Also:
    • DEBUG

      protected static final boolean DEBUG
      See Also:
    • core1

      protected final int[] core1
    • core2

      protected final int[] core2
    • in1

      protected final int[] in1
    • in2

      protected final int[] in2
    • out1

      protected final int[] out1
    • out2

      protected final int[] out2
    • n1

      protected final int n1
    • n2

      protected final int n2
    • coreLen

      protected int coreLen
    • 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
    • g1

      protected final GraphOrdering<V,E> g1
    • g2

      protected final GraphOrdering<V,E> g2
    • vertexComparator

      protected final Comparator<V> vertexComparator
    • edgeComparator

      protected final Comparator<E> edgeComparator
  • Constructor Details

    • VF2State

      public VF2State(GraphOrdering<V,E> g1, GraphOrdering<V,E> g2, Comparator<V> vertexComparator, 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 Details

    • 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 $v_1$ and $v_2$ 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 $v_1$ to $v_2$ and from $u_1$ to $u_2$ for semantic equivalence
      Parameters:
      v1 -
      v2 -
      u1 -
      u2 -
      Returns:
      edges are equivalent
    • getCurrentMapping

      public IsomorphicGraphMapping<V,E> getCurrentMapping()
    • resetAddVertexes

      public void resetAddVertexes()
    • showLog

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