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

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

See Also:

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