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