Class AHUForestIsomorphismInspector<V,E>
- Type Parameters:
V
- the type of the verticesE
- the type of the edges
- All Implemented Interfaces:
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.
-
Field Summary
Fields -
Constructor Summary
Constructors -
Method Summary
Modifier and TypeMethodDescriptionGet an isomorphism between the input forests ornull
if none exists.Get an iterator over all calculated (isomorphic) mappings between two graphs.boolean
Check if an isomorphism exists.private void
-
Field Details
-
forest1
-
forest2
-
roots1
-
roots2
-
computed
private boolean computed -
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 forestroots1
- the roots of the first forestforest2
- the second rooted forestroots2
- the roots of the second forest- Throws:
NullPointerException
- ifforest1
orforest2
isnull
NullPointerException
- ifroots1
orroots2
isnull
IllegalArgumentException
- ifforest1
orforest2
is emptyIllegalArgumentException
- ifroots1
orroots2
is emptyIllegalArgumentException
- ifroots1
orroots2
contain an invalid vertex
-
-
Method Details
-
validateForest
-
getMappings
Get an iterator over all calculated (isomorphic) mappings between two graphs.- Specified by:
getMappings
in interfaceIsomorphismInspector<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 interfaceIsomorphismInspector<V,
E> - Returns:
- true if there is an isomorphism, false if there is no isomorphism
-
createSingleRootGraph
-
getMapping
Get an isomorphism between the input forests ornull
if none exists.- Returns:
- isomorphic mapping,
null
is none exists
-