3.1.9.5. dg/Strategies

This section describes two interfaces for the derivation graph strategies; the basic API and an embedded language which is built on the basic API. Usually the embedded strategy language is easiest and sufficient for constructing strategies.

The semantics of the individual strategies are described in Derivation Graph Strategies. Note that a DGStrat is a representation of a strategy and must be given to a derivation graph to be evaluated.

3.1.9.5.1. The Embedded Strategy Language

The strategy language is really a collection of proxy classes with a lot of operator overloading, thus the normal syntax and semantics of Python applies.

The following is the grammar for the strategies.

strat ::=  strats
           strat ">>" strat
           rule
           "addSubset(" graphs ")"
           "addUniverse(" graphs ")"
           "execute(" executeFunc ")"
           "filterSubset(" filterPred ")"
           "filterUniverse(" filterPred ")"
           "leftPredicate[" derivationPred "](" strat ")"
           "rightPredicate[" derivationPred "](" strat ")"
           "repeat" [ "[" int "]" ] "(" strat ")"
           "revive(" strat ")"

A strats must be an iterable of strat, e.g., an iterable of Rule. A graphs can either be a single Graph, an iterable of graphs, or a function taking no arguments and returning a list of graphs.

The functions in the language have the following signatures.

mod.addSubset(g, *gs, graphPolicy=IsomorphismPolicy.Check)
mod.addUniverse(g, *gs, graphPolicy=IsomorphismPolicy.Check)

Depending on g it calls either DGStrat.makeAddStatic() or DGStrat.makeAddDynamic().

Parameters

  • g (Graph or Iterable[Graph] or Callable[[], Iterable[Graph]]) – graph(s) to add, or a callback to compute them.

  • gs (Graph or Iterable[Graph]) – a variable amount of additional arguments with graphs, unless g is a callback, then no additional arguments may be given.

  • graphPolicy (IsomorphismPolicy) – the policy to use when adding the graphs. When IsomorphismPolicy.Check is given, and a graph is added which is isomorphic to an existing graph in the internal database of the DG the strategy is executed on, then a LogicError is thrown.

mod.execute(f)
Returns

the result of DGStrat.makeExecute().

mod.filterSubset(p)
mod.filterUniverse(p)
Returns

the result of the corresponding DGStrat.makeFilter().

mod.leftPredicate
mod.rightPredicate

Objects of unspecified type which can be used as obj[pred](strat). This will call respectively DGStrat.makeLeftPredicate() or DGStrat.makeRightPredicate().

mod.repeat

An object of unspecified type which can be used either as repeat(strat) or repeat[limit](strat). This will call DGStrat.makeRepeat().

mod.revive(strat)
Returns

the result of DGStrat.makeRevive().

3.1.9.5.2. The Basic API

3.1.9.5.2.1. Class DGStratGraphState

class mod.DGStratGraphState

This class represents a graph state with a subset \(S\) and a universe \(U\) fulfilling \(S\subseteq U\).

subset

The subset \(\mathcal{S}\).

Type

list[Graph]

universe

The universe \(\mathcal{U}\).

Type

list[Graph]

3.1.9.5.2.2. Class DGStrat

class mod.DGStrat
static makeAddStatic(onlyUniverse, graphs, graphPolicy)
Parameters
Returns

an Add Universe strategy if onlyUniverse is True, otherwise an Add Subset strategy.

Return type

DGStrat

Raises

LogicError if there is a None in graphs.

static makeAddDynamic(onlyUniverse, graphsFunc, graphPolicy)
Parameters

  • onlyUniverse (bool) – if the strategy is Add Universe or Add Subset.

  • graphsFunc (Callable[[], list[Graph]]) – a function returning the graphs to be added by the strategy.

  • graphPolicy (IsomorphismPolicy) – refers to the checking of each added graph against the internal graph database.

Returns

an Add Universe strategy if onlyUniverse is True, otherwise an Add Subset strategy.

Return type

DGStrat

static makeSequence(strats)
Parameters

strats (list[DGStrat]) – the strategies to evaluate in sequence.

Retunrs

a Sequence strategy.

Return type

DGStrat

Raises

LogicError if the given list of strategies is empty.

Raises

LogicError if there is a None in strats.

static makeParallel(strats)
Parameters

strats (list[DGStrat]) – the sub-strategies to evaluate.

Returns

a Parallel strategy.

Return type

DGStrat

Raises

LogicError if strats is empty.

Raises

LogicError if there is a None in strats.

static makeFilter(alsoUniverse, p)
Parameters

  • alsoUniverse (bool) – if the strategy is Filter Universe or Filter Subset.

  • p (Callable[[Graph, DGStratGraphState, bool], bool]) – the filtering predicate being called for each graph in either the subset or the universe. The predicate is called with the graph and the graph state as arguments, and a bool stating whether or not the call is the first in the filtering process.

Returns

a Filter Universe strategy if onlyUniverse is True, otherwise a Filter Subset strategy.

Return type

DGStrat

static makeExecute(func)
Parameters

func (Callable[[DGStratGraphState], None]) – A function being executed when the strategy is evaluated.

Returns

an Execute strategy.

Return type

DGStrat

static makeRule(r)
Parameters

r (Rule) – the rule to make into a strategy.

Returns

a Rule strategy.

Return type

DGStrat

Raises

LogicError is r is None.

static makeLeftPredicate(p, strat)
Parameters

  • p (Callable[[Derivation], bool]) – the predicate to be called on each candidate derivation. Even though the predicate is called with a Derivation object, only the left side and the rule of the object is valid.

  • strat (DGStrat) – the sub-strategy to be evaluated under the constraints of the left predicate.

Returns

a Derivation Predicates strategy.

Return type

DGStrat

Raises

LogicError if strat is None.

static makeRightPredicate(p, strat)
Parameters

  • p (Callable[[Derivation], bool]) – the predicate to be called on each candidate derivation.

  • strat (DGStrat) – the sub-strategy to be evaluated under the constraints of the right predicate.

Returns

a Derivation Predicates strategy.

Return type

DGStrat

Raises

LogicError if strat is None.

static makeRevive(strat)
Parameters

strat (DGStrat) – the strategy to encapsulate.

Returns

a Revive strategy.

Return type

DGStrat

Raises

LogicError if strat is None.

static makeRepeat(limit, strat)
Parameters

  • limit (int) – the maximum number of iterations.

  • strat (DGStrat) – the strategy to be repeated.

Returns

a Repeat strategy.

Return type

DGStrat

Raises

LogicError if limit is not positive.

Raises

LogicError if strat is None.