4.1.8.6. dg/VertexMapper

class mod.DGVertexMapper

A class for enumerating vertex maps for a given DG.HyperEdge.

For the given hyperedge, collect the graphs associated with respectively the source and target vertices, and create the disjoint union of those graphs. Let the result be the graphs \(G\) and \(H\), available via DGVertexMapper.left and DGVertexMapper.right respectively. Then each rule \(p = (L\leftarrow K\rightarrow R)\) associated with the hyperedge, generate direct derivations \(\require{mathtools} G\xRightarrow{p, m} H'\). An isomorphism \(H'\rightarrow H\) is then found to ensure we have generated the correct product. Each result can be described in the following commutative diagram.

Figure made with TikZ

A diagram describing each result generated by the vertex mapper. A consists of a double-pushout diagram for a direct derivation \(G\xRightarrow{p, m} H'\) and an isomorphism \(H'\rightarrow H\).

Each result is available in the form of three vertex maps:

  • Result::map (\(V(G) \rightarrow V(H)\)): the vertex map of the derivation, which maps vertices of the input graph \(G\) to the product graph \(H\). The map is defined as the composition \(b\circ h\circ g^{-1}\). Note that if the rule \(p\) either creates or removes vertices, then the map is partial. As all morphisms are injective, the vertex map is as well.

  • Result::match (\(m\colon L\rightarrow G\)): the match morphism.

  • Result::comatch (\(m'\colon L\rightarrow H\)): the comatch morphism. It is defined as the composition \(b\circ a\).

The vertex mapper can be configured in two ways via the constructor:

  • upToIsomorphismGDH: this controls which spans \(G\leftarrow D\rightarrow H'\) and match morphisms \(m\colon L\rightarrow G\) are enumerated. When set true only a single representative of the span is generated per isomorphism class.

  • rightLimit: this controls the amount of isomorphisms \(b\colon H'\rightarrow H\) are generated.

For example:

  • If you just want a single result, then use upToIsomorphismGDH = True and rightLimit = 1.

  • If you want all different vertex maps \(V(G)\rightarrow V(H)\), then use upToIsomorphismGDH = True and rightLimit set to some arbitrary high value, e.g., \(2^{30}\).

  • If you are interested in all the different ways the rule can be matched to generate this direct derivation, but do not care about the specific vertex map \(V(G)\rightarrow V(H)\), then use upToIsomorphismGDH = False and rightLimit = 1.

  • And finally, if you want all possible results, then use upToIsomorphismGDH = False and set rightLimit to some high value, e.g., \(2^{30}\).

__init__(e, upToIsomorphismGDH=True, rightLimit=2**30)

Construct a vertex map holder, and immediately calculate vertex maps for the derivations underlying the given hyperedge.

Parameters:

  • e (DG.HyperEdge) – the hyperedge to construct vertex maps for.

  • upToIsomorphismGDH (bool) – whether to only enumerate spans \(G \leftarrow D\rightarrow H'\) up to isomorphism, all \(m\), or just those such that all bottom spans \((G\leftarrow D\rightarrow H)\) up to isomorphism are generated. Defaults to True.

  • rightLimit (int) – after bottom span generation, find this many isomorphisms back to the targets of the hyperedge.

Raises:

LogicError if not e.

edge

(Read-only) The hyperedge to calculate vertex maps for.

Type:

DG.HyperEdge

left
right
Returns:

the disjoint union of graphs from respectively the source and target vertices of the hyperedge. That is, the graphs \(G\) and \(H\).

Type:

UnionGraph

__iter__()
Returns:

an iterator over the vertex maps, see __getitem__() for the specific type.

size

(Read-only) The number of vertex maps calculated.

Type:

int

__len__()
Returns:

size

Return type:

int

__getitem__(i)
Parameters:

i (int) – the index of the map to retrieve.

Returns:

the ith vertex map.

Return type:

Result

Raises:

LogicError if i is out of range.

class DGVertexMapper.Result

The value type returned for each result.

rule

The rule used to generate the map.

Type:

Rule

map

The vertex map \(V(G) \rightarrow V(H)\).

Type:

VertexMapUnionGraphUnionGraph

match

The vertex map \(V(L) \rightarrow V(G)\).

Type:

VertexMapRuleLeftGraphUnionGraph

comatch

The vertex map \(V(R) \rightarrow V(H)\).

Type:

VertexMapRuleRightGraphUnionGraph