3.2.11.7. dg/VertexMapper.hpp

3.2.11.7.1. Class dg::VertexMapper

class dg::VertexMapper

A class for enumerating vertex maps for a given dg::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 getLeft() and getRight() 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}\).

3.2.11.7.1.1. Synopsis

using Map = VertexMap<graph::Union, graph::Union>
using Match = VertexMap<rule::Rule::LeftGraph, graph::Union>
using Comatch = VertexMap<rule::Rule::RightGraph, graph::Union>
class Result
class iterator
using const_iterator = iterator
VertexMapper(DG::HyperEdge e)
VertexMapper(DG::HyperEdge e, bool upToIsomorphismGDH, int rightLimit, int verbosity)
DG::HyperEdge getEdge() const
graph::Union getLeft() const
graph::Union getRight() const
const_iterator begin() const
const_iterator end() const
std::size_t size() const
Result operator[](std::size_t i) const

3.2.11.7.1.2. Details

using Map = VertexMap<graph::Union, graph::Union>

The type of the vertex map \(V(G) \rightarrow V(H)\).

using Match = VertexMap<rule::Rule::LeftGraph, graph::Union>

The type of the vertex map \(V(L) \rightarrow V(G)\), i.e., the match morphism \(m\).

using Comatch = VertexMap<rule::Rule::RightGraph, graph::Union>

The type of the vertex map \(V(R) \rightarrow V(H)\), i.e., the co-match morphism \(m'\).

class Result

The value type returned for each result.

std::shared_ptr<rule::Rule> r

The rule used to generate the result.

Map map

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

Match match

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

Comatch comatch

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

class iterator

A random-access iterator over Results.

using const_iterator = iterator
VertexMapper(DG::HyperEdge e)
VertexMapper(DG::HyperEdge e, bool upToIsomorphismGDH, int rightLimit, int verbosity)

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

Parameters:

  • e – the hyperedge to construct vertex maps for.

  • upToIsomorphismGDH – 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 – after bottom span generation, find this many isomorphisms back to the targets of the hyperedge. Defaults to \(2^{30}\).

  • verbosity –

    the level of debug information to print. Defaults to 0.

    • 0 (or less): print no information.

    • 1: print debug information within the vertex mapping, but not debug information related to rule composition.

    • 10: also print information for morphism generation for rule composition.

    • 20: also print rule composition information.

Throws:

LogicError if !e.

DG::HyperEdge getEdge() const
Returns:

the hyperedge for which the mapper calculates vertex maps.

graph::Union getLeft() const
graph::Union getRight() const
Returns:

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

const_iterator begin() const
const_iterator end() const
Returns:

iterators for the range of vertex maps calculated by the mapper.

std::size_t size() const
Returns:

end() - begin()

Result operator[](std::size_t i) const
Returns:

begin()[i]

Throws:

LogicError if i >= size().