Package org.graph4j.isomorphism

Class RootedTreeIsomorphism

java.lang.Object

org.graph4j.isomorphism.RootedTreeIsomorphism

All Implemented Interfaces:

IsomorphismAlgorithm

public class RootedTreeIsomorphism
extends Object
implements IsomorphismAlgorithm

Algorithm for testing isomorphism of rooted 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.

The trees may be either directed or undirected, but if they are directed, all edges should flow from the root (they should be arborescences).

Author:

Ignat Gabriel-Andrei, Cristian Frasinaru

Constructor Summary

Constructors

Constructor	Description
RootedTreeIsomorphism(Graph tree1, Graph tree2, int root1, int root2)	Constructor for the rooted tree isomorphism algorithm.
RootedTreeIsomorphism(RootedTree rootedTree1, RootedTree rootedTree2)	Constructor for the rooted tree isomorphism algorithm.

Method Summary

Modifier and Type	Method	Description
boolean	areIsomorphic()	Checks if the graphs are isomorphic.
Isomorphism	findIsomorphism()	Finds the isomorphic mapping between the first and the second graph.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Methods inherited from interface org.graph4j.isomorphism.IsomorphismAlgorithm

checkTrivialConditions

Constructor Details

RootedTreeIsomorphism

public RootedTreeIsomorphism(Graph tree1,
 Graph tree2,
 int root1,
 int root2)

Constructor for the rooted tree isomorphism algorithm. It does not verify if the input graphs are actually trees.

Parameters:

tree1 - first tree.

tree2 - second tree.

root1 - root of the first tree.

root2 - root of the second tree.

Throws:

NullPointerException - if either tree1 or tree2 is null.

IllegalArgumentException - if either root1 or root2 is not in their respective trees.

RootedTreeIsomorphism

public RootedTreeIsomorphism(RootedTree rootedTree1,
 RootedTree rootedTree2)

Constructor for the rooted tree isomorphism algorithm. It does not verify if the input graphs are actually trees.

Parameters:

rootedTree1 - the first rooted tree.

rootedTree2 - the second rooted tree.

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.