Generated on Mon Jul 27 2020 00:00:00 for Gecode by doxygen 1.8.18
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  * This file is part of Gecode, the generic constraint
10  * development environment:
11  * http://www.gecode.org
12  *
13  * Permission is hereby granted, free of charge, to any person obtaining
14  * a copy of this software and associated documentation files (the
15  * "Software"), to deal in the Software without restriction, including
16  * without limitation the rights to use, copy, modify, merge, publish,
17  * distribute, sublicense, and/or sell copies of the Software, and to
18  * permit persons to whom the Software is furnished to do so, subject to
19  * the following conditions:
20  *
21  * The above copyright notice and this permission notice shall be
22  * included in all copies or substantial portions of the Software.
23  *
24  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
25  * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
26  * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
27  * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
28  * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
29  * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
30  * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
31  *
32  */
33 
34 #ifndef __GECODE_SEARCH_PAR_PATH_HH__
35 #define __GECODE_SEARCH_PAR_PATH_HH__
36 
37 #include <algorithm>
38 
39 #include <gecode/search.hh>
40 #include <gecode/search/support.hh>
41 #include <gecode/search/worker.hh>
42 #include <gecode/search/nogoods.hh>
43 
44 namespace Gecode { namespace Search { namespace Par {
45 
59  template<class Tracer>
60  class Path : public NoGoods {
61  friend class Search::NoGoodsProp;
62  public:
64  typedef typename Tracer::ID ID;
66  class Edge {
67  protected:
71  unsigned int _alt;
73  unsigned int _alt_max;
75  const Choice* _choice;
78  public:
80  Edge(void);
82  Edge(Space* s, Space* c, unsigned int nid);
83 
85  Space* space(void) const;
87  void space(Space* s);
88 
90  const Choice* choice(void) const;
91 
93  unsigned int alt(void) const;
95  unsigned int truealt(void) const;
97  bool rightmost(void) const;
99  bool lao(void) const;
101  bool work(void) const;
103  void next(void);
105  unsigned int steal(void);
106 
108  unsigned int nid(void) const;
109 
111  void dispose(void);
112  };
113  protected:
117  unsigned int _ngdl;
119  unsigned int n_work;
120  public:
122  Path(unsigned int l);
124  unsigned int ngdl(void) const;
126  void ngdl(unsigned int l);
128  const Choice* push(Worker& stat, Space* s, Space* c, unsigned int nid);
130  void next(void);
132  Edge& top(void) const;
134  bool empty(void) const;
136  int lc(void) const;
138  void unwind(int l, Tracer& t);
140  void commit(Space* s, int i) const;
142  Space* recompute(unsigned int& d, unsigned int a_d, Worker& s,
143  Tracer& t);
145  Space* recompute(unsigned int& d, unsigned int a_d, Worker& s,
146  const Space& best, int& mark,
147  Tracer& t);
149  int entries(void) const;
151  void reset(unsigned int l);
153  bool steal(void) const;
155  Space* steal(Worker& stat, unsigned long int& d,
156  Tracer& myt, Tracer& ot);
158  void virtual post(Space& home) const;
159  };
160 
161 }}}
162 
164 
165 #endif
166 
167 // STATISTICS: search-par
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
void commit(Space *s, int i) const
Commit space s as described by stack entry at position i.
Definition: path.hpp:188
No-good propagator.
Definition: nogoods.hh:65
unsigned int nid(void) const
Return node identifier.
Definition: path.hpp:70
bool empty(void) const
Test whether path is empty.
Definition: path.hpp:182
Search worker statistics
Definition: worker.hh:44
bool rightmost(void) const
Test whether current alternative is rightmost.
Definition: path.hpp:81
bool work(void) const
Test whether there is an alternative that can be stolen.
Definition: path.hpp:91
void next(void)
Move to next alternative.
Definition: path.hpp:96
Support::DynamicStack< Edge, Heap > ds
Stack to store edge information.
Definition: path.hh:115
Path(unsigned int l)
Initialize with no-good depth limit l.
Definition: path.hpp:128
Space * recompute(unsigned int &d, unsigned int a_d, Worker &s, Tracer &t)
Recompute space according to path.
Definition: path.hpp:289
void * mark(void *p)
Return marked pointer for unmarked pointer p.
NodeType t
Type of node.
Definition: bool-expr.cpp:230
Search tree edge for recomputation
Definition: path.hh:66
const Choice * _choice
Choice.
Definition: path.hh:75
Computation spaces.
Definition: core.hpp:1742
unsigned int truealt(void) const
Return true number for alternatives (excluding lao optimization)
Definition: path.hpp:76
void unwind(int l, Tracer &t)
Unwind the stack up to position l (after failure)
Definition: path.hpp:210
bool lao(void) const
Test whether current alternative was LAO.
Definition: path.hpp:86
unsigned int _alt_max
Number of alternatives left.
Definition: path.hh:73
Gecode toplevel namespace
const Choice * choice(void) const
Return choice.
Definition: path.hpp:108
No-goods recorded from restarts.
Definition: core.hpp:1588
Space * _space
Space corresponding to this edge (might be NULL)
Definition: path.hh:69
Edge(void)
Default constructor.
Definition: path.hpp:42
unsigned int n_work
Number of edges that have work for stealing.
Definition: path.hh:119
Depth-first path (stack of edges) supporting recomputation.
Definition: path.hh:60
bool steal(void) const
Make a quick check whether stealing might be feasible.
Definition: path.hpp:246
unsigned int _ngdl
Depth limit for no-good generation.
Definition: path.hh:117
int entries(void) const
Return number of entries on stack.
Definition: path.hpp:204
unsigned int ngdl(void) const
Return no-good depth limit.
Definition: path.hpp:133
Tracer.
Definition: tracer.hpp:149
Space * space(void) const
Return space for edge.
Definition: path.hpp:53
void dispose(void)
Free memory for edge.
Definition: path.hpp:114
Tracer::ID ID
Identity type.
Definition: path.hh:64
NNF * l
Left subtree.
Definition: bool-expr.cpp:240
unsigned int _alt
Current alternative.
Definition: path.hh:71
unsigned int steal(void)
Steal rightmost alternative and return its number.
Definition: path.hpp:101
Gecode::IntSet d(v, 7)
ID _nid
Node identifier.
Definition: path.hh:77
Stack with arbitrary number of elements.
void next(void)
Generate path for next node.
Definition: path.hpp:160
virtual void post(Space &home) const
Post no-goods.
Definition: path.hpp:449
const unsigned int a_d
Create a clone during recomputation if distance is greater than a_d (adaptive distance)
Definition: search.hh:115
Gecode::FloatVal c(-8, 8)
Choice for performing commit
Definition: core.hpp:1412
int lc(void) const
Return position on stack of last copy.
Definition: path.hpp:195
unsigned int alt(void) const
Return number for alternatives.
Definition: path.hpp:64
Edge & top(void) const
Provide access to topmost edge.
Definition: path.hpp:175
Gecode::IntArgs i({1, 2, 3, 4})
void reset(unsigned int l)
Reset stack and set no-good depth limit to l.
Definition: path.hpp:237