Package com.jgalgo.alg.isomorphism

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:

  • Method Details

    • 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

    • inverse

      IsomorphismMapping<V2,E2,V1,E1> inverse()
      Get the inverse mapping.
      Returns:
      the inverse mapping

    • 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