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, 2009
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
34namespace Gecode { namespace Search { namespace Seq {
35
36 template<class Tracer>
37 forceinline
38 DFS<Tracer>::DFS(Space* s, const Options& o)
39 : tracer(o.tracer), opt(o), path(opt.nogoods_limit), d(0) {
40 if (tracer) {
41 tracer.engine(SearchTracer::EngineType::DFS, 1U);
42 tracer.worker();
43 }
44 if ((s == nullptr) || (s->status(*this) == SS_FAILED)) {
45 fail++;
46 cur = nullptr;
47 if (!opt.clone)
48 delete s;
49 } else {
50 cur = snapshot(s,opt);
51 }
52 }
53
54 template<class Tracer>
55 forceinline void
56 DFS<Tracer>::reset(Space* s) {
57 tracer.round();
58 delete cur;
59 path.reset();
60 d = 0;
61 if ((s == nullptr) || (s->status(*this) == SS_FAILED)) {
62 delete s;
63 cur = nullptr;
64 } else {
65 cur = s;
66 }
67 Worker::reset();
68 }
69
70 template<class Tracer>
71 forceinline NoGoods&
72 DFS<Tracer>::nogoods(void) {
73 return path;
74 }
75
76 template<class Tracer>
77 forceinline Space*
78 DFS<Tracer>::next(void) {
79 /*
80 * The engine maintains the following invariant:
81 * - If the current space (cur) is not nullptr, the path always points
82 * to exactly that space.
83 * - If the current space (cur) is nullptr, the path always points
84 * to the next space (if there is any).
85 *
86 * This invariant is needed so that no-goods can be extracted properly
87 * when the engine is stopped or has found a solution.
88 *
89 */
90 start();
91 while (true) {
92 if (stop(opt))
93 return nullptr;
94 while (cur == nullptr) {
95 if (path.empty())
96 return nullptr;
97 cur = path.recompute(d,opt.a_d,*this,tracer);
98 if (cur != nullptr)
99 break;
100 path.next();
101 }
102 node++;
103 SearchTracer::EdgeInfo ei;
104 if (tracer && (path.entries() > 0)) {
105 typename Path<Tracer>::Edge& top = path.top();
106 ei.init(tracer.wid(), top.nid(), top.truealt(), *cur, *top.choice());
107 }
108 unsigned int nid = tracer.nid();
109 switch (cur->status(*this)) {
110 case SS_FAILED:
111 if (tracer) {
112 SearchTracer::NodeInfo ni(SearchTracer::NodeType::FAILED,
113 tracer.wid(), nid, *cur);
114 tracer.node(ei,ni);
115 }
116 fail++;
117 delete cur;
118 cur = nullptr;
119 path.next();
120 break;
121 case SS_SOLVED:
122 {
123 if (tracer) {
124 SearchTracer::NodeInfo ni(SearchTracer::NodeType::SOLVED,
125 tracer.wid(), nid, *cur);
126 tracer.node(ei,ni);
127 }
128 // Deletes all pending branchers
129 (void) cur->choice();
130 Space* s = cur;
131 cur = nullptr;
132 path.next();
133 return s;
134 }
135 case SS_BRANCH:
136 {
137 Space* c;
138 if ((d == 0) || (d >= opt.c_d)) {
139 c = cur->clone();
140 d = 1;
141 } else {
142 c = nullptr;
143 d++;
144 }
145 const Choice* ch = path.push(*this,cur,c,nid);
146 if (tracer) {
147 SearchTracer::NodeInfo ni(SearchTracer::NodeType::BRANCH,
148 tracer.wid(), nid, *cur, ch);
149 tracer.node(ei,ni);
150 }
151 cur->commit(*ch,0);
152 break;
153 }
154 default:
155 GECODE_NEVER;
156 }
157 }
158 GECODE_NEVER;
159 return nullptr;
160 }
161
162 template<class Tracer>
163 forceinline Statistics
164 DFS<Tracer>::statistics(void) const {
165 return *this;
166 }
167
168 template<class Tracer>
169 forceinline void
170 DFS<Tracer>::constrain(const Space& b) {
171 (void) b;
172 assert(false);
173 }
174
175 template<class Tracer>
176 forceinline
177 DFS<Tracer>::~DFS(void) {
178 delete cur;
179 tracer.done();
180 path.reset();
181 }
182
183}}}
184
185// STATISTICS: search-seq