13. Groups and tracing

Groups are a means to control certain execution aspects of propagators and branchers. Tracing can be used for tracing constraint propagation on variables as well as the general execution of propagators and branchers. Groups are ultimately linked to tracing, as the generated traces can be filtered according to group membership.

Overview. Propagator groups explains groups of propagators, whereas Brancher groups explains groups of branchers. Tracing variables is explained in Variable tracing and general tracing in General tracing. Programming variable tracers shows how variable tracers and Programming general tracers shows how general tracers (the objects that process trace information) can be programmed.

13.1. Propagator groups

Each propagator belongs to exactly one propagator group of type PropagatorGroup. When a propagator is created, it is added to a group. Group membership of a propagator remains stable during copying of spaces. For propagators posted with local information under Space::NoGPI, later group changes affect only that space. See Scoped control of propagator information for scoped control of propagator information.

Adding propagators to groups. The following code creates a propagator group pg:

PropagatorGroup pg;

A propagator can be added to the group pg by passing the group as additional information adjoined to the home information when the propagator is posted. For example, when assuming that home refers to a space of type Space&, then

distinct(home(pg), x);

adds all propagators created by the constraint post function distinct() to the propagator group pg. Equivalently, one can also use:

distinct(pg(home), x);

If no propagator group is specified when a propagator is created, then the propagator is added to the default propagator group PropagatorGroup::def.

Moving propagators between groups. Propagators can be moved from one group to another. For example, if pga and pgb are propagator groups, then

pga.move(home,pgb);

moves all propagators from group pgb into group pga. An individual propagator p (of type Propagator&) can also be moved into a propagator group pg by

pg.move(home,p);

A propagator p can also be moved by giving its identity p.id(). For example, the following is equivalent to the previous example:

unsigned int id = p.id();
pg.move(home,id);

If no propagator with a given id exists, an exception of type UnknownPropagator is thrown.

In order to remove a propagator from its group or all propagators of a group from their group, one can use the default group. For example, if pg is a propagator group, all of its propagators are removed from pg by

PropagatorGroup::def.move(home,pg);

Move operations can be concatenated as they return their group. For example, if pg is a propagator group and p and q are two propagators, then

pg.move(p).move(q);

moves both p and q to pg.

Operations on propagator groups. The number of propagators in a group can be computed by the size() member function. The following expression:

pg.size(home)

evaluates to the number of propagators in the group pg. Each group has a unique identifier of type unsigned int which can be accessed by:

pg.id()

One can iterate over all propagators in a group. For example,

for (Propagators p(home,pg); p() ++p)
  std::cout << p.propagator.id() << ' ' << std::endl;

prints the unique identifier of each propagator contained in group pg. A propagator also provides access to the group it belongs to, assume that p is of type Propagator&, then

p.group()

evaluates to the group p belongs to.

The propagators of a group can be disabled and enabled. By

pg.disable(home);

all propagators in pg are disabled in that they are not any longer performing any propagation (for more details on disabling and enabling propagators, see also Disabling and re-enabling propagators.). Similarly, propagators can be enabled by

pg.enable(home);

By default, enabling a disabled propagator will schedule the propagator for execution if necessary. Hence, next time the status() function of the propagator’s home space is executed, the propagator will be executed again. It is also possible to enable propagators in a group without scheduling them by:

pg.enable(home,false);

All propagators in a group can be killed by

pg.kill(home);

Groups for all propagators. For convenience, there is one special propagator group PropagatorGroup::all which refers to all propagators in a space (one can think of it as the union of all propagator groups). For example,

PropagatorGroup::all.size(home)

evaluates to the number of all propagators in the space home.

13.2. Brancher groups

Brancher groups contain branchers and each brancher belongs to exactly one brancher group of type BrancherGroup. Brancher groups are similar to propagator groups as described in the previous section:

  • A brancher group bg is created as follows:

    BrancherGroup bg;
    
  • A brancher is added to the group bg by passing the group as additional information adjoined to the home information when the propagator is posted. For example, the brancher created by

    branch(home(bg), x, INT_VAR_NONE(), INT_VAL_MIN());
    

    adds the newly created brancher created to the brancher group bg. Equivalently, one can also write bg(home) instead of home(bg).

  • Brancher groups provide move() functions for moving branchers into brancher groups that are analogous to the move() functions for propagator groups.

  • If no brancher group is specified, branchers are added to the default group BrancherGroup::def.

  • The number of branchers in a group can be computed by the size() member function. Each group has a unique identifier of type unsigned int which can be accessed by bg.id().

  • One can iterate over all branchers in a group by using the iterator class Branchers.

  • Each brancher provides access to the group it belongs to, assume that b is of type Brancher&, then

    b.group()
    

    evaluates to the group b belongs to.

  • All branchers in a group can be killed by

    bg.kill(home);
    
  • There is one special brancher group BrancherGroup::all which refers to all branchers in a space.

13.3. Variable tracing

Gecode offers support to trace constraint propagation on an array of variables. Variable tracing distinguishes two components: a variable trace recorder that records information about relevant events during constraint propagation and a variable tracer that processes the recorded trace information. A very simple variable tracer instance would just print some textual information about recorded trace events. In fact, Gecode offers default tracers for each variable type that comes with Gecode that just print to an output stream of type std::ostream.

13.3.1. Creating a variable trace recorder

A variable trace recorder can be created by calling the overloaded function trace() together with an array of variables. For example,

trace(home, x);

creates a variable trace recorder for an array of variables x. Here, x can be an array of integer, Boolean, set, or float variables.

The variable trace recorder records the following events:

  • A single init-event providing some information about the variables for which the variable trace recorder will record information.

  • Each time the domain of a variable changes, a prune-event is recorded. The variable trace recorder provides information about which variable has been changed, how the variable has been changed, and on behalf of which entity (a propagator, a brancher, or a constraint post function performing pruning outside a propagator or brancher) the variable has been changed.

  • A fixpoint-event is recorded when the space containing the variable trace recorder reaches a fixpoint, triggered by the execution of the space’s status() function.

  • A failure-event is recorded when the space containing the variable trace recorder fails, triggered by the execution of the space’s status() function.

  • A done-event that is recorded when all of the variable trace recorder’s variables have been assigned and hence no further recording is needed. Note that this event can occur only once per space, however when using tracing during search the event might occur several times for different spaces.

The information that is recorded for each event depends on the variable trace recorder’s variable type.

13.3.2. Default variable tracers

The following paragraphs explain the information printed by the default variable tracer for a given variable type.

Integer and Boolean variables.

Program 13.1 Abridged output for variable tracing Send More Money
SEND+MORE=MONEY
trace<Int>::init(id:0) slack: 100.00% (72 values)
trace<Int>::prune(id:0): [0] = [1..9] - {0} by post()
trace<Int>::prune(id:0): [4] = [1..9] - {0} by post()
trace<Int>::prune(id:0): [0] = 9 - {1..8} by propagator(id:2)
  ...
trace<Int>::fix(id:0) slack: 33.33% - 66.67%
  ...
trace<Int>::done(id:0) slack: 0%
        {9, 5, 6, 7, 1, 0, 8, 2}
trace<Int>::prune(id:0): [1] = [6..7] - {5} by brancher(id:1)
  ...

Running the SEND+MORE=MONEY puzzle (see Getting started and Getting comfortable for the Send More Money problem) with the commandline option -trace all (trace events to be recorded can be specified on the command line, see Commandline options), the default variable tracer for integer variables prints information about all trace events to std::cerr. An excerpt of the information printed is shown in Program 13.1 where the variable trace recorder has been posted with

trace(home, le);

where le is the array of eight variables used in Send More Money.

The output for each event starts with the information

trace<Int>::

signaling that integer variables are being traced. After that, the type of event is shown (init, prune, fix for fixpoint, fail for failure, or done). This is followed by information about the identifier of the variable trace recorder (a variable trace recorder is in fact a propagator and hence has a unique identifier, see Enabling and disabling variable trace recorders). If the variable trace recorder belongs to a propagator group different from the default propagator group, also the identifier of the respective propagator group is printed.

The information for each event type is as follows:

  • For an init-event, the total slack of all variables is shown where the slack of a variable is the number of values that must be removed before the variable becomes assigned to a single value. This information serves as a measure of how much propagation is still to be done.

  • For a prune-event, it is printed which variable has been pruned where the variable is identified by its position in the variable array of the variable trace recorder (for example, the first prune event in Program 13.1 shows [0] as the variable at position 0 has been pruned).

    Next, the current domain of the variable is printed (that is, [1..9]) and that the value 0 has been pruned (that is, - {0}).

    This is followed by information which entity has pruned the variable: a constraint post function (as is the case for the first two prune-events in Program 13.1), a propagator (as is the case for the third prune-event in Program 13.1), a brancher (as is the case for the last prune-event in Program 13.1), or unknown. In case the prune-event has been caused by a propagator or brancher, their identifiers are shown. In case the propagator or brancher belong to a group different from the respective default group, also the group’s identifier is shown. This is also true if the event has been caused by a constraint post function where some group information had been passed to the constraint post function.

  • For a fixpoint-event, the current slack and its change since the last fixpoint are shown.

  • For a failure-event, the current slack and its change since the last fixpoint are shown.

  • For a done-event, the current slack is shown (unsurprisingly, the slack is \(0\%\) as all variables have been assigned).

The information printed by the default variable tracer for Boolean variables is exactly the same as for integer variables.

Defining custom variable tracers is straightforward, this is explained in Programming variable tracers.

Set variables. The information printed for init-, fixpoint-, failure-, and done-events for set variables is analogous to the information for integer variables. The slack of a set variable here is defined as the number of values that can be still included in or excluded from the set variable (that is, it corresponds to x.unknownSize() where x is a set variable of type SetVar).

For a prune-event, it is shown which values have been included in the set and which values have been excluded from the set. For example in

trace<Set>::prune(id:0): [0] = {1..6} + {6..6} - {} by brancher(id:1)

the value 6 has been included into the variable and no value has been excluded whereas in

trace<Set>::prune(id:0): [1] = {1..3} + {} - {4..6} by propagator(id:1)

the values 4, 5, and 6 have been excluded. You can try the Generating Hamming codes example that supports tracing.

Float variables. For float variables, the slack is defined as the width of the variable domain. The information printed for the events is analogous to the information for integer variables, where for a prune-event the interval containing the pruned values is printed.

For an example that supports tracing for float variables, you might want to try the Folium of Descartes example.

13.3.3. Using trace filters

The amount of prune-events that are generated during tracing can be prohibitive and often one is only interested in events generated by a subset of the propagators, branchers, or post functions. Therefore, one can pass as an optional argument a trace filter of type TraceFilter defined by a trace filter expression (or TFE) of type TFE to a trace recorder.

Assume that pga and pgb are two propagator groups and bg is a brancher group. Then

trace(home, x, pga);

traces only prune-events that have been caused by a propagator or a post function associated with the group pga. Prune-events caused by propagators or post functions from groups pga and pgb are traced by

trace(home, x, pga+pgb);

Likewise, prune-events caused by branchers in the group bg or by propagators or post functions not associated with pga are traced by

trace(home, x, bg-pga);

The following only traces post functions associated with pga and propagators included in pgb:

trace(home, x, post(pga)+propagator(pgb));

In summary, TFEs can be constructed from the unary and binary operators + and - and the functions post() and propagator() taking a propagator group as argument.

13.3.4. Selecting the events to trace

When creating a trace recorder, it can be defined which events should be recorded by providing an additional argument. For example

trace(home, x, TE_PRUNE);

only records prune-events, whereas

trace(home, x, TE_PRUNE | TE_FIX);

records prune- and fixpoint-events. All events (the default) are recorded by

trace(home, x,
      TE_INIT | TE_PRUNE | TE_FIX | TE_FAIL | TE_DONE);

13.3.5. Enabling and disabling variable trace recorders

A variable trace recorder is implemented by a propagator, hence it can be controlled by propagator groups. In particular, a variable trace recorder can be disabled and enabled.

For example, by creating a propagator group t by

PropagatorGroup t;

and then creating a variable trace recorder so that it belongs to the group t by

trace(home(t), x);

the variable trace recorder can be controlled through the group t.

For example, the variable trace recorder can be disabled by

t.disable(home);

and the later enabled by

t.enable(home);

One can easily add several variable trace recorders (either for different variables or different variable types) to the same propagator group and jointly control all variable trace recorders in that group.

13.4. General tracing

In addition to variable tracing, Gecode offers support to trace the execution of propagators and branchers. Like with variable tracing, general tracing distinguishes two components: a general trace recorder (or, trace recorder for short) that records information about relevant events during constraint propagation as well as branching, and a general tracer (or, tracer for short) that processes the recorded trace information.

13.4.1. Creating a general trace recorder

A trace recorder can be created by calling the overloaded function trace(). For example,

trace(home);

creates a trace recorder.

A general trace recorder records the following events:

  • Each time a constraint is posted, a post-event is recorded. The recorder provides information whether posting has lead to failure, the posted constraint is subsumed (that is, no propagator has been posted for the constraint), or one or several propagators have been created.

  • Each time a propagator is executed, a propagate-event is recorded. The recorder provides information about which propagator has been executed and what the status of the execution is (that is, whether the propagator computed a fixpoint, did not compute a fixpoint, became subsumed, or resulted in failure).

  • Each time a commit operation on a brancher is executed, a commit-event is recorded.

13.4.2. Default general tracers

The following paragraphs explain the information printed by the default general tracer.

Program 13.2 Abridged output for general tracing of Send More Money
SEND+MORE=MONEY
trace::post(s:posted(1))
trace::post(s:subsumed)
  ...
trace::propagate(id:2,s:fix)
  ...
trace::commit(id:1)
        var[1] = 4
trace::propagate(id:2,s:subsumed)
  ...
trace::propagate(id:1,s:failed)
  ...

Running the SEND+MORE=MONEY puzzle (see Getting started and Getting comfortable for the Send More Money problem) with the commandline option -trace propagate,commit (trace events to be recorded can be specified on the command line, see Commandline options), the default tracer prints information about all trace events to std::cerr. An excerpt of the information printed is shown in Program 13.2 where the trace recorder has been posted with

trace(home);

The output for each event starts with the information

trace::

After that, the type of event is shown (propagate, choice, or post).

The information for each event type is as follows:

  • For a propagate-event, the propagator identifier is printed, potentially followed by the propagator group. This is followed by status information.

  • For a choice-event, the brancher identifier is printed, potentially followed by the brancher group. This is followed by information which alternative the brancher has been committed to, see also Using variable-value print functions.

  • For a post-event, potentially the propagator group is printed. This is followed by status information.

Defining custom general tracers is straightforward, this is explained in Programming general tracers.

Additional features. Like for variable tracers, general tracers can also be controlled by trace filters (see Using trace filters) and can be disabled (see Enabling and disabling variable trace recorders).

When creating a trace recorder, it can be defined which events should be recorded by providing an additional argument. For example,

trace(home, TE_PROPAGATE);

only records propagate-events, whereas

trace(home, TE_CHOICE);

only records choice-events. All events (the default) are recorded by

trace(home, TE_POST | TE_PROPAGATE | TE_CHOICE);

13.5. Programming variable tracers

Programming variable tracers is straightforward and is done by inheriting from a class that depends on the variable type and implements one virtual member function for each trace event type. These virtual member functions are called when an event of that type is being recorded and the event type has been selected for tracing. For integer variables, the tracer class to inherit from is IntTracer, for Boolean variables BoolTracer, for set variables SetTracer, and for float variables FloatTracer.

In the following we are discussing variable tracers for integer and Boolean variables in some detail in Tracers for integer and Boolean variables and summarize variable tracers for set and float variables in Variable tracers for set variables and Variable tracers for float variables respectively.

13.5.1. Tracers for integer and Boolean variables

Program 13.3 An integer variable tracer printing to std::cout
...
class StdCoutIntTracer : public IntTracer {
protected:
  // [integer variable tracer:print propagator information]
  static void ids(const Brancher& b) {
    ...
  }
  // [integer variable tracer:print view trace information]
public:
  virtual void init(const Space& home, const IntTraceRecorder& t) {
    ...
  }
  // [integer variable tracer:prune event]
  // [integer variable tracer:fixpoint event]
  virtual void fail(const Space& home, const IntTraceRecorder& t) {
    ...
  }
  virtual void done(const Space& home, const IntTraceRecorder& t) {
    ...
  }
};

The example tracer we discuss is implemented by a class StdCoutIntTracer, prints trace information to std::cout, and is shown in Program 13.3. The init(), fail(), and done() member functions are not discussed as they are similar to the member function fix() which is discussed below.

Printing propagator information. The example tracer prints information about propagators and branchers using overloaded static member functions ids() (for identifiers). Printing information about propagators is implemented as follows:

  static void ids(const Propagator& p) {
    std::cout << "(id:" << p.id();
    if (p.group().in())
      std::cout << ",g:" << p.group().id();
    std::cout << ')';
  }

The function always prints the identifier p.id() of the propagator p. If p is in a propagator group p.group() which is different from the default propagator group (tested by the in() function of a propagator group), then also the group identifier is printed. The overloaded function ids() for branchers is identical and hence only shown in abbreviation in Program 13.3.

Printing variable trace information. The member function prune() receives as an argument a reference to an object of class ViewTraceInfo providing information about which entity triggered the corresponding prune-event. The following function illustrates the information provided by an object of class ViewTraceInfo.

  static void info(const ViewTraceInfo& vti) {
    switch (vti.what()) {
    case ViewTraceInfo::PROPAGATOR:
      std::cout << "propagator"; ids(vti.propagator());
      break;
    case ViewTraceInfo::BRANCHER:
      std::cout << "brancher"; ids(vti.brancher());
      break;
    case ViewTraceInfo::POST:
      std::cout << "post(";
      if (vti.post().in())
        std::cout << "g:" << vti.post().id();
      std::cout << ')';
      break;
    case ViewTraceInfo::OTHER:
      std::cout << '-';
      break;
    }
  }

Printing prune-events. A prune() member function takes arguments that provide information about what is being pruned (this is given by the integer i as the position of the variable in the array passed to the trace() function), how the variable has been pruned (this is given by the argument d of class IntTraceDelta), and by whom (this is given by the class ViewTraceInfo, which has been discussed in the previous paragraph). It also gets access to the trace recorder of type IntTraceRecorder.

The example prune() function prints information as follows:

  virtual void prune(const Space& home, const IntTraceRecorder& t,
                     const ViewTraceInfo& vti, int i, IntTraceDelta& d) {
    std::cout << "trace::prune"; ids(t);
    std::cout << ": [" << i << "] = " << t[i] << " - {";
    std::cout << d.min();
    if (d.width() > 1)
      std::cout << ".." << d.max();
    ++d;
    while (d()) {
      ...
    }
    std::cout << "} by "; info(vti);
    std::cout << std::endl;
  }

As can be seen, the argument d of type IntTraceDelta is a range iterator with the same interface as described in Iterating over integer variable domains and iterates of the integer ranges that correspond to the values that have been removed. The trace recorder t provides access to its variables through the array operator [].

Printing fixpoint-events. The fix() function also receives an argument of type IntTraceRecorder as shown here:

  virtual void fix(const Space& home, const IntTraceRecorder& t) {
    std::cout << "trace::fix"; ids(t);
    double sl_i = static_cast<double>(t.slack().initial());
    double sl_p = static_cast<double>(t.slack().previous());
    double sl_c = static_cast<double>(t.slack().current());
    ...
  }

The integer trace recorder t provides access to slack information about all of its variables through a slack() member function.

For integer variables, the slack is the number of values that still need to be pruned before all variables become assigned and is of type unsigned long long int. Here, the function initial() of t.slack() returns the initial slack when the trace recorder has been created, previous() returns the slack at the previous fixpoint (or, the initial slack if it is the first fixpoint), and current() returns the current slack.

Note that the slack information is only updated when a fixpoint-, init-, or done-event occurs.

Variable tracers for Boolean variables. Variable tracers for Boolean variables are exactly like variable tracers for integer variables: a Boolean variable trace recorder is of type BoolTraceRecorder, the trace delta is also a range iterator of class BoolTraceDelta, and the slack is defined as for integer variables and is also of type unsigned long long int.

Memory and concurrency properties of tracers. There is no automatic memory management for tracers, the user is responsible for creating and deleting tracers. A tracer can be used across several threads where it is ensured that the execution of a trace function is synchronized in that at most one thread executes any trace function at any given time.

13.5.2. Variable tracers for set variables

The types and classes for set variable tracers are as follows:

  • The variable trace recorder is of type SetTraceRecorder.

  • The trace delta information is of class SetTraceDelta which implements two member functions glb() (for greatest lower bound) and lub() (for least upper bound) which return range iterators. The function glb() returns a range iterator of class SetTraceDelta::Glb which iterates over the values that have been included into a set variable by a prune-event. The function lub() returns a range iterator of class SetTraceDelta::Lub which iterates over the values that have been excluded from a set variable by a prune-event.

  • The slack of a set variable is defined as the number of values where membership has not been decided and is of type unsigned long long int.

13.5.3. Variable tracers for float variables

The types and classes for float variable tracers are as follows:

  • The variable trace recorder is of type FloatTraceRecorder.

  • The trace delta information is of class FloatTraceDelta which implements two member functions min() and max() defining the interval of float values that have been pruned.

  • The slack of a float variable is defined as its width and is of type FloatNum.

13.6. Programming general tracers

Programming general tracers is straightforward and is done by inheriting from the class Tracer that implements one virtual member function for each trace event type. These virtual member functions are called when an event of that type is being recorded and the event type has been selected for tracing.

Program 13.4 A general tracer printing to std::cout
...
class StdCoutTracer : public Tracer {
public:
  virtual void post(const Space& home,
                    const PostTraceInfo& pti) {
    std::cout << "trace::" << pti << std::endl;
  }
  virtual void propagate(const Space& home,
                         const PropagateTraceInfo& pti) {
    std::cout << "trace::" << pti << std::endl;
  }
  virtual void commit(const Space& home,
                      const CommitTraceInfo& cti) {
    std::cout << "trace::" << cti << std::endl
              << '\t';
    cti.brancher().print(home, cti.choice(), cti.alternative(),
                         std::cout);
    std::cout << std::endl;
  }
};

The example tracer we discuss is implemented by a class StdCoutTracer, prints trace information to std::cout, and is shown in Program 13.4.

The virtual member function commit() takes a space and an object cti of class CommitTraceInfo as input. Information about the brancher, the choice, and the alternative to commit to can be accessed through the member functions of cti.

The virtual member function post() takes a space and an object pti of class PostTraceInfo as input. Information about propagator group, status, and the number of posted propagators can be accessed through the member functions of pti.

The virtual member function propagate() takes a space and an object pti of class PropagateTraceInfo as input. Information about the propagator and the status of propagation can be accessed through the member functions of pti.