V
 the type of the verticesE
 the type of the edgespublic class AHURootedTreeIsomorphismInspector<V,E> extends Object implements IsomorphismInspector<V,E>
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.
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.
Constructor and Description 

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

Modifier and Type  Method and 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.

public AHURootedTreeIsomorphismInspector(Graph<V,E> tree1, V root1, Graph<V,E> tree2, V root2)
tree1
 the first rooted treeroot1
 the root of the first treetree2
 the second rooted treeroot2
 the root of the second treeNullPointerException
 if tree1
or tree2
is null
NullPointerException
 if root1
or root2
is null
IllegalArgumentException
 if tree1
or tree2
is emptyIllegalArgumentException
 if root1
or root2
is an invalid vertexpublic Iterator<GraphMapping<V,E>> getMappings()
getMappings
in interface IsomorphismInspector<V,E>
public boolean isomorphismExists()
isomorphismExists
in interface IsomorphismInspector<V,E>
public IsomorphicGraphMapping<V,E> getMapping()
null
if none exists.null
is none existsCopyright © 2019. All rights reserved.