Generated on Thu Jan 16 2025 00:00:00 for Gecode by doxygen 1.14.0
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>
43
44namespace 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;
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
Choice for performing commit
Definition core.hpp:1414
NoGoods(void)
Initialize.
Definition core.hpp:3056
No-good propagator.
Definition nogoods.hh:65
Search tree edge for recomputation
Definition path.hh:66
bool work(void) const
Test whether there is an alternative that can be stolen.
Definition path.hpp:91
void dispose(void)
Free memory for edge.
Definition path.hpp:114
Edge(void)
Default constructor.
Definition path.hpp:42
unsigned int truealt(void) const
Return true number for alternatives (excluding lao optimization)
Definition path.hpp:76
bool lao(void) const
Test whether current alternative was LAO.
Definition path.hpp:86
unsigned int nid(void) const
Return node identifier.
Definition path.hpp:70
const Choice * _choice
Choice.
Definition path.hh:75
unsigned int _alt_max
Number of alternatives left.
Definition path.hh:73
const Choice * choice(void) const
Return choice.
Definition path.hpp:108
Space * space(void) const
Return space for edge.
Definition path.hpp:53
unsigned int alt(void) const
Return number for alternatives.
Definition path.hpp:64
ID _nid
Node identifier.
Definition path.hh:77
unsigned int _alt
Current alternative.
Definition path.hh:71
bool rightmost(void) const
Test whether current alternative is rightmost.
Definition path.hpp:81
unsigned int steal(void)
Steal rightmost alternative and return its number.
Definition path.hpp:101
void next(void)
Move to next alternative.
Definition path.hpp:96
Space * _space
Space corresponding to this edge (might be NULL)
Definition path.hh:69
void reset(unsigned int l)
Reset stack and set no-good depth limit to l.
Definition path.hpp:237
unsigned int ngdl(void) const
Return no-good depth limit.
Definition path.hpp:133
void unwind(int l, Tracer &t)
Unwind the stack up to position l (after failure)
Definition path.hpp:210
Tracer::ID ID
Identity type.
Definition path.hh:64
unsigned int n_work
Number of edges that have work for stealing.
Definition path.hh:119
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
Path(unsigned int l)
Initialize with no-good depth limit l.
Definition path.hpp:128
Support::DynamicStack< Edge, Heap > ds
Stack to store edge information.
Definition path.hh:115
void commit(Space *s, int i) const
Commit space s as described by stack entry at position i.
Definition path.hpp:188
void next(void)
Generate path for next node.
Definition path.hpp:160
bool empty(void) const
Test whether path is empty.
Definition path.hpp:182
virtual void post(Space &home) const
Post no-goods.
Definition path.hpp:449
unsigned int _ngdl
Depth limit for no-good generation.
Definition path.hh:117
int lc(void) const
Return position on stack of last copy.
Definition path.hpp:195
int entries(void) const
Return number of entries on stack.
Definition path.hpp:204
Edge & top(void) const
Provide access to topmost edge.
Definition path.hpp:175
bool steal(void) const
Make a quick check whether stealing might be feasible.
Definition path.hpp:246
Space * recompute(unsigned int &d, unsigned int a_d, Worker &s, Tracer &t)
Recompute space according to path.
Definition path.hpp:289
Search worker statistics
Definition worker.hh:44
Computation spaces.
Definition core.hpp:1744
Stack with arbitrary number of elements.
Search engines
Gecode toplevel namespace