Package org.graph4j.isomorphism

Class RootedForestIsomorphism

java.lang.Object

org.graph4j.isomorphism.RootedForestIsomorphism

All Implemented Interfaces:

IsomorphismAlgorithm

public class RootedForestIsomorphism
extends Object
implements IsomorphismAlgorithm

Algorithm for testing isomorphism of forests with specified roots.

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:

• RootedTreeIsomorphism

Constructor Summary

Constructors

Constructor	Description
RootedForestIsomorphism(Graph forest1, Graph forest2, VertexSet roots1, VertexSet roots2)	Constructor for the rooted forest isomorphism algorithm.

Method Summary

Modifier and Type	Method	Description
boolean	areIsomorphic()	Checks if the graphs are isomorphic.
void	createRootedTreeAlg()
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

RootedForestIsomorphism

public RootedForestIsomorphism(Graph forest1,
 Graph forest2,
 VertexSet roots1,
 VertexSet roots2)

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

Parameters:

forest1 - the first forest.

forest2 - the second forest.

roots1 - the roots of the first forest.

roots2 - the roots of the second forest.

Throws:

NullPointerException - if either forest1 or forest2 is null.

IllegalArgumentException - if either forest1 or forest2 is not a simple graph.

IllegalArgumentException - if either roots1 or roots2 contain vertices that are not in the forest.

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.

createRootedTreeAlg

public void createRootedTreeAlg()