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/s00224-016-9686-0, 2016 (color refinement) The complexity of this algorithm is O(|V| + |E| log |V|).- Author:
- Christoph GrĂ¼ne, Dennis Fischer
-
-
Method Summary
All Methods Instance Methods Concrete Methods Modifier and Type Method Description Iterator<GraphMapping<V,E>>
getMappings()
Get an iterator over all calculated (isomorphic) mappings between two graphs.boolean
isomorphismExists()
Check if an isomorphism exists.
-
-
-
Constructor Detail
-
ColorRefinementIsomorphismInspector
public ColorRefinementIsomorphismInspector(Graph<V,E> graph1, Graph<V,E> graph2)
Constructor for a isomorphism inspector based on color refinement. It checks whethergraph1
andgraph2
are isomorphic.- Parameters:
graph1
- the first graphgraph2
- the second graph
-
-
Method Detail
-
getMappings
public Iterator<GraphMapping<V,E>> 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
-
-