Generated on Tue Feb 11 2025 17:33:26 for Gecode by doxygen 1.12.0
Gecode::Search::Par::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
 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 Choicepush (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.
 
Edgetop (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.
 
Spacerecompute (unsigned int &d, unsigned int a_d, Worker &s, Tracer &t)
 Recompute space according to path.
 
Spacerecompute (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 (unsigned int l)
 Reset stack and set no-good depth limit to l.
 
bool steal (void) const
 Make a quick check whether stealing might be feasible.
 
Spacesteal (Worker &stat, unsigned long int &d, Tracer &myt, Tracer &ot)
 Steal work at depth d.
 
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, Heapds
 Stack to store edge information.
 
unsigned int _ngdl
 Depth limit for no-good generation.
 
unsigned int n_work
 Number of edges that have work for stealing.
 
- 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::Par::Path< Tracer >

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

Maintains the invariant that it contains the path of the node 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 >
Tracer::ID Gecode::Search::Par::Path< Tracer >::ID

Identity type.

Definition at line 64 of file path.hh.

Constructor & Destructor Documentation

◆ Path()

template<class Tracer >
Gecode::Search::Par::Path< Tracer >::Path ( unsigned int l)
inline

Initialize with no-good depth limit l.

Definition at line 128 of file path.hpp.

Member Function Documentation

◆ ngdl() [1/2]

template<class Tracer >
unsigned int Gecode::Search::Par::Path< Tracer >::ngdl ( void ) const
inline

Return no-good depth limit.

Definition at line 133 of file path.hpp.

◆ ngdl() [2/2]

template<class Tracer >
void Gecode::Search::Par::Path< Tracer >::ngdl ( unsigned int l)
inline

Set no-good depth limit to l.

Definition at line 139 of file path.hpp.

◆ push()

template<class Tracer >
const Choice * Gecode::Search::Par::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 145 of file path.hpp.

◆ next()

template<class Tracer >
void Gecode::Search::Par::Path< Tracer >::next ( void )
inline

Generate path for next node.

Definition at line 160 of file path.hpp.

◆ top()

template<class Tracer >
Path< Tracer >::Edge & Gecode::Search::Par::Path< Tracer >::top ( void ) const
inline

Provide access to topmost edge.

Definition at line 175 of file path.hpp.

◆ empty()

template<class Tracer >
bool Gecode::Search::Par::Path< Tracer >::empty ( void ) const
inline

Test whether path is empty.

Definition at line 182 of file path.hpp.

◆ lc()

template<class Tracer >
int Gecode::Search::Par::Path< Tracer >::lc ( void ) const
inline

Return position on stack of last copy.

Definition at line 195 of file path.hpp.

◆ unwind()

template<class Tracer >
void Gecode::Search::Par::Path< Tracer >::unwind ( int l,
Tracer & t )
inline

Unwind the stack up to position l (after failure)

Definition at line 210 of file path.hpp.

◆ commit()

template<class Tracer >
void Gecode::Search::Par::Path< Tracer >::commit ( Space * s,
int i ) const
inline

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

Definition at line 188 of file path.hpp.

◆ recompute() [1/2]

template<class Tracer >
Space * Gecode::Search::Par::Path< Tracer >::recompute ( unsigned int & d,
unsigned int a_d,
Worker & s,
Tracer & t )
inline

Recompute space according to path.

Definition at line 289 of file path.hpp.

◆ recompute() [2/2]

template<class Tracer >
Space * Gecode::Search::Par::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 355 of file path.hpp.

◆ entries()

template<class Tracer >
int Gecode::Search::Par::Path< Tracer >::entries ( void ) const
inline

Return number of entries on stack.

Definition at line 204 of file path.hpp.

◆ reset()

template<class Tracer >
void Gecode::Search::Par::Path< Tracer >::reset ( unsigned int l)
inline

Reset stack and set no-good depth limit to l.

Definition at line 237 of file path.hpp.

◆ steal() [1/2]

template<class Tracer >
bool Gecode::Search::Par::Path< Tracer >::steal ( void ) const
inline

Make a quick check whether stealing might be feasible.

Definition at line 246 of file path.hpp.

◆ steal() [2/2]

template<class Tracer >
Space * Gecode::Search::Par::Path< Tracer >::steal ( Worker & stat,
unsigned long int & d,
Tracer & myt,
Tracer & ot )
inline

Steal work at depth d.

Definition at line 252 of file path.hpp.

◆ post()

template<class Tracer >
void Gecode::Search::Par::Path< Tracer >::post ( Space & home) const
virtual

Post no-goods.

Reimplemented from Gecode::NoGoods.

Definition at line 449 of file path.hpp.

Member Data Documentation

◆ ds

Stack to store edge information.

Definition at line 115 of file path.hh.

◆ _ngdl

template<class Tracer >
unsigned int Gecode::Search::Par::Path< Tracer >::_ngdl
protected

Depth limit for no-good generation.

Definition at line 117 of file path.hh.

◆ n_work

template<class Tracer >
unsigned int Gecode::Search::Par::Path< Tracer >::n_work
protected

Number of edges that have work for stealing.

Definition at line 119 of file path.hh.


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