Gecode::Search::Parallel::Path Class Reference

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

#include <path.hh>

List of all members.

Classes
class	Edge
	Search tree edge for recomputation More...
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)
	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)
	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)
	Recompute space according to path.
Space *	recompute (unsigned int &d, unsigned int a_d, Worker &s, const Space &best, int &mark)
	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.
Space *	steal (Worker &stat, unsigned long int &d)
	Steal work at depth d.
virtual void	post (Space &home) const
	Post no-goods.
Protected Attributes
Support::DynamicStack< Edge, Heap >	ds
	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.

---

Detailed Description

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 61 of file path.hh.

---

Constructor & Destructor Documentation

Gecode::Search::Parallel::Path::Path

(

unsigned int

l

)

[inline]

Initialize with no-good depth limit l.

Definition at line 225 of file path.hh.

---

Member Function Documentation

unsigned int Gecode::Search::Parallel::Path::ngdl

(

void

)

const [inline]

Return no-good depth limit.

Definition at line 229 of file path.hh.

void Gecode::Search::Parallel::Path::ngdl

(

unsigned int

l

)

[inline]

Set no-good depth limit to l.

Definition at line 234 of file path.hh.

const Choice * Gecode::Search::Parallel::Path::push	(	Worker &	stat,
		Space *	s,
		Space *	c
	)			[inline]

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

Definition at line 239 of file path.hh.

void Gecode::Search::Parallel::Path::next

(

void

)

[inline]

Generate path for next node.

Definition at line 253 of file path.hh.

Path::Edge & Gecode::Search::Parallel::Path::top

(

void

)

const [inline]

Provide access to topmost edge.

Definition at line 267 of file path.hh.

bool Gecode::Search::Parallel::Path::empty

(

void

)

const [inline]

Test whether path is empty.

Definition at line 273 of file path.hh.

int Gecode::Search::Parallel::Path::lc

(

void

)

const [inline]

Return position on stack of last copy.

Definition at line 284 of file path.hh.

void Gecode::Search::Parallel::Path::unwind

(

int

l

)

[inline]

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

Definition at line 297 of file path.hh.

void Gecode::Search::Parallel::Path::commit	(	Space *	s,
		int	i
	)			const [inline]

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

Definition at line 278 of file path.hh.

Space * Gecode::Search::Parallel::Path::recompute	(	unsigned int &	d,
		unsigned int	a_d,
		Worker &	s
	)			[inline]

Recompute space according to path.

Definition at line 353 of file path.hh.

Space * Gecode::Search::Parallel::Path::recompute	(	unsigned int &	d,
		unsigned int	a_d,
		Worker &	s,
		const Space &	best,
		int &	mark
	)			[inline]

Recompute space according to path.

Definition at line 417 of file path.hh.

int Gecode::Search::Parallel::Path::entries

(

void

)

const [inline]

Return number of entries on stack.

Definition at line 292 of file path.hh.

void Gecode::Search::Parallel::Path::reset

(

unsigned int

l

)

[inline]

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

Definition at line 309 of file path.hh.

bool Gecode::Search::Parallel::Path::steal

(

void

)

const [inline]

Make a quick check whether stealing might be feasible.

Definition at line 317 of file path.hh.

Space * Gecode::Search::Parallel::Path::steal	(	Worker &	stat,
		unsigned long int &	d
	)			[inline]

Steal work at depth d.

Definition at line 322 of file path.hh.

void Gecode::Search::Parallel::Path::post

(

Space &

home

)

const [virtual]

Post no-goods.

Reimplemented from Gecode::NoGoods.

Definition at line 43 of file path.cpp.

---

Member Data Documentation

Support::DynamicStack<Edge,Heap> Gecode::Search::Parallel::Path::ds [protected]

Stack to store edge information.

Definition at line 109 of file path.hh.

unsigned int Gecode::Search::Parallel::Path::_ngdl [protected]

Depth limit for no-good generation.

Definition at line 111 of file path.hh.

unsigned int Gecode::Search::Parallel::Path::n_work [protected]

Number of edges that have work for stealing.

Definition at line 113 of file path.hh.

---

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

• gecode/search/parallel/path.hh (Revision: 14471)
• gecode/search/parallel/path.cpp (Revision: 14258)