Package org.graph4j.isomorphism

Class ForestIsomorphism

java.lang.Object

org.graph4j.isomorphism.ForestIsomorphism

All Implemented Interfaces:

IsomorphismAlgorithm

public class ForestIsomorphism
extends Object
implements IsomorphismAlgorithm

Algorithm for testing isomorphism of undirected forests. The implementation runs in linear time (in the number of vertices of the input forest).

Author:

Cristian Frasinaru

See Also:

• TreeIsomorphism

Constructor Summary

Constructors

Constructor	Description
ForestIsomorphism(Graph forest1, Graph forest2)	Constructor for the forest 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

ForestIsomorphism

public ForestIsomorphism(Graph forest1,
 Graph forest2)

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

Parameters:

forest1 - the first forest.

forest2 - the second forest.

Throws:

NullPointerException - if either forest1 or forest2 is null.

IllegalArgumentException - if either forest1 or forest2 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.