Package org.graph4j.isomorphism

Class VF2SubState

java.lang.Object

org.graph4j.isomorphism.AbstractState

org.graph4j.isomorphism.AbstractVF2State

org.graph4j.isomorphism.VF2SubState

All Implemented Interfaces:

State

public class VF2SubState
extends AbstractVF2State

Class for the VF2 algorithm for subgraph isomorphism.

The first graph is the subgraph and the second graph is the graph where we search the isomorphic subgraph.

Author:

Ignat Gabriel-Andrei

Field Summary

Fields inherited from class org.graph4j.isomorphism.AbstractVF2State

in1, in2, last_added1, out1, out2, prev_1, prev_2, t1both_len, t1in_len, t1out_len, t2both_len, t2in_len, t2out_len

Fields inherited from class org.graph4j.isomorphism.AbstractState

core_1, core_2, core_len, n1, n2, o1, o2

Fields inherited from interface org.graph4j.isomorphism.State

DEBUG, NULL_NODE

Constructor Summary

Constructors

Constructor	Description
VF2SubState(Digraph g1, Digraph g2, boolean cache)
VF2SubState(VF2SubState s)

Method Summary

Modifier and Type	Method	Description
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 the number of 'in'/'out'/'new' vertices in the subgraph G1(s) is lower or equal as in the subgraph G2(s)
boolean	isDead()	For subgraph isomorphism, a state is 'dead' if the number of 'in'/'out'/'both' vertices in the subgraph G1(s) is bigger from that in the subgraph G2(s)
boolean	isGoal()	For subgraph isomorphism, a state is complete if all vertices from the first graph are mapped.

Methods inherited from class org.graph4j.isomorphism.AbstractVF2State

addPair, backTrack, isFeasiblePair, nextPair, resetPreviousVertices

Methods inherited from class org.graph4j.isomorphism.AbstractState

compatibleEdges, compatibleVertices, getCoreLen, getMapping

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Details

VF2SubState

public VF2SubState(Digraph g1,
 Digraph g2,
 boolean cache)

VF2SubState

public VF2SubState(VF2SubState s)

Method Details

exactOrSubgraphIsomorphismCompatibilityCheck

public 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 the number of 'in'/'out'/'new' vertices in the subgraph G1(s) is lower or equal as in the subgraph G2(s)

Specified by:

exactOrSubgraphIsomorphismCompatibilityCheck in class AbstractVF2State

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

isGoal

public boolean isGoal()

For subgraph isomorphism, a state is complete if all vertices from the first graph are mapped.

Specified by:

isGoal in interface State

Specified by:

isGoal in class AbstractVF2State

isDead

public boolean isDead()

For subgraph isomorphism, a state is 'dead' if the number of 'in'/'out'/'both' vertices in the subgraph G1(s) is bigger from that in the subgraph G2(s)

Specified by:

isDead in interface State

Specified by:

isDead in class AbstractVF2State