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 vertices
E - the type of the edges
All Implemented Interfaces:
IsomorphismInspector<V,​E>
public class AHUUnrootedTreeIsomorphismInspector<V,​E>
extends java.lang.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.). 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.

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

    Constructors 
    Constructor Description
    AHUUnrootedTreeIsomorphismInspector​(Graph<V,​E> tree1, Graph<V,​E> tree2)
    Construct a new AHU unrooted 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.
    java.util.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 Details

    • AHUUnrootedTreeIsomorphismInspector

      public AHUUnrootedTreeIsomorphismInspector​(Graph<V,​E> tree1, Graph<V,​E> tree2)
      Construct a new AHU unrooted tree isomorphism inspector. Note: The constructor does NOT check if the input trees are valid.
      Parameters:
      tree1 - the first tree
      tree2 - the second tree
      Throws:
      java.lang.NullPointerException - if tree1 or tree2 is null
      java.lang.IllegalArgumentException - if tree1 or tree2 is not undirected
      java.lang.IllegalArgumentException - if tree1 or tree2 is empty

  • Method Details