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

    • 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