Module org.jgrapht.core

Package org.jgrapht.alg.isomorphism

Class AHUForestIsomorphismInspector<V,E>

java.lang.Object

org.jgrapht.alg.isomorphism.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 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 Summary

Fields

Modifier and Type	Field	Description
private boolean	computed
private final Graph<V,E>	forest1
private final Graph<V,E>	forest2
private IsomorphicGraphMapping<V,E>	isomorphicMapping
private final Set<V>	roots1
private final Set<V>	roots2

Constructor Summary

Constructors

Constructor	Description
AHUForestIsomorphismInspector(Graph<V,E> forest1, Set<V> roots1, Graph<V,E> forest2, Set<V> roots2)	Construct a new AHU rooted forest isomorphism inspector.

Method Summary

Modifier and Type	Method	Description
private Pair<V,Graph<V,E>>	createSingleRootGraph(Graph<V,E> forest, Set<V> roots)
IsomorphicGraphMapping<V,E>	getMapping()	Get an isomorphism between the input forests or null if none exists.
Iterator<GraphMapping<V,E>>	getMappings()	Get an iterator over all calculated (isomorphic) mappings between two graphs.
boolean	isomorphismExists()	Check if an isomorphism exists.
private void	validateForest(Graph<V,E> forest, Set<V> roots)

Methods inherited from class java.lang.Object

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

Field Details

forest1

private final Graph<V,E> forest1

forest2

private final Graph<V,E> forest2

roots1

private final Set<V> roots1

roots2

private final Set<V> roots2

computed

private boolean computed

isomorphicMapping

private IsomorphicGraphMapping<V,E> isomorphicMapping

Constructor Details

AHUForestIsomorphismInspector

public AHUForestIsomorphismInspector(Graph<V,E> forest1,
 Set<V> roots1,
 Graph<V,E> forest2,
 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:

NullPointerException - if forest1 or forest2 is null

NullPointerException - if roots1 or roots2 is null

IllegalArgumentException - if forest1 or forest2 is empty

IllegalArgumentException - if roots1 or roots2 is empty

IllegalArgumentException - if roots1 or roots2 contain an invalid vertex

Method Details

validateForest

private void validateForest(Graph<V,E> forest,
 Set<V> roots)

getMappings

public 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,
 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