Package org.graph4j.isomorphism

Class UllmanExactState

java.lang.Object

org.graph4j.isomorphism.AbstractState

org.graph4j.isomorphism.AbstractUllmanState

org.graph4j.isomorphism.UllmanExactState

All Implemented Interfaces:

State

public class UllmanExactState
extends AbstractUllmanState

Class for the Ullman algorithm for exact graph isomorphism. Two vertices are compatible if they have the same degree and same labels.

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
UllmanExactState(Digraph g1, Digraph g2)
UllmanExactState(Digraph g1, Digraph g2, boolean cache)
UllmanExactState(UllmanExactState s)

Method Summary

Modifier and Type	Method	Description
boolean	exactOrSubgraphIsomorphismCompatibilityCheck(int vertexIndex1, int vertexIndex2)	For exact isomorphism, two vertices are compatible if they have the same degree.
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 exact isomorphism, a mapping is complete when all vertices from both graphs 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

UllmanExactState

public UllmanExactState(Digraph g1,
 Digraph g2)

UllmanExactState

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

UllmanExactState

public UllmanExactState(UllmanExactState s)

Method Details

exactOrSubgraphIsomorphismCompatibilityCheck

public boolean exactOrSubgraphIsomorphismCompatibilityCheck(int vertexIndex1,
 int vertexIndex2)

For exact isomorphism, two vertices are compatible if they have the same degree.

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 exact isomorphism, a mapping is complete when all vertices from both graphs are mapped.

Specified by:

isGoal in interface State

Specified by:

isGoal in class AbstractUllmanState

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