Generated on Thu Apr 5 2018 19:44:19 for Gecode by doxygen 1.8.13
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  * Last modified:
10  * $Date$ by $Author$
11  * $Revision$
12  *
13  * This file is part of Gecode, the generic constraint
14  * development environment:
15  * http://www.gecode.org
16  *
17  * Permission is hereby granted, free of charge, to any person obtaining
18  * a copy of this software and associated documentation files (the
19  * "Software"), to deal in the Software without restriction, including
20  * without limitation the rights to use, copy, modify, merge, publish,
21  * distribute, sublicense, and/or sell copies of the Software, and to
22  * permit persons to whom the Software is furnished to do so, subject to
23  * the following conditions:
24  *
25  * The above copyright notice and this permission notice shall be
26  * included in all copies or substantial portions of the Software.
27  *
28  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
29  * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
30  * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
31  * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
32  * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
33  * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
34  * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
35  *
36  */
37 
38 #ifndef __GECODE_SEARCH_SEQ_PATH_HH__
39 #define __GECODE_SEARCH_SEQ_PATH_HH__
40 
41 #include <algorithm>
42 
43 #include <gecode/search.hh>
44 #include <gecode/search/support.hh>
45 #include <gecode/search/worker.hh>
46 #include <gecode/search/nogoods.hh>
47 
48 namespace Gecode { namespace Search { namespace Seq {
49 
63  template<class Tracer>
65  friend class Search::NoGoodsProp;
66  public:
68  typedef typename Tracer::ID ID;
70  class Edge {
71  protected:
75  unsigned int _alt;
77  const Choice* _choice;
79  ID _nid;
80  public:
82  Edge(void);
84  Edge(Space* s, Space* c, unsigned int nid);
85 
87  Space* space(void) const;
89  void space(Space* s);
90 
92  const Choice* choice(void) const;
93 
95  unsigned int alt(void) const;
97  unsigned int truealt(void) const;
99  bool leftmost(void) const;
101  bool rightmost(void) const;
103  void next(void);
105  bool lao(void) const;
106 
108  unsigned int nid(void) const;
109 
111  void dispose(void);
112  };
113  protected:
117  unsigned int _ngdl;
118  public:
120  Path(unsigned int l);
122  unsigned int ngdl(void) const;
124  void ngdl(unsigned int l);
126  const Choice* push(Worker& stat, Space* s, Space* c, unsigned int nid);
128  void next(void);
130  Edge& top(void) const;
132  bool empty(void) const;
134  int lc(void) const;
136  void unwind(int l, Tracer& t);
138  void commit(Space* s, int i) const;
140  Space* recompute(unsigned int& d, unsigned int a_d, Worker& s,
141  Tracer& t);
143  Space* recompute(unsigned int& d, unsigned int a_d, Worker& s,
144  const Space& best, int& mark,
145  Tracer& t);
147  int entries(void) const;
149  void reset(void);
151  virtual void post(Space& home) const;
152  };
153 
154 }}}
155 
157 
158 #endif
159 
160 // STATISTICS: search-seq
Support::DynamicStack< Edge, Heap > ds
Stack to store edge information.
Definition: path.hh:115
NodeType t
Type of node.
Definition: bool-expr.cpp:234
unsigned int _ngdl
Depth limit for no-good generation.
Definition: path.hh:117
NNF * l
Left subtree.
Definition: bool-expr.cpp:244
void * mark(void *p)
Return marked pointer for unmarked pointer p.
Computation spaces.
Definition: core.hpp:1668
No-good propagator.
Definition: nogoods.hh:69
Gecode::IntSet d(v, 7)
Gecode::FloatVal c(-8, 8)
Gecode::IntArgs i(4, 1, 2, 3, 4)
Tracer::ID ID
Node identity type.
Definition: path.hh:68
const unsigned int a_d
Create a clone during recomputation if distance is greater than a_d (adaptive distance) ...
Definition: search.hh:117
const Choice * _choice
Choice.
Definition: path.hh:77
Search tree edge for recomputation
Definition: path.hh:70
Space * _space
Space corresponding to this edge (might be NULL)
Definition: path.hh:73
Search worker statistics
Definition: worker.hh:48
Depth-first path (stack of edges) supporting recomputation.
Definition: path.hh:64
Choice for performing commit
Definition: core.hpp:1338
No-goods recorded from restarts.
Definition: core.hpp:1514
Stack with arbitrary number of elements.
unsigned int _alt
Current alternative.
Definition: path.hh:75
Tracer.
Definition: tracer.hpp:153
Gecode toplevel namespace
#define GECODE_VTABLE_EXPORT
Definition: support.hh:76
ID _nid
Node identifier.
Definition: path.hh:79
TFE post(PropagatorGroup g)
Only post functions (but not propagators) from g are considered.
Definition: filter.cpp:142