Package com.jgalgo.alg

Interface IsomorphismMapping<V1,​E1,​V2,​E2>

  • 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
    All Known Subinterfaces:
    IsomorphismIMapping
    public interface IsomorphismMapping<V1,​E1,​V2,​E2>
    A mapping between two graphs that preserves the structure of the graphs.

    Given two graphs, an isomorphism is a mapping functions that maps the first graph vertices to the second graph vertices, while preserving the structure of the graph. There are few variants, described in the different types of isomorphism, see IsomorphismTester. Some types of isomorphism map only a subset of the vertices or edges, and in such case the mapping will return null for vertices or edges that are not mapped.

    Author:
    Barak Ugav
    See Also:
    IsomorphismTester, Wikipedia

    • Method Detail

      • mapVertex

        V2 mapVertex​(V1 vertex)
        Map a vertex from the first graph to a vertex of the second graph.
        Parameters:
        vertex - the vertex to map
        Returns:
        the mapped vertex, or null if v1 is not mapped
        Throws:
        NoSuchVertexException - if the vertex does not exist in the first graph

      • mapEdge

        E2 mapEdge​(E1 edge)
        Map an edge from the first graph to an edge of the second graph.
        Parameters:
        edge - the edge to map
        Returns:
        the mapped edge, or null if e1 is not mapped
        Throws:
        NoSuchEdgeException - if the edge does not exist in the first graph

      • sourceGraph

        Graph<V1,​E1> sourceGraph()
        Get the source graph.

        The 'source' graph contains the vertices and edges of the domain of the mapping, namely these vertices and edges are mapped to vertices and edges of the target (range) graph.

        Returns:
        the source graph

      • targetGraph

        Graph<V2,​E2> targetGraph()
        Get the target graph.

        The 'target' graph contains the vertices and edges of the range of the mapping, namely the vertices and edges of another graph (the source or domain graph) are mapped to these vertices and edges.

        Returns:
        the target graph

      • mappedVertices

        Set<V1> mappedVertices()
        Get the set of the vertices that are mapped out of all the vertices of the source graph.

        The mapping may not map all the vertices of the source graph, in case the first graph is smaller than the second graph, and a (maybe induced) sub graph isomorphism was searched. This method can be used to get the set of vertices for which there is a corresponding vertex in the target graph.

        Together with mappedEdges(), this method can be used to construct the subgraph mapped to the target graph: 

         
 Set<V1> vertices = mapping.mappedVertices();
 Set<E1> edges = mapping.mappedEdges();
 Graph<V1, E1> mappedSubGraph = mapping.sourceGraph().subGraphCopy(vertices, edges);
        Returns:
        the set of the mapped vertices

      • mappedEdges

        Set<E1> mappedEdges()
        Get the set of the edges that are mapped out of all the edges of the source graph.

        The mapping may not map all the edges of the source graph, in case the first graph is smaller than the second graph, and a (maybe induced) sub graph isomorphism was searched. This method can be used to get the set of edges for which there is a corresponding edge in the target graph.

        Together with mappedVertices(), this method can be used to construct the subgraph mapped to the target graph: 

         
 Set<V1> vertices = mapping.mappedVertices();
 Set<E1> edges = mapping.mappedEdges();
 Graph<V1, E1> mappedSubGraph = mapping.sourceGraph().subGraphCopy(vertices, edges);
        Returns:
        the set of the mapped edges