V- the type of the vertices
E- the type of the edges
public 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.). 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
For an implementation that supports rooted forests see
Note: This inspector only returns a single mapping (chosen arbitrarily) rather than all possible mappings.
|Constructor and Description|
Construct a new AHU rooted tree isomorphism inspector.
|Modifier and Type||Method and Description|
Get an isomorphism between the input trees or
Get an iterator over all calculated (isomorphic) mappings between two graphs.
Check if an isomorphism exists.
public AHURootedTreeIsomorphismInspector(Graph<V,E> tree1, V root1, Graph<V,E> tree2, V root2)
tree1- the first rooted tree
root1- the root of the first tree
tree2- the second rooted tree
root2- the root of the second tree
root2is an invalid vertex
public Iterator<GraphMapping<V,E>> getMappings()
public boolean isomorphismExists()
public IsomorphicGraphMapping<V,E> getMapping()
nullif none exists.
nullis none exists
Copyright © 2018. All rights reserved.