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 vertices

E - 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

Constructor Summary

Constructors

Constructor	Description
ColorRefinementIsomorphismInspector(Graph<V,E> graph1, Graph<V,E> graph2)	Constructor for a isomorphism inspector based on color refinement.

Method Summary

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.

Methods inherited from class java.lang.Object

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

Constructor Detail

ColorRefinementIsomorphismInspector

public ColorRefinementIsomorphismInspector(Graph<V,E> graph1,
                                           Graph<V,E> graph2)

Constructor for a isomorphism inspector based on color refinement. It checks whether graph1 and graph2 are isomorphic.

Parameters:

graph1 - the first graph

graph2 - 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 interface IsomorphismInspector<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 interface IsomorphismInspector<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