Package org.graph4j.isomorphism

Class AbstractUllmanState

java.lang.Object

org.graph4j.isomorphism.AbstractState

org.graph4j.isomorphism.AbstractUllmanState

All Implemented Interfaces:

State

Direct Known Subclasses:

UllmanExactState, UllmanSubState

public abstract class AbstractUllmanState
extends AbstractState

Abstract class for the Ullman's algorithm: exact isomorphism and subgraph isomorphism.

Based on the paper " J.R. Ullmann, An Algorithm for Subgraph Isomorphism, Journal of the Association for Computing Machinery, 1976"

A matrix M is used to store the compatibility between the vertices of the two graphs.

After a pair of vertices is added to the matching, the matrix M is refined, in order to remove the inconsistent pairs, thus reducing the search space.

Author:

Ignat Gabriel-Andrei

Field Summary

Fields

Modifier and Type	Field	Description
static final int	COMPATIBLE
protected int[][]	M
protected int	prev_1
protected int	prev_2

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
AbstractUllmanState(Digraph g1, Digraph g2)
AbstractUllmanState(Digraph g1, Digraph g2, boolean cache)
AbstractUllmanState(AbstractUllmanState s)	Copy constructor: the arrays are just referenced, for memory efficiency

Method Summary

Modifier and Type	Method	Description
void	addPair()	Adds the pair (prev_1, prev_2) to the matching
void	backTrack()	Return to the previous state
abstract boolean	exactOrSubgraphIsomorphismCompatibilityCheck(int v1, int v2)	Compatibility function for the 2 cases: exact and subgraph isomorphism
protected boolean	existsCandidateNeighbourInSecondGraph(int i, int j)	For every neighbour of i, there must be at least one candidate that is neighbour of j If this condition is not respected, then j is eliminated as a candidate for i
protected List<Integer>	getCandidates(int i)
abstract boolean	isDead()	Checks if the current state can be pruned.
boolean	isFeasiblePair()	Feasible pair: vertices are compatible
abstract boolean	isGoal()	Checks if the current state is complete.
boolean	nextPair()	Finds the next pair of vertices to be matched prev_1 must always be equal to core_len(clasic backtracking behaviour) prev_2 will have values that are compatible with prev_1
void	resetPreviousVertices()	After a successful addPair(), we must reinitialize prev_1 and prev_2 in order to find the next pair

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

Field Details

COMPATIBLE

public static final int COMPATIBLE

See Also:

• Constant Field Values

M

protected int[][] M

prev_1

protected int prev_1

prev_2

protected int prev_2

Constructor Details

AbstractUllmanState

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

Parameters:

g1 - the first graph, with the vertices ordered by degree.

g2 - the second graph, with the vertices ordered by degree.

cache - true if caching is enabled.

AbstractUllmanState

public AbstractUllmanState(Digraph g1,
 Digraph g2)

AbstractUllmanState

public AbstractUllmanState(AbstractUllmanState s)

Copy constructor: the arrays are just referenced, for memory efficiency

Parameters:

s - : the state to be copied

Method Details

exactOrSubgraphIsomorphismCompatibilityCheck

public abstract boolean exactOrSubgraphIsomorphismCompatibilityCheck(int v1,
 int v2)

Compatibility function for the 2 cases: exact and subgraph isomorphism

Parameters:

v1 - the first vertex.

v2 - the seconf vertex.

Returns:

true if they are compatible.

nextPair

public boolean nextPair()

Finds the next pair of vertices to be matched prev_1 must always be equal to core_len(clasic backtracking behaviour) prev_2 will have values that are compatible with prev_1

isFeasiblePair

public boolean isFeasiblePair()

Feasible pair: vertices are compatible

addPair

public void addPair()

Adds the pair (prev_1, prev_2) to the matching

backTrack

public void backTrack()

Return to the previous state

resetPreviousVertices

public void resetPreviousVertices()

After a successful addPair(), we must reinitialize prev_1 and prev_2 in order to find the next pair

isGoal

public abstract boolean isGoal()

Checks if the current state is complete.

isDead

public abstract boolean isDead()

Checks if the current state can be pruned.

existsCandidateNeighbourInSecondGraph

protected boolean existsCandidateNeighbourInSecondGraph(int i,
 int j)

For every neighbour of i, there must be at least one candidate that is neighbour of j If this condition is not respected, then j is eliminated as a candidate for i

Parameters:

i - : node from g1

j - : node from g2, some candidate for i

Returns:

true if the condition is respected, false otherwise

getCandidates

protected List<Integer> getCandidates(int i)