main page
modules
namespaces
classes
files
Gecode home
Generated on Mon Jul 27 2020 00:00:00 for Gecode by
doxygen
1.8.18
gecode
search
seq
dfs.hpp
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, 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
34
namespace
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 == NULL) || (s->
status
(*
this
) ==
SS_FAILED
)) {
45
fail
++;
46
cur = NULL;
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 == NULL) || (s->
status
(*
this
) ==
SS_FAILED
)) {
62
delete
s;
63
cur = NULL;
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 NULL, the path always points
82
* to exactly that space.
83
* - If the current space (cur) is NULL, 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
NULL;
94
while
(cur == NULL) {
95
if
(
path
.empty())
96
return
NULL;
97
cur =
path
.recompute(
d
,
opt
.a_d,*
this
,tracer);
98
if
(cur != NULL)
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 = NULL;
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 = NULL;
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
= NULL;
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
NULL;
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
Gecode::Search::Seq::DFS::nogoods
NoGoods & nogoods(void)
Return no-goods.
Definition:
dfs.hpp:72
Gecode::Search::Seq::DFS::constrain
void constrain(const Space &b)
Constrain future solutions to be better than b (should never be called)
Definition:
dfs.hpp:170
Gecode::Search::Seq::Path::Edge::truealt
unsigned int truealt(void) const
Return true number for alternatives (excluding lao optimization)
Definition:
path.hpp:67
Gecode::SS_SOLVED
@ SS_SOLVED
Space is solved (no brancher left)
Definition:
core.hpp:1683
Gecode::Search::Options
Search engine options
Definition:
search.hh:746
Gecode::Search::Statistics::fail
unsigned long int fail
Number of failed nodes in search tree.
Definition:
search.hh:150
Gecode::Search::snapshot
Space * snapshot(Space *s, const Options &o)
Clone space s dependening on options o.
Definition:
support.hh:71
Gecode::SS_BRANCH
@ SS_BRANCH
Space must be branched (at least one brancher left)
Definition:
core.hpp:1684
Gecode::Space
Computation spaces.
Definition:
core.hpp:1742
Gecode
Gecode toplevel namespace
Gecode::Search::Seq::DFS::statistics
Statistics statistics(void) const
Return statistics.
Definition:
dfs.hpp:164
Gecode::NoGoods
No-goods recorded from restarts.
Definition:
core.hpp:1588
Test::opt
Options opt
The options.
Definition:
test.cpp:97
Gecode::Search::Seq::Path::Edge::nid
unsigned int nid(void) const
Return node identifier.
Definition:
path.hpp:99
Gecode::Driver::stop
void stop(Support::Timer &timer, std::ostream &os)
Get time since start of timer and print user friendly time information.
Definition:
script.cpp:42
Gecode::Search::Seq::Path::Edge
Search tree edge for recomputation
Definition:
path.hh:66
Gecode::SearchTracer::NodeInfo
Node information.
Definition:
search.hh:282
Gecode::Search::Config::nogoods_limit
const unsigned int nogoods_limit
Depth limit for no-good generation during search.
Definition:
search.hh:131
b
struct Gecode::@602::NNF::@65::@66 b
For binary nodes (and, or, eqv)
Gecode::Search::Seq::DFS::DFS
DFS(Space *s, const Options &o)
Initialize for space s with options o.
Definition:
dfs.hpp:38
Gecode::Gist::BRANCH
@ BRANCH
Node representing a branch.
Definition:
spacenode.hh:47
GECODE_NEVER
#define GECODE_NEVER
Assert that this command is never executed.
Definition:
macros.hpp:56
Gecode::Search::Seq::Path::Edge::choice
const Choice * choice(void) const
Return choice.
Definition:
path.hpp:93
Gecode::Space::status
SpaceStatus status(StatusStatistics &stat=unused_status)
Query space status.
Definition:
core.cpp:252
Gecode::SearchTracer::EdgeInfo
Edge information.
Definition:
search.hh:242
Gecode::Search::Seq::DFS::~DFS
~DFS(void)
Destructor.
Definition:
dfs.hpp:177
Test::Int::Distinct::d
Gecode::IntSet d(v, 7)
Gecode::SearchTracer::EdgeInfo::init
void init(unsigned int wid, unsigned int nid, unsigned int a)
Initialize.
Definition:
tracer.hpp:107
Gecode::path
void path(Home home, int offset, const IntVarArgs &x, IntVar s, IntVar e, IntPropLevel ipl)
Post propagator such that x forms a Hamiltonian path.
Definition:
circuit.cpp:124
forceinline
#define forceinline
Definition:
config.hpp:185
Test::Float::Arithmetic::c
Gecode::FloatVal c(-8, 8)
Gecode::Search::Statistics::reset
void reset(void)
Reset.
Definition:
statistics.hpp:39
Gecode::Choice
Choice for performing commit
Definition:
core.hpp:1412
Gecode::Search::Options::clone
bool clone
Whether engines create a clone when being initialized.
Definition:
search.hh:749
Gecode::Gist::FAILED
@ FAILED
Node representing failure.
Definition:
spacenode.hh:46
Gecode::Search::Statistics
Search engine statistics
Definition:
search.hh:147
Gecode::SS_FAILED
@ SS_FAILED
Space is failed
Definition:
core.hpp:1682
Gecode::Gist::SOLVED
@ SOLVED
Node representing a solution.
Definition:
spacenode.hh:45
Gecode::Search::Seq::DFS::next
Space * next(void)
Search for next solution
Definition:
dfs.hpp:78