Module org.jgrapht.core
Package org.jgrapht.alg.isomorphism

Class IsomorphicGraphMapping<V,E>

java.lang.Object
org.jgrapht.alg.isomorphism.IsomorphicGraphMapping<V,E>
Type Parameters:
V - the type of the vertices
E - the type of the edges
All Implemented Interfaces:
GraphMapping<V,E>
public class IsomorphicGraphMapping<V,E> extends Object implements GraphMapping<V,E>
This class represents a GraphMapping between two (subgraph)isomorphic graphs. In the subgraph isomorphic case, the second one is assumed to be a subgraph of the first one.
Author:
Fabian Späh, Alexandru Valeanu

  • Field Details

  • Constructor Details

    • IsomorphicGraphMapping

      public IsomorphicGraphMapping(org.jgrapht.alg.isomorphism.GraphOrdering<V,E> g1, org.jgrapht.alg.isomorphism.GraphOrdering<V,E> g2, int[] core1, int[] core2)
      Construct a new isomorphic graph mapping
      Parameters:
      g1 - the first graph
      g2 - the second graph which is a possible subgraph of g1
      core1 - the mapping as array (forwards)
      core2 - the mapping as array (backwards)

    • IsomorphicGraphMapping

      public IsomorphicGraphMapping(Map<V,V> forwardMapping, Map<V,V> backwardMapping, Graph<V,E> graph1, Graph<V,E> graph2)
      Construct a new isomorphic graph mapping.
      Parameters:
      forwardMapping - the mapping from graph1 to graph2
      backwardMapping - the mapping from graph2 to graph1 (inverse of forwardMapping)
      graph1 - the first graph
      graph2 - the second graph

  • Method Details

    • getVertexCorrespondence

      public V getVertexCorrespondence(V v, boolean forward)
      Description copied from interface: GraphMapping
      Gets the mapped value where the key is vertex
      Specified by:
      getVertexCorrespondence in interface GraphMapping<V,E>
      Parameters:
      v - vertex in one of the graphs
      forward - if true, uses mapping from graph1 to graph2; if false, use mapping from graph2 to graph1
      Returns:
      corresponding vertex in other graph, or null if none

    • getEdgeCorrespondence

      public E getEdgeCorrespondence(E e, boolean forward)
      Description copied from interface: GraphMapping
      Gets the mapped value where the key is edge
      Specified by:
      getEdgeCorrespondence in interface GraphMapping<V,E>
      Parameters:
      e - edge in one of the graphs
      forward - if true, uses mapping from graph1 to graph2; if false, use mapping from graph2 to graph1
      Returns:
      corresponding edge in other graph, or null if none

    • getForwardMapping

      public Map<V,V> getForwardMapping()
      Get an unmodifiable version of the forward mapping function.
      Returns:
      the unmodifiable forward mapping function

    • getBackwardMapping

      public Map<V,V> getBackwardMapping()
      Get an unmodifiable version of the backward mapping function.
      Returns:
      the unmodifiable backward mapping function

    • getMappingDomain

      public Set<V> getMappingDomain()
      Get the active domain of the isomorphism.
      Returns:
      the set of vertices $v$ for which the mapping is defined

    • getMappingRange

      public Set<V> getMappingRange()
      Get the range of the isomorphism.
      Returns:
      the set of vertices $v$ for which a preimage exists

    • hasVertexCorrespondence

      public boolean hasVertexCorrespondence(V v)
      Checks if a vertex $v$ from the first graph has a corresponding vertex in the second graph
      Parameters:
      v - the vertex
      Returns:
      is there a corresponding vertex to $v$ in the subgraph

    • hasEdgeCorrespondence

      public boolean hasEdgeCorrespondence(E e)
      Checks if a edge e from the first graph has a corresponding edge in the second graph
      Parameters:
      e - the edge
      Returns:
      is there a corresponding edge to $e$ in the subgraph

    • equals

      public boolean equals(Object o)
      Overrides:
      equals in class Object

    • hashCode

      public int hashCode()
      Overrides:
      hashCode in class Object

    • toString

      public String toString()
      Overrides:
      toString in class Object

    • isValidIsomorphism

      public boolean isValidIsomorphism()
      Determines whether this mapping is indeed a valid isomorphic mapping between the first graph and the second graph. Note that this method will return false for a homomorphism returned by a subgraph isomorphism inspector unless the resulting mapping happens to be bijective as well (mapping all of the vertices and edges from the first graph to the second graph and vice versa).
      Returns:
      true iff this mapping is a valid isomorphism between the two graphs

    • isEqualMapping

      public boolean isEqualMapping(GraphMapping<V,E> rel)
      Checks for equality. Assuming both are mappings on the same graphs.
      Parameters:
      rel - the corresponding mapping
      Returns:
      do both relations map to the same vertices

    • compose

      public IsomorphicGraphMapping<V,E> compose(IsomorphicGraphMapping<V,E> otherMapping)
      Computes the composition of two isomorphisms. Let $f : V_{G_1} \rightarrow V_{G_2}$ be an isomorphism from $V_{G_1}$ to $V_{G_2}$ and $g : V_{G_2} \rightarrow V_{G_3}$ one from $V_{G_2}$ to $V_{G_3}$. This method computes an isomorphism $h : V_{G_1} \rightarrow V_{G_3}$ from $V_{G_1}$ to $V_{G_3}$. Note: The composition $g ∘ f$ can be built only if $f$'s codomain equals $g$'s domain; this implementation only requires that the former is a subset of the latter.
      Parameters:
      otherMapping - the other isomorphism (i.e. function $g$)
      Returns:
      the composition of the two isomorphism

    • identity

      public static <V, E> IsomorphicGraphMapping<V,E> identity(Graph<V,E> graph)
      Computes an identity automorphism (i.e. a self-mapping of a graph in which each vertex also maps to itself).
      Type Parameters:
      V - the graph vertex type
      E - the graph edge type
      Parameters:
      graph - the input graph
      Returns:
      a mapping from graph to graph