Gecode::Search::Seq::Path< Tracer > Class Template Reference

Depth-first path (stack of edges) supporting recomputation. More...

`#include <path.hh>`

## Classes

class | Edge
| Search tree edge for recomputation More...

## Public Types

typedef Tracer::ID | ID
| Node identity type.

## Public Member Functions

| Path (unsigned int l)
| Initialize with no-good depth limit l.
unsigned int | ngdl (void) const
| Return no-good depth limit.
void | ngdl (unsigned int l)
| Set no-good depth limit to l.
const Choice * | push (Worker &stat, Space *s, Space *c, unsigned int nid)
| Push space c (a clone of s or NULL).
void | next (void)
| Generate path for next node.
Edge & | top (void) const
| Provide access to topmost edge.
bool | empty (void) const
| Test whether path is empty.
int | lc (void) const
| Return position on stack of last copy.
void | unwind (int l, Tracer &t)
| Unwind the stack up to position l (after failure).
void | commit (Space *s, int i) const
| Commit space s as described by stack entry at position i.
Space * | recompute (unsigned int &d, unsigned int a_d, Worker &s, Tracer &t)
| Recompute space according to path.
Space * | recompute (unsigned int &d, unsigned int a_d, Worker &s, const Space &best, int &mark, Tracer &t)
| Recompute space according to path.
int | entries (void) const
| Return number of entries on stack.
void | reset (void)
| Reset stack.
virtual void | post (Space &home) const
| Post no-goods.
Public Member Functions inherited from Gecode::NoGoods
| NoGoods (void)
| Initialize.
unsigned long int | ng (void) const
| Return number of no-goods posted.
void | ng (unsigned long int n)
| Set number of no-goods posted to n
virtual | ~NoGoods (void)
| Destructor.

## Protected Attributes

Support::DynamicStack< Edge, Heap > | ds
| Stack to store edge information.
unsigned int | _ngdl
| Depth limit for no-good generation.
Protected Attributes inherited from Gecode::NoGoods
unsigned long int | n
| Number of no-goods.

## Additional Inherited Members

Static Public Attributes inherited from Gecode::NoGoods
static NoGoods | eng
| Empty no-goods.

## Detailed Description

template<class Tracer>
class Gecode::Search::Seq::Path< Tracer >

Depth-first path (stack of edges) supporting recomputation.

Maintains the invariant that it contains the path of the space being currently explored. This is required to support recomputation, of course.

The path supports adaptive recomputation controlled by the value of a_d: only if the recomputation distance is at least this large, an additional clone is created.

Definition at line 60 of file path.hh.

## Member Typedef Documentation

## ID

template<class Tracer>

typedef Tracer::ID Gecode::Search::Seq::Path< Tracer >::ID

Node identity type.

Definition at line 64 of file path.hh.

## Constructor & Destructor Documentation

## Path()

template<class Tracer>

Gecode::Search::Seq::Path< Tracer >::Path | ( | unsigned int | l | ) |

inline

Initialize with no-good depth limit l.

Definition at line 119 of file path.hpp.

## Member Function Documentation

## ngdl() [1/2]

template<class Tracer>

unsigned int Gecode::Search::Seq::Path< Tracer >::ngdl | ( | void |  | ) | const

inline

Return no-good depth limit.

Definition at line 124 of file path.hpp.

## ngdl() [2/2]

template<class Tracer>

void Gecode::Search::Seq::Path< Tracer >::ngdl | ( | unsigned int | l | ) |

inline

Set no-good depth limit to l.

Definition at line 130 of file path.hpp.

## push()

template<class Tracer>

const Choice * Gecode::Search::Seq::Path< Tracer >::push | ( | Worker & | stat,
|  | Space * | s,
|  | Space * | c,
|  | unsigned int | nid )

inline

Push space c (a clone of s or NULL).

Definition at line 136 of file path.hpp.

## next()

template<class Tracer>

void Gecode::Search::Seq::Path< Tracer >::next | ( | void |  | ) |

inline

Generate path for next node.

Definition at line 149 of file path.hpp.

## top()

template<class Tracer>

Path< Tracer >::Edge & Gecode::Search::Seq::Path< Tracer >::top | ( | void |  | ) | const

inline

Provide access to topmost edge.

Definition at line 161 of file path.hpp.

## empty()

template<class Tracer>

bool Gecode::Search::Seq::Path< Tracer >::empty | ( | void |  | ) | const

inline

Test whether path is empty.

Definition at line 168 of file path.hpp.

## lc()

template<class Tracer>

int Gecode::Search::Seq::Path< Tracer >::lc | ( | void |  | ) | const

inline

Return position on stack of last copy.

Definition at line 181 of file path.hpp.

## unwind()

template<class Tracer>

void Gecode::Search::Seq::Path< Tracer >::unwind | ( | int | l,
|  | Tracer & | t )

inline

Unwind the stack up to position l (after failure).

Definition at line 196 of file path.hpp.

## commit()

template<class Tracer>

void Gecode::Search::Seq::Path< Tracer >::commit | ( | Space * | s,
|  | int | i ) const

inline

Commit space s as described by stack entry at position i.

Definition at line 174 of file path.hpp.

## recompute() [1/2]

template<class Tracer>

Space * Gecode::Search::Seq::Path< Tracer >::recompute | ( | unsigned int & | d,
|  | unsigned int | a_d,
|  | Worker & | s,
|  | Tracer & | t )

inline

Recompute space according to path.

Definition at line 225 of file path.hpp.

## recompute() [2/2]

template<class Tracer>

Space * Gecode::Search::Seq::Path< Tracer >::recompute | ( | unsigned int & | d,
|  | unsigned int | a_d,
|  | Worker & | s,
|  | const Space & | best,
|  | int & | mark,
|  | Tracer & | t )

inline

Recompute space according to path.

Definition at line 291 of file path.hpp.

## entries()

template<class Tracer>

int Gecode::Search::Seq::Path< Tracer >::entries | ( | void |  | ) | const

inline

Return number of entries on stack.

Definition at line 190 of file path.hpp.

## reset()

template<class Tracer>

void Gecode::Search::Seq::Path< Tracer >::reset | ( | void |  | ) |

inline

Reset stack.

Definition at line 218 of file path.hpp.

## post()

template<class Tracer>

void Gecode::Search::Seq::Path< Tracer >::post | ( | Space & | home | ) | const

virtual

Post no-goods.

Reimplemented from Gecode::NoGoods.

Definition at line 385 of file path.hpp.

## Member Data Documentation

## ds

template<class Tracer>

Support::DynamicStack<Edge,Heap> Gecode::Search::Seq::Path< Tracer >::ds

protected

Stack to store edge information.

Definition at line 111 of file path.hh.

## _ngdl

template<class Tracer>

unsigned int Gecode::Search::Seq::Path< Tracer >::_ngdl

protected

Depth limit for no-good generation.

Definition at line 113 of file path.hh.

The documentation for this class was generated from the following files:

- gecode/search/seq/path.hh
- gecode/search/seq/path.hpp