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
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_SEQ_PATH_HH__
35
#define __GECODE_SEARCH_SEQ_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
Seq {
45
59
template
<
class
Tracer>
60
class
GECODE_VTABLE_EXPORT
Path
:
public
NoGoods
{
61
friend
class
Search::NoGoodsProp
;
62
public
:
64
typedef
typename
Tracer::ID
ID
;
66
class
Edge
{
67
protected
:
69
Space
*
_space
;
71
unsigned
int
_alt
;
73
const
Choice
*
_choice
;
75
ID
_nid
;
76
public
:
78
Edge
(
void
);
80
Edge
(
Space
* s,
Space
*
c
,
unsigned
int
nid);
81
83
Space
* space(
void
)
const
;
85
void
space(
Space
* s);
86
88
const
Choice
* choice(
void
)
const
;
89
91
unsigned
int
alt(
void
)
const
;
93
unsigned
int
truealt(
void
)
const
;
95
bool
leftmost(
void
)
const
;
97
bool
rightmost(
void
)
const
;
99
void
next(
void
);
101
bool
lao(
void
)
const
;
102
104
unsigned
int
nid(
void
)
const
;
105
107
void
dispose(
void
);
108
};
109
protected
:
111
Support::DynamicStack<Edge,Heap>
ds
;
113
unsigned
int
_ngdl
;
114
public
:
116
Path
(
unsigned
int
l
);
118
unsigned
int
ngdl(
void
)
const
;
120
void
ngdl(
unsigned
int
l
);
122
const
Choice
* push(
Worker
& stat,
Space
* s,
Space
*
c
,
unsigned
int
nid);
124
void
next(
void
);
126
Edge& top(
void
)
const
;
128
bool
empty(
void
)
const
;
130
int
lc(
void
)
const
;
132
void
unwind(
int
l
,
Tracer
&
t
);
134
void
commit(
Space
* s,
int
i
)
const
;
136
Space
* recompute(
unsigned
int
&
d
,
unsigned
int
a_d
,
Worker
& s,
137
Tracer
&
t
);
139
Space
* recompute(
unsigned
int
&
d
,
unsigned
int
a_d
,
Worker
& s,
140
const
Space
& best,
int
&
mark
,
141
Tracer
&
t
);
143
int
entries(
void
)
const
;
145
void
reset(
void
);
147
virtual
void
post
(
Space
& home)
const
;
148
};
149
150
}}}
151
152
#include <
gecode/search/seq/path.hpp
>
153
154
#endif
155
156
// STATISTICS: search-seq
Gecode::Search::NoGoodsProp
No-good propagator.
Definition:
nogoods.hh:65
Gecode::Search::Worker
Search worker statistics
Definition:
worker.hh:44
worker.hh
GECODE_VTABLE_EXPORT
#define GECODE_VTABLE_EXPORT
Definition:
support.hh:72
Gecode::Search::Seq::Path
Depth-first path (stack of edges) supporting recomputation.
Definition:
path.hh:60
Gecode::Search::Seq::Path::ds
Support::DynamicStack< Edge, Heap > ds
Stack to store edge information.
Definition:
path.hh:111
Gecode::Support::mark
void * mark(void *p)
Return marked pointer for unmarked pointer p.
Definition:
marked-pointer.hpp:58
nogoods.hh
t
NodeType t
Type of node.
Definition:
bool-expr.cpp:230
search.hh
Gecode::Space
Computation spaces.
Definition:
core.hpp:1742
support.hh
Gecode
Gecode toplevel namespace
Gecode::Search::Seq::Path::ID
Tracer::ID ID
Node identity type.
Definition:
path.hh:64
Gecode::NoGoods
No-goods recorded from restarts.
Definition:
core.hpp:1588
Gecode::Search::Seq::Path::Edge
Search tree edge for recomputation
Definition:
path.hh:66
Gecode::Search::Seq::Path::Edge::_choice
const Choice * _choice
Choice.
Definition:
path.hh:73
Gecode::post
TFE post(PropagatorGroup g)
Only post functions (but not propagators) from g are considered.
Definition:
filter.cpp:138
path.hpp
Gecode::Tracer
Tracer.
Definition:
tracer.hpp:149
l
NNF * l
Left subtree.
Definition:
bool-expr.cpp:240
Gecode::Search::Seq::Path::_ngdl
unsigned int _ngdl
Depth limit for no-good generation.
Definition:
path.hh:113
Test::Int::Distinct::d
Gecode::IntSet d(v, 7)
Gecode::Search::Seq::Path::Edge::_alt
unsigned int _alt
Current alternative.
Definition:
path.hh:71
Gecode::Support::DynamicStack
Stack with arbitrary number of elements.
Definition:
dynamic-stack.hpp:42
Gecode::Search::Seq::Path::Edge::_nid
ID _nid
Node identifier.
Definition:
path.hh:75
Gecode::Search::Config::a_d
const unsigned int a_d
Create a clone during recomputation if distance is greater than a_d (adaptive distance)
Definition:
search.hh:115
Test::Float::Arithmetic::c
Gecode::FloatVal c(-8, 8)
Gecode::Choice
Choice for performing commit
Definition:
core.hpp:1412
Test::Int::Basic::i
Gecode::IntArgs i({1, 2, 3, 4})
Gecode::Search::Seq::Path::Edge::_space
Space * _space
Space corresponding to this edge (might be NULL)
Definition:
path.hh:69