Package com.jgalgo.alg.isomorphism

Class IsomorphismTesterAbstract

  • All Implemented Interfaces:
    IsomorphismTester
    Direct Known Subclasses:
    IsomorphismTesterVf2
    public abstract class IsomorphismTesterAbstract
extends Object
implements IsomorphismTester
    Abstract class for computing isomorphism mapping between two graphs.

    The class implements the interface by solving the problem on the index graph and then maps the results back to the original graph. The implementation for index graphs is abstract and left to the subclasses.

    Author:
    Barak Ugav

    • Constructor Detail

      • IsomorphismTesterAbstract

        public IsomorphismTesterAbstract()
        Default constructor.

    • Method Detail

      • isomorphicMappingsIter

        public <V1,​E1,​V2,​E2> Iterator<IsomorphismMapping<V1,​E1,​V2,​E2>> isomorphicMappingsIter​(Graph<V1,​E1> g1,
                                                                                                                          Graph<V2,​E2> g2,
                                                                                                                          boolean induced,
                                                                                                                          BiPredicate<? super V1,​? super V2> vertexMatcher,
                                                                                                                          BiPredicate<? super E1,​? super E2> edgeMatcher)
        Description copied from interface: IsomorphismTester
        Get an iterator over all the sub graph isomorphism mappings between two graphs, optionally induced, with vertex and/or edge matchers.

        Given two graphs \(G_1 = (V_1, E_1)\) and \(G_2 = (V_2, E_2)\), a subgraph isomorphism is an injective function \(m: V_1 \rightarrow V_2\) such that if \((u, v) \in E_1\) than \((m(u), m(v)) \in E_2\). In the case of a directed graph, the function must preserve the direction of the edges. An induced subgraph isomorphism is same as above, but the mapping also satisfies \((u, v) \in E_1\) if and only if \((m(u), m(v)) \in E_2\). The first graph \(G_1\) is the smaller graph, and the second graph \(G_2\) is the bigger graph, namely there is a sub graph of g2 that is isomorphic to g1. Note that subgraph isomorphism can only exists between graphs \(G_1\) and \(G_2\) if \(|V_1| \leq |V_2|\) and \(|E_1| \leq |E_2|\). There may be vertices of \(G_2\) that are not mapped to any vertex of \(G_1\), and if non-induced sub graph isomorphism is searched, also edges of \(G_2\) that are not mapped to any edge of \(G_1\) (even if they are connecting mapped vertices of \(G_2\)). In such case the inverse of the returned mappings may not map all vertices and edges of g2, see IsomorphismMapping.

        In addition to the structure of the graphs, this method also takes two predicates that filter pairs of vertices and edges, one from each graph, that are not allowed to be mapped to each other. For a given pair \(v_1,v_2\) where \(v_1 \in V_1\) and \(v_2 \in V_2\), if the vertex matcher returns false, then the pair is not considered for mapping. The edge matchers is used similarly. If a matcher is null, all pairs of vertices or edges are allowed. The matchers allow to compare other properties of the vertices/edge besides their structure, such as weights.

        Note that the type of vertices and edges of the two graphs may be different. Only the structure of the graphs is considered, along with the matchers, if provided.

        If both g1 and g2 are instances of IntGraph, the returned iterator will iterate over objects of IsomorphismIMapping.

        Specified by:
        isomorphicMappingsIter in interface IsomorphismTester
        Type Parameters:
        V1 - the type of vertices of the first graph
        E1 - the type of edges of the first graph
        V2 - the type of vertices of the second graph
        E2 - the type of edges of the second graph
        Parameters:
        g1 - the first graph. If sub graph isomorphism is searched, g1 is the smaller graph, namely the method search for a mapping from g1 to a sub graph of g2
        g2 - the second graph. If sub graph isomorphism is searched, g2 is the bigger graph, namely the method search for a mapping from g1 to a sub graph of g2
        induced - whether to search for an induced sub graph isomorphism or a sub graph isomorphism. See the interface documentation for more details
        vertexMatcher - a predicate that filters pairs of vertices, one from each graph, that are not allowed to be mapped to each other. For a given pair \(v_1,v_2\) where \(v_1 \in V_1\) and \(v_2 \in V_2\), if the matcher returns false, then the pair is not considered for mapping. If null, all pairs of vertices are allowed.
        edgeMatcher - a predicate that filters pairs of edges, one from each graph, that are not allowed to be mapped to each other. For a given pair \(e_1,e_2\) where \(e_1 \in E_1\) and \(e_2 \in E_2\), if the matcher returns false, then the pair is not considered for mapping. If null, all pairs of edges are allowed.
        Returns:
        an iterator over all the (optionally induced) sub graph isomorphism mappings between the two graphs. The returned mappings maps vertices and edges from the first graph to vertices and edges of the second graph. The inverse mapping can be obtained by calling IsomorphismMapping.inverse().