Package org.graph4j.isomorphism

Class VF2ExactState

java.lang.Object

org.graph4j.isomorphism.AbstractState

org.graph4j.isomorphism.AbstractVF2State

org.graph4j.isomorphism.VF2ExactState

All Implemented Interfaces:

State

public class VF2ExactState
extends AbstractVF2State

Class for the VF2 algorithm for exact graph isomorphism.

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
VF2ExactState(Digraph g1, Digraph g2)
VF2ExactState(Digraph g1, Digraph g2, boolean cache)
VF2ExactState(VF2ExactState 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 the same as in the subgraph G2(s)
boolean	isDead()	For exact isomorphism, a state is 'dead' if the number of 'in'/'out'/'both' vertices in the subgraph G1(s) is different from that in the subgraph G2(s)
boolean	isGoal()	For exact isomorphism, a state is complete if all vertices from the both graphs 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

VF2ExactState

public VF2ExactState(Digraph g1,
 Digraph g2)

VF2ExactState

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

VF2ExactState

public VF2ExactState(VF2ExactState 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 the same 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 exact isomorphism, a state is complete if all vertices from the both graphs are mapped.

Specified by:

isGoal in interface State

Specified by:

isGoal in class AbstractVF2State

isDead

public boolean isDead()

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

Specified by:

isDead in interface State

Specified by:

isDead in class AbstractVF2State