Package org.graph4j.isomorphism

Class UllmanSubState

java.lang.Object

org.graph4j.isomorphism.AbstractState

org.graph4j.isomorphism.AbstractUllmanState

org.graph4j.isomorphism.UllmanSubState

All Implemented Interfaces:

State

public class UllmanSubState
extends AbstractUllmanState

Class for the Ullman algorithm for exact graph isomorphism. Two vertices are compatible if the degree in the first graph is less than or equal to the degree in the second graph.

Author:

Ignat Gabriel-Andrei

Field Summary

Fields inherited from class org.graph4j.isomorphism.AbstractUllmanState

COMPATIBLE, M, prev_1, 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
UllmanSubState(Digraph g1, Digraph g2)
UllmanSubState(Digraph g1, Digraph g2, boolean cache)
UllmanSubState(UllmanSubState s)

Method Summary

Modifier and Type	Method	Description
boolean	exactOrSubgraphIsomorphismCompatibilityCheck(int vertexIndex1, int vertexIndex2)	For exact isomorphism, two vertices are compatible if the degree in the first graph is less than or equal to the degree in the second graph.
boolean	isDead()	A partial mapping is "dead" if there is a vertex from the first graph that has no compatible vertex in the second graph.
boolean	isGoal()	For subgraph isomorphism, a mapping is complete when all vertices from the first graph are mapped.

Methods inherited from class org.graph4j.isomorphism.AbstractUllmanState

addPair, backTrack, existsCandidateNeighbourInSecondGraph, getCandidates, 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

UllmanSubState

public UllmanSubState(Digraph g1,
 Digraph g2)

UllmanSubState

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

UllmanSubState

public UllmanSubState(UllmanSubState s)

Method Details

exactOrSubgraphIsomorphismCompatibilityCheck

public boolean exactOrSubgraphIsomorphismCompatibilityCheck(int vertexIndex1,
 int vertexIndex2)

For exact isomorphism, two vertices are compatible if the degree in the first graph is less than or equal to the degree in the second graph.

Specified by:

exactOrSubgraphIsomorphismCompatibilityCheck in class AbstractUllmanState

Parameters:

vertexIndex1 - the index of the vertex in the first graph (in the list of vertices ordered by degree)

vertexIndex2 - the index of the vertex in the second graph (in the list of vertices ordered by degree)

Returns:

true if the vertices are compatible, false otherwise.

isGoal

public boolean isGoal()

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

Specified by:

isGoal in interface State

Specified by:

isGoal in class AbstractUllmanState

Returns:

true if the current state is complete.

isDead

public boolean isDead()

A partial mapping is "dead" if there is a vertex from the first graph that has no compatible vertex in the second graph.

Specified by:

isDead in interface State

Specified by:

isDead in class AbstractUllmanState

Returns:

true if the current state is dead.