path.hh
Go to the documentation of this file.
/* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
/*
* Main authors:
* Christian Schulte <schulte@gecode.org>
*
* Copyright:
* Christian Schulte, 2003
*
* This file is part of Gecode, the generic constraint
* development environment:
* http://www.gecode.org
*
* Permission is hereby granted, free of charge, to any person obtaining
* a copy of this software and associated documentation files (the
* "Software"), to deal in the Software without restriction, including
* without limitation the rights to use, copy, modify, merge, publish,
* distribute, sublicense, and/or sell copies of the Software, and to
* permit persons to whom the Software is furnished to do so, subject to
* the following conditions:
*
* The above copyright notice and this permission notice shall be
* included in all copies or substantial portions of the Software.
*
* THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
* EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
* MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
* NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
* LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
* OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
* WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
*
*/
#ifndef __GECODE_SEARCH_PAR_PATH_HH__
#define __GECODE_SEARCH_PAR_PATH_HH__
#include <algorithm>
#include <gecode/search.hh>
#include <gecode/search/support.hh>
#include <gecode/search/worker.hh>
#include <gecode/search/nogoods.hh>
namespace Gecode { namespace Search { namespace Par {
template<class Tracer>
class Path : public NoGoods {
friend class Search::NoGoodsProp;
public:
typedef typename Tracer::ID ID;
class Edge {
protected:
Space* _space;
unsigned int _alt;
unsigned int _alt_max;
const Choice* _choice;
ID _nid;
public:
Edge(void);
Edge(Space* s, Space* c, unsigned int nid);
Space* space(void) const;
void space(Space* s);
const Choice* choice(void) const;
unsigned int alt(void) const;
unsigned int truealt(void) const;
bool rightmost(void) const;
bool lao(void) const;
bool work(void) const;
void next(void);
unsigned int steal(void);
unsigned int nid(void) const;
void dispose(void);
};
protected:
Support::DynamicStack<Edge,Heap> ds;
unsigned int _ngdl;
unsigned int n_work;
public:
Path(unsigned int l);
unsigned int ngdl(void) const;
void ngdl(unsigned int l);
const Choice* push(Worker& stat, Space* s, Space* c, unsigned int nid);
void next(void);
Edge& top(void) const;
bool empty(void) const;
int lc(void) const;
void unwind(int l, Tracer& t);
void commit(Space* s, int i) const;
Space* recompute(unsigned int& d, unsigned int a_d, Worker& s,
Tracer& t);
Space* recompute(unsigned int& d, unsigned int a_d, Worker& s,
const Space& best, int& mark,
Tracer& t);
int entries(void) const;
void reset(unsigned int l);
bool steal(void) const;
Space* steal(Worker& stat, unsigned long int& d,
Tracer& myt, Tracer& ot);
void virtual post(Space& home) const;
};
}}}
#include <gecode/search/par/path.hpp>
#endif
// STATISTICS: search-par
Gecode::Choice
Choice for performing commit
Definition core.hpp:1412
Gecode::NoGoods::NoGoods
NoGoods(void)
Initialize.
Definition core.hpp:3052
Gecode::Search::NoGoodsProp
No-good propagator.
Definition nogoods.hh:65
Gecode::Search::Par::Path::Edge
Search tree edge for recomputation
Definition path.hh:66
Gecode::Search::Par::Path::Edge::work
bool work(void) const
Test whether there is an alternative that can be stolen.
Definition path.hpp:91
Gecode::Search::Par::Path::Edge::dispose
void dispose(void)
Free memory for edge.
Definition path.hpp:114
Gecode::Search::Par::Path::Edge::Edge
Edge(void)
Default constructor.
Definition path.hpp:42
Gecode::Search::Par::Path::Edge::truealt
unsigned int truealt(void) const
Return true number for alternatives (excluding lao optimization).
Definition path.hpp:76
Gecode::Search::Par::Path::Edge::lao
bool lao(void) const
Test whether current alternative was LAO.
Definition path.hpp:86
Gecode::Search::Par::Path::Edge::nid
unsigned int nid(void) const
Return node identifier.
Definition path.hpp:70
Gecode::Search::Par::Path::Edge::_choice
const Choice * _choice
Choice.
Definition path.hh:75
Gecode::Search::Par::Path::Edge::_alt_max
unsigned int _alt_max
Number of alternatives left.
Definition path.hh:73
Gecode::Search::Par::Path::Edge::choice
const Choice * choice(void) const
Return choice.
Definition path.hpp:108
Gecode::Search::Par::Path::Edge::space
Space * space(void) const
Return space for edge.
Definition path.hpp:53
Gecode::Search::Par::Path::Edge::alt
unsigned int alt(void) const
Return number for alternatives.
Definition path.hpp:64
Gecode::Search::Par::Path::Edge::_nid
ID _nid
Node identifier.
Definition path.hh:77
Gecode::Search::Par::Path::Edge::_alt
unsigned int _alt
Current alternative.
Definition path.hh:71
Gecode::Search::Par::Path::Edge::rightmost
bool rightmost(void) const
Test whether current alternative is rightmost.
Definition path.hpp:81
Gecode::Search::Par::Path::Edge::steal
unsigned int steal(void)
Steal rightmost alternative and return its number.
Definition path.hpp:101
Gecode::Search::Par::Path::Edge::next
void next(void)
Move to next alternative.
Definition path.hpp:96
Gecode::Search::Par::Path::Edge::_space
Space * _space
Space corresponding to this edge (might be NULL).
Definition path.hh:69
Gecode::Search::Par::Path::reset
void reset(unsigned int l)
Reset stack and set no-good depth limit to l.
Definition path.hpp:237
Gecode::Search::Par::Path::ngdl
unsigned int ngdl(void) const
Return no-good depth limit.
Definition path.hpp:133
Gecode::Search::Par::Path::unwind
void unwind(int l, Tracer &t)
Unwind the stack up to position l (after failure).
Definition path.hpp:210
Gecode::Search::Par::Path::ID
Tracer::ID ID
Identity type.
Definition path.hh:64
Gecode::Search::Par::Path::n_work
unsigned int n_work
Number of edges that have work for stealing.
Definition path.hh:119
Gecode::Search::Par::Path::push
const Choice * push(Worker &stat, Space *s, Space *c, unsigned int nid)
Push space c (a clone of s or NULL).
Definition path.hpp:145
Gecode::Search::Par::Path::Path
Path(unsigned int l)
Initialize with no-good depth limit l.
Definition path.hpp:128
Gecode::Search::Par::Path::ds
Support::DynamicStack< Edge, Heap > ds
Stack to store edge information.
Definition path.hh:115
Gecode::Search::Par::Path::commit
void commit(Space *s, int i) const
Commit space s as described by stack entry at position i.
Definition path.hpp:188
Gecode::Search::Par::Path::next
void next(void)
Generate path for next node.
Definition path.hpp:160
Gecode::Search::Par::Path::empty
bool empty(void) const
Test whether path is empty.
Definition path.hpp:182
Gecode::Search::Par::Path::post
virtual void post(Space &home) const
Post no-goods.
Definition path.hpp:449
Gecode::Search::Par::Path::_ngdl
unsigned int _ngdl
Depth limit for no-good generation.
Definition path.hh:117
Gecode::Search::Par::Path::lc
int lc(void) const
Return position on stack of last copy.
Definition path.hpp:195
Gecode::Search::Par::Path::entries
int entries(void) const
Return number of entries on stack.
Definition path.hpp:204
Gecode::Search::Par::Path::top
Edge & top(void) const
Provide access to topmost edge.
Definition path.hpp:175
Gecode::Search::Par::Path::steal
bool steal(void) const
Make a quick check whether stealing might be feasible.
Definition path.hpp:246
Gecode::Search::Par::Path::recompute
Space * recompute(unsigned int &d, unsigned int a_d, Worker &s, Tracer &t)
Recompute space according to path.
Definition path.hpp:289
Gecode::Search::Worker
Search worker statistics
Definition worker.hh:44
Gecode::Space
Computation spaces.
Definition core.hpp:1742
Gecode::Support::DynamicStack
Stack with arbitrary number of elements.
Definition dynamic-stack.hpp:42
Gecode::Tracer
Tracer.
Definition tracer.hpp:149
Gecode::Search::Par
Definition bab.hh:39
Gecode::Search
Search engines
Gecode
Gecode toplevel namespace
nogoods.hh
path.hpp
support.hh
search.hh
worker.hh