Package org.graph4j.isomorphism

Class AbstractState

java.lang.Object

org.graph4j.isomorphism.AbstractState

All Implemented Interfaces:

State

Direct Known Subclasses:

AbstractUllmanState, AbstractVF2State

public abstract class AbstractState
extends Object
implements State

Abstract class for the state of the search algorithm.

A state is a partial solution of the graph isomorphism problem.

It has fields for the current partial forward/backward mapping.

A partial mapping works only with indices of the vertices in the ordered digraph(meaning the position in the sorted list of the vertices).

Author:

Ignat Gabriel-Andrei

Field Summary

Fields

Modifier and Type	Field	Description
protected int[]	core_1
protected int[]	core_2
protected int	core_len
protected int	n1
protected int	n2
protected OrderedDigraph	o1
protected OrderedDigraph	o2

Fields inherited from interface org.graph4j.isomorphism.State

DEBUG, NULL_NODE

Constructor Summary

Constructors

Constructor	Description
AbstractState()

Method Summary

Modifier and Type	Method	Description
protected boolean	compatibleEdges(int i1, int j1, int i2, int j2)	If the graphs allow multiple edges, the edges must have the same multiplicity
protected boolean	compatibleVertices(int vertexIndex1, int vertexIndex2)	If the graphs allow self loops, the vertices must have the same number of self loops
int	getCoreLen()
Isomorphism	getMapping()	Computes the mapping when a complete solution is found.

Methods inherited from class java.lang.Object

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

Methods inherited from interface org.graph4j.isomorphism.State

addPair, backTrack, isDead, isFeasiblePair, isGoal, nextPair, resetPreviousVertices

Field Details

o1

protected OrderedDigraph o1

o2

protected OrderedDigraph o2

n1

protected int n1

n2

protected int n2

core_len

protected int core_len

core_1

protected int[] core_1

core_2

protected int[] core_2

Constructor Details

AbstractState

public AbstractState()

Method Details

getCoreLen

public int getCoreLen()

Specified by:

getCoreLen in interface State

getMapping

public Isomorphism getMapping()

Computes the mapping when a complete solution is found.

Specified by:

getMapping in interface State

Returns:

isomorphic graph mapping

compatibleVertices

protected boolean compatibleVertices(int vertexIndex1,
 int vertexIndex2)

If the graphs allow self loops, the vertices must have the same number of self loops

Parameters:

vertexIndex1 - the index of a vertex from the ordered digraph 1 (the index in the sorted list of vertices)

vertexIndex2 - the index of a vertex from the ordered digraph 2 (the index in the sorted list of vertices)

Returns:

true if the vertices are compatible, false otherwise

compatibleEdges

protected boolean compatibleEdges(int i1,
 int j1,
 int i2,
 int j2)

If the graphs allow multiple edges, the edges must have the same multiplicity

Parameters:

i1 - the index of the source vertex of the edge in the ordered digraph 1

j1 - the index of the target vertex of the edge in the ordered digraph 1

i2 - the index of the source vertex of the edge in the ordered digraph 2

j2 - the index of the target vertex of the edge in the ordered digraph 2

Returns:

true if the edges are compatible, false otherwise