Package org.graph4j.isomorphism

Class AbstractGraphIsomorphism

java.lang.Object

org.graph4j.isomorphism.AbstractGraphIsomorphism

All Implemented Interfaces:

GraphIsomorphism

Direct Known Subclasses:

UllmanExactGraphIsomorphism, UllmanSubGraphIsomorphism, VF2ExactGraphIsomorphism, VF2SubGraphIsomorphism

public abstract class AbstractGraphIsomorphism
extends Object
implements GraphIsomorphism

Abstract class for finding the isomorphism between two graphs.

It provides a method for finding all the mappings between two graphs and a method for finding the first mapping.

Author:

Ignat Gabriel-Andrei

Field Summary

Fields

Modifier and Type	Field	Description
protected final boolean	cache
protected final Digraph	dg1
protected final Digraph	dg2

Constructor Summary

Constructors

Constructor	Description
AbstractGraphIsomorphism(Graph g1, Graph g2)
AbstractGraphIsomorphism(Graph g1, Graph g2, boolean cache)	Constructor for the AbstractGraphIsomorphism class.

Method Summary

Modifier and Type	Method	Description
boolean	areIsomorphic()	Checks if the two graphs are isomorphic by computing the first mapping, if it exists.
List<Isomorphism>	getAllMappings()
Optional<Isomorphism>	getMapping()
protected abstract State	getNewStateInstance(State s)
protected abstract State	getStateInstance(Digraph g1, Digraph g2, boolean cache)

Methods inherited from class java.lang.Object

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

Field Details

dg1

protected final Digraph dg1

dg2

protected final Digraph dg2

cache

protected final boolean cache

Constructor Details

AbstractGraphIsomorphism

public AbstractGraphIsomorphism(Graph g1,
 Graph g2,
 boolean cache)

Constructor for the AbstractGraphIsomorphism class.

Parameters:

g1 - the first graph - it is converted to a digraph

g2 - the second graph - it is converted to a digraph

cache - if true, the algorithm will cache the successors, predecessors, the adjacency relations

AbstractGraphIsomorphism

public AbstractGraphIsomorphism(Graph g1,
 Graph g2)

Method Details

areIsomorphic

public boolean areIsomorphic()

Checks if the two graphs are isomorphic by computing the first mapping, if it exists.

Specified by:

areIsomorphic in interface GraphIsomorphism

Returns:

true if the graphs are isomorphic, false otherwise

getMapping

public Optional<Isomorphism> getMapping()

Specified by:

getMapping in interface GraphIsomorphism

Returns:

the first mapping between the two graphs, if it exists.

getAllMappings

public List<Isomorphism> getAllMappings()

Specified by:

getAllMappings in interface GraphIsomorphism

Returns:

all the mappings between the two graphs.

getStateInstance

protected abstract State getStateInstance(Digraph g1,
 Digraph g2,
 boolean cache)

getNewStateInstance

protected abstract State getNewStateInstance(State s)