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 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 Summary

Fields
Modifier and Type Field and Description
static int NULL_NODE
• ### Constructor Summary

Constructors
Constructor and Description
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
IsomorphicGraphMapping(Map<V,V> forwardMapping, Map<V,V> backwardMapping, Graph<V,E> graph1, Graph<V,E> graph2)
Construct a new isomorphic graph mapping.
• ### Method Summary

All Methods
Modifier and Type Method and Description
IsomorphicGraphMapping<V,E> compose(IsomorphicGraphMapping<V,E> otherMapping)
Computes the composition of two isomorphisms.
boolean equals(Object o)
Map<V,V> getBackwardMapping()
Get an unmodifiable version of the backward mapping function.
E getEdgeCorrespondence(E e, boolean forward)
Gets the mapped value where the key is edge
Map<V,V> getForwardMapping()
Get an unmodifiable version of the forward mapping function.
Set<V> getMappingDomain()
Get the active domain of the isomorphism.
Set<V> getMappingRange()
Get the range of the isomorphism.
V getVertexCorrespondence(V v, boolean forward)
Gets the mapped value where the key is vertex
boolean hasEdgeCorrespondence(E e)
Checks if a edge e from the first graph has a corresponding edge in the second graph
int hashCode()
boolean hasVertexCorrespondence(V v)
Checks if a vertex $v$ from the first graph has a corresponding vertex in the second graph
static <V,E> IsomorphicGraphMapping<V,E> identity(Graph<V,E> graph)
Computes an identity automorphism (i.e.
boolean isEqualMapping(GraphMapping<V,E> rel)
Checks for equality.
boolean isValidIsomorphism()
Determines whether this mapping is indeed a valid isomorphic mapping between the first graph and the second graph.
String toString()
• ### Methods inherited from class java.lang.Object

clone, finalize, getClass, notify, notifyAll, wait, wait, wait
• ### Field Detail

• #### NULL_NODE

public static final int NULL_NODE
Constant Field Values
• ### 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(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 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 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