Class AHUForestIsomorphismInspector<V,​E>

  • Type Parameters:
    V - the type of the vertices
    E - the type of the edges
    All Implemented Interfaces:
    IsomorphismInspector<V,​E>

    public class AHUForestIsomorphismInspector<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 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.

    For an implementation that supports rooted trees see AHURootedTreeIsomorphismInspector and for one for unrooted trees see AHUUnrootedTreeIsomorphismInspector.

    Note: This implementation requires the input graphs to have valid vertex suppliers (see Graph.getVertexSupplier()).

    Note: This inspector only returns a single mapping (chosen arbitrarily) rather than all possible mappings.

    • Field Detail

      • forest1

        private final Graph<V,​E> forest1
      • forest2

        private final Graph<V,​E> forest2
      • roots1

        private final java.util.Set<V> roots1
      • roots2

        private final java.util.Set<V> roots2
      • computed

        private boolean computed
    • Constructor Detail

      • AHUForestIsomorphismInspector

        public AHUForestIsomorphismInspector​(Graph<V,​E> forest1,
                                             java.util.Set<V> roots1,
                                             Graph<V,​E> forest2,
                                             java.util.Set<V> roots2)
        Construct a new AHU rooted forest isomorphism inspector. Note: The constructor does NOT check if the input forests are valid trees.
        Parameters:
        forest1 - the first rooted forest
        roots1 - the roots of the first forest
        forest2 - the second rooted forest
        roots2 - the roots of the second forest
        Throws:
        java.lang.NullPointerException - if forest1 or forest2 is null
        java.lang.NullPointerException - if roots1 or roots2 is null
        java.lang.IllegalArgumentException - if forest1 or forest2 is empty
        java.lang.IllegalArgumentException - if roots1 or roots2 is empty
        java.lang.IllegalArgumentException - if roots1 or roots2 contain an invalid vertex
    • Method Detail

      • validateForest

        private void validateForest​(Graph<V,​E> forest,
                                    java.util.Set<V> roots)
      • getMappings

        public java.util.Iterator<GraphMapping<V,​E>> getMappings()
        Get an iterator over all calculated (isomorphic) mappings between two graphs.
        Specified by:
        getMappings in interface IsomorphismInspector<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 interface IsomorphismInspector<V,​E>
        Returns:
        true if there is an isomorphism, false if there is no isomorphism
      • createSingleRootGraph

        private Pair<V,​Graph<V,​E>> createSingleRootGraph​(Graph<V,​E> forest,
                                                                     java.util.Set<V> roots)
      • getMapping

        public IsomorphicGraphMapping<V,​E> getMapping()
        Get an isomorphism between the input forests or null if none exists.
        Returns:
        isomorphic mapping, null is none exists