.. _cpp-dg/VertexMapper: ********************************************************** dg/VertexMapper.hpp ********************************************************** .. default-domain:: cpp .. default-role:: cpp:texpr .. py:currentmodule:: mod .. cpp:namespace:: mod Class ``dg::VertexMapper`` -------------------------------------------------------------------------------------------------------------------------------- .. class:: dg::VertexMapper A class for enumerating vertex maps for a given :class:`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 :math:`G` and :math:`H`, available via `getLeft()` and `getRight()` respectively. Then each rule :math:`p = (L\leftarrow K\rightarrow R)` associated with the hyperedge, generate direct derivations :math:`\require{mathtools} G\xRightarrow{p, m} H'`. An isomorphism :math:`H'\rightarrow H` is then found to ensure we have generated the correct product. Each result can be described in the following commutative diagram. .. tikz:: A diagram describing each result generated by the vertex mapper. A consists of a double-pushout diagram for a direct derivation :math:`G\xRightarrow{p, m} H'` and an isomorphism :math:`H'\rightarrow H`. \matrix[matrix of math nodes, row sep=4em, column sep=4em]{ |(L)| L \& |(K)| K \& |(R)| R \\ |(G)| G \& |(D)| D \& |(H')| H\smash{'} \& |(H)| H \\ }; \foreach \s/\t in {K/L, K/R, K/D} { \draw[->] (\s) to (\t); } \draw[->] (L) to node[auto] {$m$} (G); \draw[->] (D) to node[above] {$g\vphantom{h}$} (G); \draw[->] (D) to node[above] {$h\vphantom{g}$} (H'); \draw[->] (R) to node[auto] {$a$} (H'); \draw[->] (H') to node[auto] {$b$} (H); \draw[->] (R) to node[auto] {$m' = b\circ a$} (H); Each result is available in the form of three vertex maps: - `Result::map` (:math:`V(G) \rightarrow V(H)`): the vertex map of the derivation, which maps vertices of the input graph :math:`G` to the product graph :math:`H`. The map is defined as the composition :math:`b\circ h\circ g^{-1}`. Note that if the rule :math:`p` either creates or removes vertices, then the map is partial. As all morphisms are injective, the vertex map is as well. - `Result::match` (:math:`m\colon L\rightarrow G`): the match morphism. - `Result::comatch` (:math:`m'\colon L\rightarrow H`): the comatch morphism. It is defined as the composition :math:`b\circ a`. The vertex mapper can be configured in two ways via the constructor: - ``upToIsomorphismGDH``: this controls which spans :math:`G\leftarrow D\rightarrow H'` and match morphisms :math:`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 :math:`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 :math:`V(G)\rightarrow V(H)`, then use ``upToIsomorphismGDH = true`` and ``rightLimit`` set to some arbitrary high value, e.g., :math:`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 :math:`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., :math:`2^{30}`. Synopsis ^^^^^^^^ .. alias:: dg::VertexMapper :maxdepth: 2 :noroot: Details ^^^^^^^ .. cpp:namespace-push:: dg::VertexMapper .. type:: Map = VertexMap The type of the vertex map :math:`V(G) \rightarrow V(H)`. .. type:: Match = VertexMap The type of the vertex map :math:`V(L) \rightarrow V(G)`, i.e., the match morphism :math:`m`. .. type:: Comatch = VertexMap The type of the vertex map :math:`V(R) \rightarrow V(H)`, i.e., the co-match morphism :math:`m'`. .. class:: Result The value type returned for each result. .. var:: std::shared_ptr r The rule used to generate the result. .. var:: Map map The vertex map :math:`V(G) \rightarrow V(H)`. .. var:: Match match The vertex map :math:`V(L) \rightarrow V(G)`. .. var:: Comatch comatch The vertex map :math:`V(R) \rightarrow V(H)`. .. class:: iterator A random-access iterator over :type:`Result`\ s. .. type:: const_iterator = iterator .. function:: 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. :param e: the hyperedge to construct vertex maps for. :param upToIsomorphismGDH: whether to only enumerate spans :math:`G \leftarrow D\rightarrow H'` up to isomorphism, all :math:`m`, or just those such that all bottom spans :math:`(G\leftarrow D\rightarrow H)` up to isomorphism are generated. Defaults to `true`. :param rightLimit: after bottom span generation, find this many isomorphisms back to the targets of the hyperedge. Defaults to :math:`2^{30}`. :param 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: :class:`LogicError` if `!e`. .. function:: DG::HyperEdge getEdge() const :returns: the hyperedge for which the mapper calculates vertex maps. .. function:: 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 :math:`G` and :math:`H`. .. function:: const_iterator begin() const const_iterator end() const :returns: iterators for the range of vertex maps calculated by the mapper. .. function:: std::size_t size() const :returns: `end() - begin()` .. function:: Result operator[](std::size_t i) const :returns: `begin()[i]` :throws: :class:`LogicError` if `i >= size()`. .. cpp:namespace-pop::