Package org.jgrapht.alg.isomorphism

Class AHURootedTreeIsomorphismInspector<V,E>

java.lang.Object

org.jgrapht.alg.isomorphism.AHURootedTreeIsomorphismInspector<V,E>

Type Parameters:

V - the type of the vertices

E - the type of the edges

All Implemented Interfaces:

IsomorphismInspector<V,E>

public class AHURootedTreeIsomorphismInspector<V,E>
extends Object
implements IsomorphismInspector<V,E>

This is an implementation of the AHU algorithm for detecting an (unweighted) isomorphism between two rooted trees. Please see mathworld.wolfram.com for a complete definition of the isomorphism problem for general graphs.

The original algorithm was first presented in "Alfred V. Aho and John E. Hopcroft. 1974. The Design and Analysis of Computer Algorithms (1st ed.). Addison-Wesley Longman Publishing Co., Inc., Boston, MA, USA."

This implementation runs in linear time (in the number of vertices of the input trees) while using a linear amount of memory.

Note: If the input graph is directed, it effectively considers only the subtree reachable from the specified root.

For an implementation that supports unrooted trees see AHUUnrootedTreeIsomorphismInspector.
For an implementation that supports rooted forests see AHUForestIsomorphismInspector.

Note: This inspector only returns a single mapping (chosen arbitrarily) rather than all possible mappings.

Author:

Alexandru Valeanu

Constructor Summary

Constructors

Constructor	Description
AHURootedTreeIsomorphismInspector(Graph<V,E> tree1, V root1, Graph<V,E> tree2, V root2)	Construct a new AHU rooted tree isomorphism inspector.

Method Summary

Modifier and Type	Method	Description
IsomorphicGraphMapping<V,E>	getMapping()	Get an isomorphism between the input trees or null if none exists.
Iterator<GraphMapping<V,E>>	getMappings()	Get an iterator over all calculated (isomorphic) mappings between two graphs.
boolean	isomorphismExists()	Check if an isomorphism exists.

Methods inherited from class java.lang.Object

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

Constructor Detail

AHURootedTreeIsomorphismInspector

public AHURootedTreeIsomorphismInspector(Graph<V,E> tree1,
                                         V root1,
                                         Graph<V,E> tree2,
                                         V root2)

Construct a new AHU rooted tree isomorphism inspector. Note: The constructor does NOT check if the input trees are valid.

Parameters:

tree1 - the first rooted tree

root1 - the root of the first tree

tree2 - the second rooted tree

root2 - the root of the second tree

Throws:

NullPointerException - if tree1 or tree2 is null

NullPointerException - if root1 or root2 is null

IllegalArgumentException - if tree1 or tree2 is empty

IllegalArgumentException - if root1 or root2 is an invalid vertex

Method Detail

getMappings

public Iterator<GraphMapping<V,E>> getMappings()

Get an iterator over all calculated (isomorphic) mappings between two graphs.

Specified by:

getMappings in interface IsomorphismInspector<V,E>

Returns:

an iterator over all calculated (isomorphic) mappings between two graphs

isomorphismExists

public boolean isomorphismExists()

Check if an isomorphism exists.

Specified by:

isomorphismExists in interface IsomorphismInspector<V,E>

Returns:

true if there is an isomorphism, false if there is no isomorphism

getMapping

public IsomorphicGraphMapping<V,E> getMapping()

Get an isomorphism between the input trees or null if none exists.

Returns:

isomorphic mapping, null is none exists