Module org.jgrapht.core
Package org.jgrapht.alg.isomorphism

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 -