Module org.jgrapht.core
Package org.jgrapht.alg.isomorphism
Class ColorRefinementIsomorphismInspector<V,E>
java.lang.Object
org.jgrapht.alg.isomorphism.ColorRefinementIsomorphismInspector<V,E>
 Type Parameters:
V
 the type of the verticesE
 the type of the edges
 All Implemented Interfaces:
IsomorphismInspector<V,
E>
public class ColorRefinementIsomorphismInspector<V,E>
extends Object
implements IsomorphismInspector<V,E>
Implementation of the color refinement algorithm isomorphism test using its feature of detecting
isomorphism between two graphs
as described in C. Berkholz, P. Bonsma, and M. Grohe. Tight lower and upper bounds for the
complexity of canonical colour refinement. Theory of Computing
Systems,doi:10.1007/s0022401696860, 2016 (color refinement) The complexity of this algorithm
is O(V + E log V).
 Author:
 Christoph GrĂ¼ne, Dennis Fischer

Constructor Summary

Method Summary
Modifier and TypeMethodDescriptionGet an iterator over all calculated (isomorphic) mappings between two graphs.boolean
Check if an isomorphism exists.

Constructor Details

ColorRefinementIsomorphismInspector
Constructor for a isomorphism inspector based on color refinement. It checks whethergraph1
andgraph2
are isomorphic. Parameters:
graph1
 the first graphgraph2
 the second graph


Method Details

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
 Throws:
IsomorphismUndecidableException
 if the isomorphism test was not executed and the inspector cannot decide whether the graphs are isomorphic

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
 Throws:
IsomorphismUndecidableException
 if the inspector cannot decide whether the graphs are isomorphic
