Generated on Sat Feb 7 2015 02:01:22 for Gecode by doxygen 1.8.9.1
graph.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, 2003
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 #include <climits>
39 
40 namespace Gecode { namespace Int { namespace Distinct {
41 
42  template<class View>
45 
46  template<class View>
49  using namespace ViewValGraph;
50  n_view = x.size();
51  view = home.alloc<ViewNode<View>*>(n_view);
52 
53  // Find value information for construction of view value graph
54  int min = x[n_view-1].min();
55  int max = x[n_view-1].max();
56  for (int i=n_view-1; i--; ) {
57  min = std::min(min,x[i].min());
58  max = std::max(max,x[i].max());
59  }
60 
61  unsigned int width = static_cast<unsigned int>(max-min+1);
62 
63  // Definitly not enough values
64  if (width < static_cast<unsigned int>(n_view))
65  return ES_FAILED;
66 
67  // Initialize view nodes
68  for (int i=n_view; i--; )
69  view[i] = new (home) ViewNode<View>(x[i]);
70 
71  Region r(home);
72 
73  if (static_cast<unsigned int>(n_view)*4 >= width) {
74  // Values are dense: use a mapping
75  ValNode<View>** val2node = r.alloc<ValNode<View>* >(width);
76 
77  for (unsigned int i=width; i--; )
78  val2node[i]=NULL;
79 
80  for (int i=n_view; i--; ) {
81  Edge<View>** edge_p = view[i]->val_edges_ref();
82  for (ViewValues<View> xi(x[i]); xi(); ++xi) {
83  if (val2node[xi.val()-min] == NULL)
84  val2node[xi.val()-min] = new (home) ValNode<View>(xi.val());
85  *edge_p = new (home) Edge<View>(val2node[xi.val()-min],view[i]);
86  edge_p = (*edge_p)->next_edge_ref();
87  }
88  *edge_p = NULL;
89  }
90 
91  for (unsigned int i=width; i--; )
92  if (val2node[i] != NULL) {
93  val2node[i]->next_val(val);
94  val = val2node[i];
95  n_val++;
96  }
97 
98  } else {
99  // Values are sparse
100  for (int i=n_view; i--; )
102  }
103 
104  if (n_val < n_view)
105  return ES_FAILED;
106 
107  typename ViewValGraph::Graph<View>::ViewNodeStack m(r,n_view);
108  for (int i = n_view; i--; )
109  if (!match(m,view[i]))
110  return ES_FAILED;
111  return ES_OK;
112  }
113 
114  template<class View>
115  forceinline bool
117  using namespace ViewValGraph;
118  Region r(home);
119  // Stack for view nodes to be rematched
120  typename ViewValGraph::Graph<View>::ViewNodeStack re(r,n_view);
121  // Synchronize nodes
122  for (int i = n_view; i--; ) {
123  ViewNode<View>* x = view[i];
124  if (x->view().assigned()) {
125  x->edge_fst()->val(x)->matching(NULL);
126  for (Edge<View>* e = x->val_edges(); e != NULL; e = e->next_edge())
127  e->unlink();
128  view[i] = view[--n_view];
129  } else if (x->changed()) {
130  ViewRanges<View> r(x->view());
131  Edge<View>* m = x->edge_fst(); // Matching edge
132  Edge<View>** p = x->val_edges_ref();
133  Edge<View>* e = *p;
134  do {
135  while (e->val(x)->val() < r.min()) {
136  // Skip edge
137  e->unlink(); e->mark();
138  e = e->next_edge();
139  }
140  *p = e;
141  assert(r.min() == e->val(x)->val());
142  // This edges must be kept
143  for (unsigned int j=r.width(); j--; ) {
144  e->free();
145  p = e->next_edge_ref();
146  e = e->next_edge();
147  }
148  ++r;
149  } while (r());
150  *p = NULL;
151  while (e != NULL) {
152  e->unlink(); e->mark();
153  e = e->next_edge();
154  }
155  if (m->marked()) {
156  // Matching has been deleted!
157  m->val(x)->matching(NULL);
158  re.push(x);
159  }
160  x->update();
161  } else {
162  // Just free edges
163  for (Edge<View>* e = x->val_edges(); e != NULL; e = e->next_edge())
164  e->free();
165  }
166  }
167 
168  typename ViewValGraph::Graph<View>::ViewNodeStack m(r,n_view);
169  while (!re.empty())
170  if (!match(m,re.pop()))
171  return false;
172  return true;
173  }
174 
175 
176  template<class View>
177  forceinline bool
179  using namespace ViewValGraph;
180 
181  Region r(home);
182 
183  int n_view_visited = 0;
184  {
185  // Marks all edges as used that are on simple paths in the graph
186  // that start from a free (unmatched node) by depth-first-search
188 
189  // Insert all free nodes: they can be only value nodes as we
190  // have a maximum matching covering all view nodes
191  count++;
192  {
193  ValNode<View>** v = &val;
194  while (*v != NULL)
195  if (!(*v)->matching()) {
196  if ((*v)->empty()) {
197  *v = (*v)->next_val();
198  n_val--;
199  } else {
200  (*v)->min = count;
201  visit.push(*v);
202  v = (*v)->next_val_ref();
203  }
204  } else {
205  v = (*v)->next_val_ref();
206  }
207  }
208 
209  // Invariant: only value nodes are on the stack!
210  while (!visit.empty()) {
211  ValNode<View>* n = visit.pop();
212  for (Edge<View>* e = n->edge_fst(); e != n->edge_lst(); e=e->next()) {
213  // Get the value node
214  e->use();
215  ViewNode<View>* x = e->view(n);
216  if (x->min < count) {
217  n_view_visited++;
218  x->min = count;
219  assert(x->edge_fst()->next() == x->edge_lst());
220  ValNode<View>* m = x->edge_fst()->val(x);
221  x->edge_fst()->use();
222  if (m->min < count) {
223  m->min = count;
224  visit.push(m);
225  }
226  }
227  }
228  }
229  }
230 
231  // If all view nodes have been visited, also all edges are used!
232  if (n_view_visited < n_view) {
233  scc(home);
234  return true;
235  } else {
236  return false;
237  }
238  }
239 
240  template<class View>
243  using namespace ViewValGraph;
244  assigned = false;
245  // Tell constraints and also eliminate nodes and edges
246  for (int i = n_view; i--; ) {
247  ViewNode<View>* x = view[i];
248  if (!x->edge_fst()->used(x)) {
249  GECODE_ME_CHECK(x->view().eq(home,x->edge_fst()->val(x)->val()));
250  x->edge_fst()->val(x)->matching(NULL);
251  for (Edge<View>* e = x->val_edges(); e != NULL; e = e->next_edge())
252  e->unlink();
253  view[i] = view[--n_view];
254  assigned = true;
255  } else {
256  IterPruneVal<View> pv(view[i]);
257  GECODE_ME_CHECK(view[i]->view().minus_v(home,pv,false));
258  }
259  }
260  return ES_OK;
261  }
262 
263 }}}
264 
265 // STATISTICS: int-prop
266 
void push(const T &x)
Push element x on top of stack.
bool mark(Space &home)
Mark edges in graph, return true if pruning is at all possible.
Definition: graph.hpp:178
const FloatNum max
Largest allowed float value.
Definition: float.hh:831
void max(Home home, FloatVar x0, FloatVar x1, FloatVar x2)
Post propagator for .
Definition: arithmetic.cpp:57
ExecStatus prune(Space &home, bool &assigned)
Prune unmarked edges, assigned is true if a view got assigned.
Definition: graph.hpp:242
Handle to region.
Definition: region.hpp:61
Value iterator for integer views.
Definition: view.hpp:94
Computation spaces.
Definition: core.hpp:1362
Range iterator for integer views.
Definition: view.hpp:54
T * alloc(long unsigned int n)
Allocate block of n objects of type T from space heap.
Definition: core.hpp:2397
ExecStatus init(Space &home, ViewArray< View > &x)
Initialize graph.
Definition: graph.hpp:48
int p
Number of positive literals for node type.
Definition: bool-expr.cpp:236
bool empty(void) const
Test whether stack is empty.
Graph(void)
Construct graph as not yet initialized.
Definition: graph.hpp:44
const FloatNum min
Smallest allowed float value.
Definition: float.hh:833
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
View arrays.
Definition: array.hpp:234
View-value graph base class.
#define GECODE_ME_CHECK(me)
Check whether modification event me is failed, and forward failure.
Definition: macros.hpp:45
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 count(Home home, const IntVarArgs &x, int n, IntRelType irt, int m, IntConLevel)
Post propagator for .
Definition: count.cpp:44
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.
T pop(void)
Pop topmost element from stack and return it.
Execution is okay.
Definition: core.hpp:527
int size(void) const
Return size of array (number of elements)
Definition: array.hpp:1215
Gecode toplevel namespace
bool sync(Space &home)
Synchronize graph with new view domains.
Definition: graph.hpp:116