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|).
  • Field Details

    • graph1

      private Graph<V,E> graph1
      The input graphs
    • graph2

      private Graph<V,E> graph2
      The input graphs
    • isomorphicGraphMapping

      private IsomorphicGraphMapping<V,E> isomorphicGraphMapping
      The isomorphism that is calculated by this color refinement isomorphism inspector
    • isIsomorphic

      private Boolean isIsomorphic
      contains whether the graphs are isomorphic or not. If we cannot decide whether they are isomorphic the value will be not present.
    • isColoringDiscrete

      private boolean isColoringDiscrete
      contains whether the two graphs produce a discrete coloring. Then, we can decide whether the graphs are isomorphic.
    • isForest

      private boolean isForest
      contains whether the two graphs are forests. Forests can be identified to be isomorphic or not.
    • isomorphismTestExecuted

      private boolean isomorphismTestExecuted
      contains whether the isomorphism test is executed to ensure that every operation is defined all the time
  • 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