Package org.graph4j.isomorphism

Class AbstractVF2State

java.lang.Object
org.graph4j.isomorphism.AbstractState
org.graph4j.isomorphism.AbstractVF2State
All Implemented Interfaces:
State
Direct Known Subclasses:
VF2ExactState, VF2SubState
public abstract class AbstractVF2State extends AbstractState
Abstract class for the VF2(Vento Foggia) algorithm.

Based on the paper "A (sub)graph isomorphism algorithm for matching large graphs - Cordella, L.P. and Foggia, P. and Sansone, C. and Vento, M. - IEEE Transactions on Pattern Analysis and Machine Intelligence, 2004 (10.1109/TPAMI.2004.75)" and the original implementation done by MIVIA research Lab of the University of Salerno

This implementation of the VF2 algorithm was adapted to support all types of graphs.
Author:
Ignat Gabriel-Andrei

  • Field Details

    • t1in_len

      protected int t1in_len

    • t2in_len

      protected int t2in_len

    • t1out_len

      protected int t1out_len

    • t2out_len

      protected int t2out_len

    • t1both_len

      protected int t1both_len

    • t2both_len

      protected int t2both_len

    • in1

      protected int[] in1

    • in2

      protected int[] in2

    • out1

      protected int[] out1

    • out2

      protected int[] out2

    • prev_1

      protected int prev_1

    • prev_2

      protected int prev_2

    • last_added1

      protected int last_added1

  • Constructor Details

    • AbstractVF2State

      public AbstractVF2State(Digraph g1, Digraph g2, boolean cache)
      Constructor for the initial state of the search algorithm.
      Parameters:
      g1 - the first graph.
      g2 - the second graph.
      cache - true if caching is enabled.

    • AbstractVF2State

      public AbstractVF2State(Digraph g1, Digraph g2)

    • AbstractVF2State

      public AbstractVF2State(AbstractVF2State s)
      Copy constructor: the arrays are just referenced, for memory efficiency.
      Parameters:
      s - : the state to be copied

  • Method Details

    • nextPair

      public boolean nextPair()
      Computes the next pair of candidate vertices for the isomorphism. If the previous vertices are not set, they are initialized with 0.
      Returns:
      true if a pair was found, false otherwise

    • isFeasiblePair

      public boolean isFeasiblePair()

      Checks if the pair of vertices is feasible. Checks if the vertices are compatible. For every edge that is going in/out the partial mapping, we check if the corresponding edge is present in the second graph.

      We also count the number of unmapped and out/in/new vertices. For exact isomorphism, a new pair of candidate vertices are feasible if these numbers are equal: term_in1 with term_in2, term_out1 with term_out2, new_1 with new_2.

    • exactOrSubgraphIsomorphismCompatibilityCheck

      public abstract boolean exactOrSubgraphIsomorphismCompatibilityCheck(int term_in1, int term_out1, int term_in2, int term_out2, int new_1, int new_2)
      For exact isomorphism, a new pair of candidate vertices are feasible if these numbers are equal: term_in1 with term_in2, term_out1 with term_out2, new_1 with new_2.
      Parameters:
      term_in1 - number of unmapped vertices that are going in the subgraph G1(s)
      term_out1 - number of unmapped vertices that are going out the subgraph G1(s)
      term_in2 - number of unmapped vertices that are going in the subgraph G2(s)
      term_out2 - number of unmapped vertices that are going out the subgraph G2(s)
      new_1 - number of unmapped vertices that were not yet marked as 'in' or 'out'
      new_2 - number of unmapped vertices that were not yet marked as 'in' or 'out'
      Returns:
      true if the pair is feasible, false otherwise

    • addPair

      public void addPair()
      Adds the pair of vertices to the mapping. Updates the in/out/both counters, the in/out vectors and the mapping.

    • backTrack

      public void backTrack()
      Removes the last added pair of vertices from the mapping. Updates the in/out/both counters, the in/out vectors and the mapping.

    • isGoal

      public abstract boolean isGoal()
      Description copied from interface: State
      Checks if the current state is a goal state(a complete solution was found). Return true if the state is a goal state, false otherwise

    • isDead

      public abstract boolean isDead()
      Description copied from interface: State
      Checks if the current state is a dead end(no solution can be found from here). Return true if the state is a dead end, false otherwise

    • resetPreviousVertices

      public void resetPreviousVertices()