9. Derivation Graph Strategies

The strategy framework is a domain specific programming language for specifying the application of transformation rules. It can therefore be used to perform computations with graphs and graph rewriting. During evaluation of a strategy the framework will remember each graph derivation performed, and store them as a directed multi-hypergraph, i.e., a derivation graph. When graphs model molecules and transformation rules model reaction patterns, then the resulting derivation graph can be seen as a chemical reaction network. Here we describe the semantics of the strategy language, while the API is described seperately for the C++ and Python interface.

9.1. Virtual Machine

The strategies are evaluated in a virtual machine. Its state is a pair \(F = (\mathcal{U}, \mathcal{S})\) of sets of graphs, where \(\mathcal{U}\) is called the universe. The set \(\mathcal{S}\) is a distinguished subset of the universe called the active subset. The machine additionally keeps track of a directed multi-hypergraph \(\mathcal{H} = (V, E)\), called a derivation graph. The vertices of \(\mathcal{H}\) each has an associated graph, while each hyperedge has an associated list of rules.

Initially the state is empty, i.e., \((\mathcal{U}, \mathcal{S}) = (\emptyset, \emptyset)\) and the derivation graph is the empty hypergraph.

9.2. Strategies

Each strategy is a function taking a graph state \(F = (\mathcal{U}, \mathcal{S})\) as input and returning a new state \(F' = (\mathcal{U}', \mathcal{S}')\). While the universe and active subset of a state are described as sets of graphs, they are implemented as lists of unique graphs. The result of most strategies do not depend on the order of the graphs and make no guarentees about the order in the results.

9.2.1. Add Universe

Given a single graph, a set of graphs, or a function returning a set of graphs, this strategy returns the graph state with the additional graphs added to the universe. That is, if \(\mathcal{G}\) is the set of graphs to be added, then the result is \((\mathcal{U}\cup \mathcal{G}, \mathcal{S})\).

9.2.2. Add Subset

This strategy is analogous to the previous strategy, except the graphs are added to both the universe and the active subset. That is, the result is \((\mathcal{U}\cup \mathcal{G}, \mathcal{S}\cup \mathcal{G})\).

9.2.3. Execute

The execute strategy is simply the identity function, but it can be used to execute arbitrary code at a given point during evalutation.

9.2.4. Filter Universe

This strategy can be used to remove graphs from the input state, using a given predicate. Assuming this predicate is \(p\), then the result is \(F' = (\mathcal{U}', \mathcal{S}')\), with \(\mathcal{U}' = \{g\in \mathcal{U}\mid p(g)\}\) and \(\mathcal{S}' = \{g\in \mathcal{S}\mid p(g)\}\).

9.2.5. Filter Subset

As the previous strategy this one also filters the input state, but only the active subset. The result is thus \(F' = (\mathcal{U}, \mathcal{S}')\), with \(\mathcal{S}' = \{g\in \mathcal{S}\mid p(g)\}\).

9.2.6. Rule

A rule (C++/Python) can be used directly as a strategy. It will search for proper derivations using a multiset of graphs drawn from the input unvierse. However, each candidate multiset will have at least one graph from the active subset. The active subset of the output will be comprised of the newly discovered graphs. That is, if \(D = \{G\Rightarrow^{p} H\mid G\subseteq \mathcal{U} \wedge G\cap \mathcal{S} \neq \emptyset\}\) is the set of all proper derivations using at least one graph from the active input subset, then the result is \(F' = (\mathcal{U}', \mathcal{S}')\) with \(\mathcal{S}' = \bigcup_{G\Rightarrow^{p} H\in D} H\backslash \mathcal{U}\), and \(\mathcal{U}' = \mathcal{U}\cup \mathcal{S}'\).

As a side-effect of evaluating a rule strategy the underlying derivation graph is augmented with vertices for every new graph discovered. The derivations in \(D\) is additionally added as directed multi-hyperedges in the graph.

9.2.7. Derivation Predicates

A derivation predicate strategy changes the execution environment for a given substrategy \(Q\). Whenever a derivation is discovered during the evaluation of \(Q\) a predicate \(p\) will be consulted before the derivation is finally accepted. There are two flavours of the derivation predicate strategy: left predicate and right predicate. The difference between them is that only the left-hand side of a potential derivation and the rule is available in the left predicate, while the whole derivation is available in the right predicate. Left predicatates are thus not strictly necessary, but can potentially be slightly more efficient than right predicates.

9.2.8. Parallel

A parallel strategy aggregates a set of substrategies \(\{Q_1, Q_2, \dots, Q_n\}\) and evaluates them on the same input state. This evaluation produces a set of output states \(\{F_1', F_2', \dots, F_n'\}\), and the final result is the union of those states: \(\mathcal{U}' = \bigcup_{1\leq i\leq n} \mathcal{U}_i'\), \(\mathcal{S}' = \bigcup_{1\leq i\leq n} \mathcal{S}_i'\).

9.2.9. Sequence

Given two substrategies \(Q_1\) and \(Q_2\), the sequence strategy evaluates the composition of the strategies, i.e., with the input state \(F\) the output is \(Q_2(Q_1(F))\).

9.2.10. Repeat

The repetition strategy acts as a loop that evaluates a given substrategy \(Q\) in sequence with it self a certain number of times. Let \(Q^k(F)\) be the \(k\)-fold composition of the strategy \(Q\) on the input state \(F\). Notably, for \(k = 0\) we have the identity function. Given a constant \(n\geq 0\), the repeatition strategy on \(Q\) results in \(F' = Q`k(F)\), where \(k = min\{0, 1, \dots, n\}\) such that either \(k = n\), or \(Q^{k+1}(F) = Q^{k}(F)\), or \(Q^{k+1}(F) = (\emptyset, \overline{\mathcal{U}})\) for an abitrary universe \(\overline{\mathcal{U}}\).

9.2.11. Revive

A revive strategy is manipulating the output of an inner strategy \(Q\), depending on which derivations are discovered by \(Q\). Let \(F = (\mathcal{U}, \mathcal{S})\) be the input state and \(\overline{F} = (\overline{\mathcal{U}}, \overline{\mathcal{S}}) = Q(F)\). Further, let \(D\) be the set of derivations discovered (and accepted by the predicates) in the evaluation of \(Q(F)\). We then define the set of consumed graphs as those being on the right side on any derivation in \(D\): \(C = \bigcup_{G\Rightarrow H \in D} G\). As output of the revive strategy we do not modify the universe, i.e., \(\mathcal{U}' = \overline{\mathcal{U}}\). The output subset is however extended by non-consumed graphs that were in the input subset: \(\mathcal{S}' = \overline{\mathcal{S}}\cup \mathcal{S}\backslash C\).