Generated on Thu Apr 5 2018 19:44:19 for Gecode by doxygen 1.8.13
path.hh
Go to the documentation of this file.
1 /* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
2 /*
3  * Main authors:
4  * Christian Schulte <schulte@gecode.org>
5  *
6  * Copyright:
7  * Christian Schulte, 2003
8  *
9  * Last modified:
10  * $Date$ by $Author$
11  * $Revision$
12  *
13  * This file is part of Gecode, the generic constraint
14  * development environment:
15  * http://www.gecode.org
16  *
17  * Permission is hereby granted, free of charge, to any person obtaining
18  * a copy of this software and associated documentation files (the
19  * "Software"), to deal in the Software without restriction, including
20  * without limitation the rights to use, copy, modify, merge, publish,
21  * distribute, sublicense, and/or sell copies of the Software, and to
22  * permit persons to whom the Software is furnished to do so, subject to
23  * the following conditions:
24  *
25  * The above copyright notice and this permission notice shall be
26  * included in all copies or substantial portions of the Software.
27  *
28  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
29  * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
30  * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
31  * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
32  * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
33  * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
34  * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
35  *
36  */
37 
38 #ifndef __GECODE_SEARCH_PAR_PATH_HH__
39 #define __GECODE_SEARCH_PAR_PATH_HH__
40 
41 #include <algorithm>
42 
43 #include <gecode/search.hh>
44 #include <gecode/search/support.hh>
45 #include <gecode/search/worker.hh>
46 #include <gecode/search/nogoods.hh>
47 
48 namespace Gecode { namespace Search { namespace Par {
49 
63  template<class Tracer>
64  class Path : public NoGoods {
65  friend class Search::NoGoodsProp;
66  public:
68  typedef typename Tracer::ID ID;
70  class Edge {
71  protected:
75  unsigned int _alt;
77  unsigned int _alt_max;
79  const Choice* _choice;
81  ID _nid;
82  public:
84  Edge(void);
86  Edge(Space* s, Space* c, unsigned int nid);
87 
89  Space* space(void) const;
91  void space(Space* s);
92 
94  const Choice* choice(void) const;
95 
97  unsigned int alt(void) const;
99  unsigned int truealt(void) const;
101  bool rightmost(void) const;
103  bool lao(void) const;
105  bool work(void) const;
107  void next(void);
109  unsigned int steal(void);
110 
112  unsigned int nid(void) const;
113 
115  void dispose(void);
116  };
117  protected:
121  unsigned int _ngdl;
123  unsigned int n_work;
124  public:
126  Path(unsigned int l);
128  unsigned int ngdl(void) const;
130  void ngdl(unsigned int l);
132  const Choice* push(Worker& stat, Space* s, Space* c, unsigned int nid);
134  void next(void);
136  Edge& top(void) const;
138  bool empty(void) const;
140  int lc(void) const;
142  void unwind(int l, Tracer& t);
144  void commit(Space* s, int i) const;
146  Space* recompute(unsigned int& d, unsigned int a_d, Worker& s,
147  Tracer& t);
149  Space* recompute(unsigned int& d, unsigned int a_d, Worker& s,
150  const Space& best, int& mark,
151  Tracer& t);
153  int entries(void) const;
155  void reset(unsigned int l);
157  bool steal(void) const;
159  Space* steal(Worker& stat, unsigned long int& d,
160  Tracer& myt, Tracer& ot);
162  void virtual post(Space& home) const;
163  };
164 
165 }}}
166 
168 
169 #endif
170 
171 // STATISTICS: search-par
Space * recompute(unsigned int &d, unsigned int a_d, Worker &s, Tracer &t)
Recompute space according to path.
Definition: path.hpp:293
NodeType t
Type of node.
Definition: bool-expr.cpp:234
Edge & top(void) const
Provide access to topmost edge.
Definition: path.hpp:179
NNF * l
Left subtree.
Definition: bool-expr.cpp:244
unsigned int alt(void) const
Return number for alternatives.
Definition: path.hpp:68
bool work(void) const
Test whether there is an alternative that can be stolen.
Definition: path.hpp:95
unsigned int n_work
Number of edges that have work for stealing.
Definition: path.hh:123
bool empty(void) const
Test whether path is empty.
Definition: path.hpp:186
unsigned int _alt
Current alternative.
Definition: path.hh:75
bool rightmost(void) const
Test whether current alternative is rightmost.
Definition: path.hpp:85
ID _nid
Node identifier.
Definition: path.hh:81
Path(unsigned int l)
Initialize with no-good depth limit l.
Definition: path.hpp:132
void unwind(int l, Tracer &t)
Unwind the stack up to position l (after failure)
Definition: path.hpp:214
void dispose(void)
Free memory for edge.
Definition: path.hpp:118
void * mark(void *p)
Return marked pointer for unmarked pointer p.
Support::DynamicStack< Edge, Heap > ds
Stack to store edge information.
Definition: path.hh:119
unsigned int ngdl(void) const
Return no-good depth limit.
Definition: path.hpp:137
Search tree edge for recomputation
Definition: path.hh:70
unsigned int nid(void) const
Return node identifier.
Definition: path.hpp:74
Computation spaces.
Definition: core.hpp:1668
No-good propagator.
Definition: nogoods.hh:69
Gecode::IntSet d(v, 7)
Gecode::FloatVal c(-8, 8)
Gecode::IntArgs i(4, 1, 2, 3, 4)
const unsigned int a_d
Create a clone during recomputation if distance is greater than a_d (adaptive distance) ...
Definition: search.hh:117
unsigned int steal(void)
Steal rightmost alternative and return its number.
Definition: path.hpp:105
unsigned int _ngdl
Depth limit for no-good generation.
Definition: path.hh:121
const Choice * choice(void) const
Return choice.
Definition: path.hpp:112
Tracer::ID ID
Identity type.
Definition: path.hh:68
Edge(void)
Default constructor.
Definition: path.hpp:46
Search worker statistics
Definition: worker.hh:48
virtual void post(Space &home) const
Post no-goods.
Definition: path.hpp:453
Choice for performing commit
Definition: core.hpp:1338
No-goods recorded from restarts.
Definition: core.hpp:1514
void commit(Space *s, int i) const
Commit space s as described by stack entry at position i.
Definition: path.hpp:192
void next(void)
Move to next alternative.
Definition: path.hpp:100
unsigned int _alt_max
Number of alternatives left.
Definition: path.hh:77
bool lao(void) const
Test whether current alternative was LAO.
Definition: path.hpp:90
int entries(void) const
Return number of entries on stack.
Definition: path.hpp:208
Stack with arbitrary number of elements.
int lc(void) const
Return position on stack of last copy.
Definition: path.hpp:199
Tracer.
Definition: tracer.hpp:153
void reset(unsigned int l)
Reset stack and set no-good depth limit to l.
Definition: path.hpp:241
Gecode toplevel namespace
const Choice * _choice
Choice.
Definition: path.hh:79
unsigned int truealt(void) const
Return true number for alternatives (excluding lao optimization)
Definition: path.hpp:80
Depth-first path (stack of edges) supporting recomputation.
Definition: path.hh:64
const Choice * push(Worker &stat, Space *s, Space *c, unsigned int nid)
Push space c (a clone of s or NULL)
Definition: path.hpp:149
Space * space(void) const
Return space for edge.
Definition: path.hpp:57
Space * _space
Space corresponding to this edge (might be NULL)
Definition: path.hh:73