Package org.graph4j.isomorphism

Class TreeIsomorphism

java.lang.Object
org.graph4j.isomorphism.TreeIsomorphism
All Implemented Interfaces:
IsomorphismAlgorithm
public class TreeIsomorphism extends Object implements IsomorphismAlgorithm
Algorithm for testing isomorphism of undirected trees.

This algorithm is based on "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.", page 83-84.

Time complexity: linear in the number of vertices of the input trees. Space complexity: linear in the number of vertices of the input trees.

Author:
Ignat Gabriel-Andrei, Cristian Frasinaru
See Also:

  • Constructor Details

    • TreeIsomorphism

      public TreeIsomorphism(Graph tree1, Graph tree2)
      Constructor for the tree isomorphism algorithm. It does not verify if the input graphs are actually trees.
      Parameters:
      tree1 - the first tree.
      tree2 - the second tree.
      Throws:
      NullPointerException - if either tree1 or tree2 is null.
      IllegalArgumentException - if either tree1 or tree2 is not undirected.

  • Method Details

    • areIsomorphic

      public boolean areIsomorphic()
      Description copied from interface: IsomorphismAlgorithm
      Checks if the graphs are isomorphic.
      Specified by:
      areIsomorphic in interface IsomorphismAlgorithm
      Returns:
      true if the graphs are isomorphic, false otherwise.

    • findIsomorphism

      public Isomorphism findIsomorphism()
      Description copied from interface: IsomorphismAlgorithm
      Finds the isomorphic mapping between the first and the second graph.
      Specified by:
      findIsomorphism in interface IsomorphismAlgorithm
      Returns:
      the isomorphism or null if the graphs are not isomorphic.

    • computeIsomorphic

      protected boolean computeIsomorphic()

    • getTree1

      public Graph getTree1()
      The first tree.
      Returns:
      the first tree.

    • getTree2

      public Graph getTree2()
      The second tree.
      Returns:
      the second tree.