edu.ucla.sspace.graph.isomorphism

Class AbstractIsomorphismTester

java.lang.Object

edu.ucla.sspace.graph.isomorphism.AbstractIsomorphismTester

All Implemented Interfaces:

IsomorphismTester

Direct Known Subclasses:

TypedVF2IsomorphismTester, VF2IsomorphismTester

public abstract class AbstractIsomorphismTester
extends Object
implements IsomorphismTester

An abstraction of an IsomorphismTester that relies on algorithm-specific State implementations to check for edge and vertex contraints when performing isomorphism testing.

This class is a an adaptation of parts of the VFLib library.

Constructor Summary

Constructors

Constructor and Description
AbstractIsomorphismTester()

Method Summary

Methods

Modifier and Type	Method and Description
boolean	areIsomorphic(Graph<? extends Edge> g1, Graph<? extends Edge> g2) Returns true if the graphs are isomorphism of each other.
Map<Integer,Integer>	findIsomorphism(Graph<? extends Edge> g1, Graph<? extends Edge> g2) Returns an isomorphic mapping from the vertices in g1 to the vertices in g2, or an empty Map if no such mapping exists.
protected abstract State	makeInitialState(Graph<? extends Edge> g1, Graph<? extends Edge> g2) Creates an empty State for mapping the vertices of g1 to g2.

Methods inherited from class java.lang.Object

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

Constructor Detail

AbstractIsomorphismTester

public AbstractIsomorphismTester()

Method Detail

areIsomorphic

public boolean areIsomorphic(Graph<? extends Edge> g1,
                    Graph<? extends Edge> g2)

Returns true if the graphs are isomorphism of each other.

Specified by:

areIsomorphic in interface IsomorphismTester

findIsomorphism

public Map<Integer,Integer> findIsomorphism(Graph<? extends Edge> g1,
                                   Graph<? extends Edge> g2)

Returns an isomorphic mapping from the vertices in g1 to the vertices in g2, or an empty Map if no such mapping exists.

Specified by:

findIsomorphism in interface IsomorphismTester

makeInitialState

protected abstract State makeInitialState(Graph<? extends Edge> g1,
                     Graph<? extends Edge> g2)

Creates an empty State for mapping the vertices of g1 to g2.