- Type Parameters:
V- the type of the vertices
E- the type of the edges
- All Implemented Interfaces:
public class AHUForestIsomorphismInspector<V,E> extends Object implements IsomorphismInspector<V,E>This is an implementation of the AHU algorithm for detecting an (unweighted) isomorphism between two rooted forests. 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., page 84). Addison-Wesley Longman Publishing Co., Inc., Boston, MA, USA."
This implementation runs in linear time (in the number of vertices of the input forests) while using a linear amount of memory.
Note: This implementation requires the input graphs to have valid vertex suppliers (see
Note: This inspector only returns a single mapping (chosen arbitrarily) rather than all possible mappings.
- Alexandru Valeanu
All Methods Instance Methods Concrete Methods Modifier and Type Method Description
getMapping()Get an isomorphism between the input forests or
nullif none exists.
getMappings()Get an iterator over all calculated (isomorphic) mappings between two graphs.
isomorphismExists()Check if an isomorphism exists.
public AHUForestIsomorphismInspector(Graph<V,E> forest1, Set<V> roots1, Graph<V,E> forest2, Set<V> roots2)Construct a new AHU rooted forest isomorphism inspector. Note: The constructor does NOT check if the input forests are valid trees.
forest1- the first rooted forest
roots1- the roots of the first forest
forest2- the second rooted forest
roots2- the roots of the second forest
roots2contain an invalid vertex
public Iterator<GraphMapping<V,E>> getMappings()Get an iterator over all calculated (isomorphic) mappings between two graphs.
public boolean isomorphismExists()Check if an isomorphism exists.