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