Generated on Sat Feb 7 2015 02:01:20 for Gecode by doxygen 1.8.9.1
base.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, 2007
8  *
9  * Last modified:
10  * $Date: 2012-09-07 17:31:22 +0200 (Fri, 07 Sep 2012) $ by $Author: schulte $
11  * $Revision: 13068 $
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 namespace Gecode { namespace Int { namespace Circuit {
39 
40  template<class View, class Offset>
43  : NaryPropagator<View,Int::PC_INT_DOM>(home,x), y(home,x), o(o0) {
44  home.notice(*this,AP_WEAKLY);
45  }
46 
47  template<class View, class Offset>
50  : NaryPropagator<View,Int::PC_INT_DOM>(home,share,p) {
51  o.update(p.o);
52  y.update(home,share,p.y);
53  }
54 
56  template<class View>
57  class SsccInfo {
58  public:
59  int min, low, pre;
61  };
62 
64  template<class View>
65  class TellInfo {
66  public:
67  View x; int n;
68  };
69 
70  template<class View, class Offset>
73  int n = x.size();
74 
76  int start = 0;
77  while (x[start].assigned()) {
78  start = o(x[start]).val();
79  if (start == 0) break;
80  }
81 
83  Region r(home);
84  typedef typename Offset::ViewType OView;
86  unsigned int n_edges = 0;
87  for (int i=n; i--; ) {
88  n_edges += x[i].size();
89  si[i].pre=-1;
90  }
91 
92  // Stack to remember which nodes have not been processed completely
94 
95  // Array to remember which mandatory tells need to be done
97  int n_eq = 0;
98 
99  // Array to remember which edges need to be pruned
100  TellInfo<OView>* nq = r.alloc<TellInfo<OView> >(n_edges);
101  int n_nq = 0;
102 
103  /*
104  * Check whether there is a single strongly connected component.
105  * This is a downstripped version of Tarjan's algorithm as
106  * the computation of sccs proper is not needed. In addition, it
107  * checks a mandatory condition for a graph to be Hamiltonian
108  * (due to Mats Carlsson).
109  *
110  * To quote Mats: Suppose you do a depth-first search of the graph.
111  * In that search, the root node will have a number of child subtrees
112  * T1, ..., Tn. By construction, if i<j then there is no edge from
113  * Ti to Tj. The necessary condition for Hamiltonianicity is that
114  * there be an edge from Ti+1 to Ti, for 0 < i < n.
115  *
116  * In addition, we do the following: if there is only a single edge
117  * from Ti+1 to Ti, then it must be mandatory and the variable must
118  * be assigned to that value.
119  *
120  * The same holds true for a back edge from T0 to the root node.
121  *
122  * Then, all edges that reach from Ti+k+1 to Ti can be pruned.
123  *
124  */
125 
126  {
127  // Start always at node start
128  int i = start;
129  // Counter for scc
130  int cnt = 0;
131  // Smallest preorder number of last subtree (initially, the root node)
132  int subtree_min = 0;
133  // Largest preorder number of last subtree (initially, the root node)
134  int subtree_max = 0;
135  // Number of back edges into last subtree or root
136  int back = 0;
137  start:
138  si[i].min = si[i].pre = si[i].low = cnt++;
139  si[i].v.init(o(x[i]));
140  do {
141  if (si[si[i].v.val()].pre < 0) {
142  next.push(i);
143  i=si[i].v.val();
144  goto start;
145  } else if ((subtree_min <= si[si[i].v.val()].pre) &&
146  (si[si[i].v.val()].pre <= subtree_max)) {
147  back++;
148  eq[n_eq].x = o(x[i]);
149  eq[n_eq].n = si[i].v.val();
150  } else if (si[si[i].v.val()].pre < subtree_min) {
151  nq[n_nq].x = o(x[i]);
152  nq[n_nq].n = si[i].v.val();
153  n_nq++;
154  }
155  cont:
156  if (si[si[i].v.val()].low < si[i].min)
157  si[i].min = si[si[i].v.val()].low;
158  ++si[i].v;
159  } while (si[i].v());
160  if (si[i].min < si[i].low) {
161  si[i].low = si[i].min;
162  } else if (i != start) {
163  // If it is not the first node visited, there is more than one SCC
164  return ES_FAILED;
165  }
166  if (!next.empty()) {
167  i=next.pop();
168  if (i == start) {
169  // No back edge
170  if (back == 0)
171  return ES_FAILED;
172  // Exactly one back edge, make it mandatory (keep topmost entry)
173  if (back == 1)
174  n_eq++;
175  back = 0;
176  subtree_min = subtree_max+1;
177  subtree_max = cnt-1;
178  }
179  goto cont;
180  }
181  // Whether all nodes have been visited
182  if (cnt != n)
183  return ES_FAILED;
184  ExecStatus es = ES_FIX;
185  // Assign all mandatory edges
186  while (n_eq-- > 0) {
187  ModEvent me = eq[n_eq].x.eq(home,eq[n_eq].n);
188  if (me_failed(me))
189  return ES_FAILED;
190  if (me_modified(me))
191  es = ES_NOFIX;
192  }
193  // Remove all edges that would require a non-simple cycle
194  while (n_nq-- > 0) {
195  ModEvent me = nq[n_nq].x.nq(home,nq[n_nq].n);
196  if (me_failed(me))
197  return ES_FAILED;
198  if (me_modified(me))
199  es = ES_NOFIX;
200  }
201  return es;
202  }
203  }
204 
205  template<class View, class Offset>
206  ExecStatus
208  // Prunes that partial assigned paths are not completed to cycles
209 
210  int n=x.size();
211 
212  Region r(home);
213 
214  // The path starting at assigned x[i] ends at x[end[j]] which is
215  // not assigned.
216  int* end = r.alloc<int>(n);
217  for (int i=n; i--; )
218  end[i]=-1;
219 
220  // A stack that records all indices i such that end[i] != -1
222 
223  typedef typename Offset::ViewType OView;
224  for (int i=y.size(); i--; ) {
225  assert(!y[i].assigned());
226  // Non-assigned views serve as starting points for assigned paths
227  Int::ViewValues<OView> v(o(y[i]));
228  // Try all connected values
229  do {
230  int j0=v.val();
231  // Starting point for not yet followed assigned path found
232  if (x[j0].assigned() && (end[j0] < 0)) {
233  // Follow assigned path until non-assigned view:
234  // all assigned view on the paths can be skipped, as
235  // if x[i] is assigned to j, then x[j] will only have
236  // x[i] as predecessor due to propagating distinct.
237  int j = j0;
238  do {
239  j=o(x[j]).val();
240  } while (x[j].assigned());
241  // Now there cannot be a cycle from x[j] to x[v.val()]!
242  // However, the tell cannot be done here as j might be
243  // equal to i and might hence kill the iterator v!
244  end[j0]=j; tell.push(j0);
245  }
246  ++v;
247  } while (v());
248  }
249 
250  // Now do the tells based on the end information
251  while (!tell.empty()) {
252  int i = tell.pop();
253  assert(end[i] >= 0);
254  GECODE_ME_CHECK(o(x[end[i]]).nq(home,i));
255  }
256  return ES_NOFIX;
257  }
258 
259  template<class View, class Offset>
260  forceinline size_t
262  home.ignore(*this,AP_WEAKLY);
264  return sizeof(*this);
265  }
266 
267 }}}
268 
269 // STATISTICS: int-prop
270 
void push(const T &x)
Push element x on top of stack.
const SetInstr * si[]
Definition: mm-set.cpp:4340
int size(void) const
Return size of array (number of elements)
Definition: array.hpp:1662
Offset o
Offset transformation.
Definition: circuit.hh:65
T * alloc(long unsigned int n)
Allocate block of n objects of type T from region.
Definition: region.hpp:326
ExecStatus path(Space &home)
Ensure path property: prune edges that could give to small cycles.
Definition: base.hpp:207
int ModEvent
Type for modification events.
Definition: core.hpp:146
ExecStatus connected(Space &home)
Check whether the view value graph is strongly connected.
Definition: base.hpp:72
Handle to region.
Definition: region.hpp:61
Value iterator for integer views.
Definition: view.hpp:94
Propagation has computed fixpoint.
Definition: core.hpp:528
Computation spaces.
Definition: core.hpp:1362
int p
Number of positive literals for node type.
Definition: bool-expr.cpp:236
bool empty(void) const
Test whether stack is empty.
Information required for non-recursive checking for a single scc.
Definition: base.hpp:57
Gecode::IntArgs i(4, 1, 2, 3, 4)
int n
Number of negative literals for node type.
Definition: bool-expr.cpp:238
Execution has resulted in failure.
Definition: core.hpp:525
NNF * r
Right subtree.
Definition: bool-expr.cpp:246
const Gecode::PropCond PC_INT_DOM
Propagate when domain changes.
Definition: var-type.hpp:100
n-ary propagator
Definition: propagator.hpp:143
ViewArray< View > y
Array for performing value propagation for distinct.
Definition: circuit.hh:63
Offset integer view.
Definition: view.hpp:422
void update(const Offset &o)
Update during cloning.
Definition: view.hpp:637
View arrays.
Definition: array.hpp:234
#define GECODE_ME_CHECK(me)
Check whether modification event me is failed, and forward failure.
Definition: macros.hpp:45
void notice(Actor &a, ActorProperty p, bool duplicate=false)
Notice actor property.
Definition: core.hpp:2849
Converter with fixed offset.
Definition: view.hpp:617
const int v[7]
Definition: distinct.cpp:207
void min(Home home, FloatVar x0, FloatVar x1, FloatVar x2)
Post propagator for .
Definition: arithmetic.cpp:75
Node * x
Pointer to corresponding Boolean expression node.
Definition: bool-expr.cpp:253
void ignore(Actor &a, ActorProperty p, bool duplicate=false)
Ignore actor property.
Definition: core.cpp:169
Base(Space &home, bool share, Base &p)
Constructor for cloning p.
ExecStatus
Definition: core.hpp:523
bool assigned(View x, int v)
Whether x is assigned to value v.
Definition: single.hpp:47
#define forceinline
Definition: config.hpp:132
Stack with fixed number of elements.
bool me_modified(ModEvent me)
Check whether modification event me describes variable modification.
Definition: modevent.hpp:63
T pop(void)
Pop topmost element from stack and return it.
Propagation has not computed fixpoint.
Definition: core.hpp:526
int val(void) const
Return current value.
Gecode toplevel namespace
Home class for posting propagators
Definition: core.hpp:717
Base-class for circuit propagator.
Definition: circuit.hh:59
Int::ViewValues< View > v
Definition: base.hpp:60
bool me_failed(ModEvent me)
Check whether modification event me is failed.
Definition: modevent.hpp:58
virtual size_t dispose(Space &home)
Delete propagator and return its size.
Definition: base.hpp:261
Information for performing a recorded tell.
Definition: base.hpp:65