V
- the type of the verticesE
- the type of the edgespublic class AHUForestIsomorphismInspector<V,E> extends Object implements IsomorphismInspector<V,E>
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.
Constructor and Description |
---|
AHUForestIsomorphismInspector(Graph<V,E> forest1,
Set<V> roots1,
Graph<V,E> forest2,
Set<V> roots2)
Construct a new AHU rooted forest isomorphism inspector.
|
Modifier and Type | Method and Description |
---|---|
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.
|
public AHUForestIsomorphismInspector(Graph<V,E> forest1, Set<V> roots1, Graph<V,E> forest2, Set<V> roots2)
forest1
- the first rooted forestroots1
- the roots of the first forestforest2
- the second rooted forestroots2
- the roots of the second forestNullPointerException
- if forest1
or forest2
is null
NullPointerException
- if roots1
or roots2
is null
IllegalArgumentException
- if forest1
or forest2
is emptyIllegalArgumentException
- if roots1
or roots2
is emptyIllegalArgumentException
- if roots1
or roots2
contain an invalid
vertexpublic Iterator<GraphMapping<V,E>> getMappings()
getMappings
in interface IsomorphismInspector<V,E>
public boolean isomorphismExists()
isomorphismExists
in interface IsomorphismInspector<V,E>
public IsomorphicGraphMapping<V,E> getMapping()
null
if none exists.null
is none existsCopyright © 2018. All rights reserved.