this repo has no description
dekker.one
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
44namespace Gecode { namespace Search { namespace Par {
45
46 /**
47 * \brief Depth-first path (stack of edges) supporting recomputation
48 *
49 * Maintains the invariant that it contains
50 * the path of the node being currently explored. This
51 * is required to support recomputation, of course.
52 *
53 * The path supports adaptive recomputation controlled
54 * by the value of a_d: only if the recomputation
55 * distance is at least this large, an additional
56 * clone is created.
57 *
58 */
59 template<class Tracer>
60 class Path : public NoGoods {
61 friend class Search::NoGoodsProp;
62 public:
63 /// Identity type
64 typedef typename Tracer::ID ID;
65 /// %Search tree edge for recomputation
66 class Edge {
67 protected:
68 /// Space corresponding to this edge (might be nullptr)
69 Space* _space;
70 /// Current alternative
71 unsigned int _alt;
72 /// Number of alternatives left
73 unsigned int _alt_max;
74 /// Choice
75 const Choice* _choice;
76 /// Node identifier
77 ID _nid;
78 public:
79 /// Default constructor
80 Edge(void);
81 /// Edge for space \a s with clone \a c (possibly nullptr)
82 Edge(Space* s, Space* c, unsigned int nid);
83
84 /// Return space for edge
85 Space* space(void) const;
86 /// Set space to \a s
87 void space(Space* s);
88
89 /// Return choice
90 const Choice* choice(void) const;
91
92 /// Return number for alternatives
93 unsigned int alt(void) const;
94 /// Return true number for alternatives (excluding lao optimization)
95 unsigned int truealt(void) const;
96 /// Test whether current alternative is rightmost
97 bool rightmost(void) const;
98 /// Test whether current alternative was LAO
99 bool lao(void) const;
100 /// Test whether there is an alternative that can be stolen
101 bool work(void) const;
102 /// Move to next alternative
103 void next(void);
104 /// Steal rightmost alternative and return its number
105 unsigned int steal(void);
106
107 /// Return node identifier
108 unsigned int nid(void) const;
109
110 /// Free memory for edge
111 void dispose(void);
112 };
113 protected:
114 /// Stack to store edge information
115 Support::DynamicStack<Edge,Heap> ds;
116 /// Depth limit for no-good generation
117 unsigned int _ngdl;
118 /// Number of edges that have work for stealing
119 unsigned int n_work;
120 public:
121 /// Initialize with no-good depth limit \a l
122 Path(unsigned int l);
123 /// Return no-good depth limit
124 unsigned int ngdl(void) const;
125 /// Set no-good depth limit to \a l
126 void ngdl(unsigned int l);
127 /// Push space \a c (a clone of \a s or nullptr)
128 const Choice* push(Worker& stat, Space* s, Space* c, unsigned int nid);
129 /// Generate path for next node
130 void next(void);
131 /// Provide access to topmost edge
132 Edge& top(void) const;
133 /// Test whether path is empty
134 bool empty(void) const;
135 /// Return position on stack of last copy
136 int lc(void) const;
137 /// Unwind the stack up to position \a l (after failure)
138 void unwind(int l, Tracer& t);
139 /// Commit space \a s as described by stack entry at position \a i
140 void commit(Space* s, int i) const;
141 /// Recompute space according to path
142 Space* recompute(unsigned int& d, unsigned int a_d, Worker& s,
143 Tracer& t);
144 /// Recompute space according to path
145 Space* recompute(unsigned int& d, unsigned int a_d, Worker& s,
146 const Space& best, int& mark,
147 Tracer& t);
148 /// Return number of entries on stack
149 int entries(void) const;
150 /// Reset stack and set no-good depth limit to \a l
151 void reset(unsigned int l);
152 /// Make a quick check whether stealing might be feasible
153 bool steal(void) const;
154 /// Steal work at depth \a d
155 Space* steal(Worker& stat, unsigned long int& d,
156 Tracer& myt, Tracer& ot);
157 /// Post no-goods
158 void virtual post(Space& home) const;
159 };
160
161}}}
162
163#include <gecode/search/par/path.hpp>
164
165#endif
166
167// STATISTICS: search-par