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 java.lang.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
    java.util.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 Details

    • 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 Details