Module org.jgrapht.core
Package org.jgrapht.alg.isomorphism
Class AHUUnrootedTreeIsomorphismInspector<V,E>
java.lang.Object
org.jgrapht.alg.isomorphism.AHUUnrootedTreeIsomorphismInspector<V,E>
 Type Parameters:
V
 the type of the verticesE
 the type of the edges
 All Implemented Interfaces:
IsomorphismInspector<V,
E>
public class AHUUnrootedTreeIsomorphismInspector<V,E>
extends Object
implements IsomorphismInspector<V,E>
This is an implementation of the AHU algorithm for detecting an (unweighted) isomorphism between
two unrooted 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.). AddisonWesley 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.
For an implementation that supports rooted trees see AHURootedTreeIsomorphismInspector
.
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

Method Summary
Modifier and TypeMethodDescriptionGet an isomorphism between the input trees ornull
if none exists.Get an iterator over all calculated (isomorphic) mappings between two graphs.boolean
Check if an isomorphism exists.

Constructor Details

AHUUnrootedTreeIsomorphismInspector
Construct a new AHU unrooted tree isomorphism inspector. Note: The constructor does NOT check if the input trees are valid. Parameters:
tree1
 the first treetree2
 the second tree Throws:
NullPointerException
 iftree1
ortree2
isnull
IllegalArgumentException
 iftree1
ortree2
is not undirectedIllegalArgumentException
 iftree1
ortree2
is empty


Method Details

getMappings
Get an iterator over all calculated (isomorphic) mappings between two graphs. Specified by:
getMappings
in interfaceIsomorphismInspector<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 interfaceIsomorphismInspector<V,
E>  Returns:
 true if there is an isomorphism, false if there is no isomorphism

getMapping
Get an isomorphism between the input trees ornull
if none exists. Returns:
 isomorphic mapping,
null
is none exists
