Package org.jgrapht.alg.isomorphism

Class 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 java.lang.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

    • Constructor Detail

      • 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​(java.util.Map<V,​V> forwardMapping,
                              java.util.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 Detail

      • 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 java.util.Map<V,​V> getForwardMapping()
        Get an unmodifiable version of the forward mapping function.
        Returns:
        the unmodifiable forward mapping function

      • getBackwardMapping

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

      • getMappingDomain

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

      • getMappingRange

        public java.util.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​(java.lang.Object o)
        Overrides:
        equals in class java.lang.Object

      • hashCode

        public int hashCode()
        Overrides:
        hashCode in class java.lang.Object

      • toString

        public java.lang.String toString()
        Overrides:
        toString in class java.lang.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