Generated on Tue Jan 19 2021 06:15:49 for Gecode by doxygen 1.8.13
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, 2011
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 namespace Gecode { namespace Int { namespace NValues {
35 
38  : n_matched(0) {}
39 
40  forceinline int
41  Graph::size(void) const {
42  return n_matched;
43  }
44 
45  forceinline void
46  Graph::init(Space& home, const ValSet& vs, const ViewArray<IntView>& x) {
47  using namespace ViewValGraph;
48  n_view = x.size() + vs.size();
49  view = home.alloc<ViewNode<IntView>*>(n_view);
50 
51  // Create nodes corresponding to the value set vs
52  {
53  int i = x.size();
54  ValSet::Ranges vsr(vs);
55  ValNode<IntView>** v = &val;
56  for (Iter::Ranges::ToValues<ValSet::Ranges> n(vsr); n(); ++n) {
57  // Create view node
58  view[i] = new (home) ViewNode<IntView>();
59  // Create and link value node
60  ValNode<IntView>* nv = new (home) ValNode<IntView>(n.val());
61  *v = nv; v = nv->next_val_ref();
62  // Create and link single edge
63  Edge<IntView>** e = view[i]->val_edges_ref();
64  *e = new (home) Edge<IntView>(nv,view[i],NULL);
65  // Match edge
66  (*e)->revert(view[i]); nv->matching(*e);
67  i++;
68  }
69  *v = NULL;
70  n_val = vs.size();
71  n_matched = vs.size();
72  assert(i - x.size() == vs.size());
73  }
74 
75  // Initialize real view nodes
76  for (int i=0; i<x.size(); i++) {
77  view[i] = new (home) ViewNode<IntView>(x[i]);
79  }
80 
81  // Match the real view nodes, if possible
82  Region r;
83  ViewNodeStack m(r,n_view);
84  for (int i=0; i<x.size(); i++)
85  if (match(m,view[i]))
86  n_matched++;
87  }
88 
89  forceinline void
90  Graph::sync(void) {
91  using namespace ViewValGraph;
92  Region r;
93 
94  // Whether to rematch
95  bool rematch = false;
96 
97  // Synchronize nodes
98  for (int i=0; i<n_view; i++) {
99  ViewNode<IntView>* x = view[i];
100  // Skip faked view nodes, they correspond to values in the value set
101  if (!x->fake()) {
102  if (x->changed()) {
103  ViewRanges<IntView> rx(x->view());
104  Edge<IntView>* m = x->matched() ? x->edge_fst() : NULL;
105  Edge<IntView>** p = x->val_edges_ref();
106  Edge<IntView>* e = *p;
107  GECODE_ASSUME(e != NULL);
108  do {
109  while (e->val(x)->val() < rx.min()) {
110  // Skip edge
111  e->unlink(); e->mark();
112  e = e->next_edge();
113  }
114  *p = e;
115  assert(rx.min() == e->val(x)->val());
116  // This edges must be kept
117  for (unsigned int j=rx.width(); j--; ) {
118  e->free();
119  p = e->next_edge_ref();
120  e = e->next_edge();
121  }
122  ++rx;
123  } while (rx());
124  *p = NULL;
125  while (e != NULL) {
126  e->unlink(); e->mark();
127  e = e->next_edge();
128  }
129  if ((m != NULL) && m->marked()) {
130  // Matching has been deleted!
131  m->val(x)->matching(NULL);
132  rematch = true;
133  n_matched--;
134  }
135  } else {
136  // Just free edges
137  for (Edge<IntView>* e=x->val_edges(); e != NULL; e = e->next_edge())
138  e->free();
139  }
140  }
141  }
142 
143  if (rematch) {
144  ViewNodeStack m(r,n_view);
145  for (int i=0; i<n_view; i++)
146  if (!view[i]->matched() && match(m,view[i]))
147  n_matched++;
148  }
149  }
150 
151  forceinline bool
152  Graph::mark(void) {
153  using namespace ViewValGraph;
154  Region r;
155 
156  int n_view_visited = 0;
157  {
158  // Marks all edges as used that are on simple paths in the graph
159  // that start from a free value node by depth-first-search
161 
162  // Insert all free value nodes
163  count++;
164  {
165  ValNode<IntView>** v = &val;
166  while (*v != NULL)
167  // Is the node free?
168  if (!(*v)->matching()) {
169  // Eliminate empty value nodes
170  if ((*v)->empty()) {
171  *v = (*v)->next_val();
172  n_val--;
173  } else {
174  (*v)->min = count;
175  visit.push(*v);
176  v = (*v)->next_val_ref();
177  }
178  } else {
179  v = (*v)->next_val_ref();
180  }
181  }
182 
183  // Invariant: only value nodes are on the stack!
184  while (!visit.empty()) {
185  ValNode<IntView>* n = visit.pop();
186  for (Edge<IntView>* e = n->edge_fst(); e != n->edge_lst();
187  e = e->next()) {
188  // Is the view node is matched: the path must be alternating!
189  ViewNode<IntView>* x = e->view(n);
190  if (x->matched()) {
191  // Mark the edge as used
192  e->use();
193  if (x->min < count) {
194  n_view_visited++;
195  x->min = count;
196  assert(x->edge_fst()->next() == x->edge_lst());
197  ValNode<IntView>* m = x->edge_fst()->val(x);
198  x->edge_fst()->use();
199  if (m->min < count) {
200  m->min = count;
201  visit.push(m);
202  }
203  }
204  }
205  }
206  }
207 
208  }
209 
210  if (n_view_visited < n_view) {
211  // Mark all edges as used starting from a free view node on
212  // an alternating path by depth-first search.
214 
215  // Insert all free view nodes
216  count++;
217  for (int i=0; i<n_view; i++)
218  if (!view[i]->matched()) {
219  view[i]->min = count;
220  visit.push(view[i]);
221  }
222 
223  // Invariant: only view nodes are on the stack!
224  while (!visit.empty()) {
225  n_view_visited++;
226  ViewNode<IntView>* x = visit.pop();
227  for (Edge<IntView>* e = x->val_edges(); e != NULL; e = e->next_edge())
228  // Consider only free edges
229  if (e != x->edge_fst()) {
230  ValNode<IntView>* n = e->val(x);
231  // Is there a matched edge from the value node to a view node?
232  if (n->matching() != NULL) {
233  e->use();
234  n->matching()->use();
235  ViewNode<IntView>* y = n->matching()->view(n);
236  if (y->min < count) {
237  y->min = count;
238  visit.push(y);
239  }
240  }
241  }
242  }
243 
244  }
245 
246  if (n_view_visited < n_view) {
247  scc();
248  return true;
249  } else {
250  return false;
251  }
252  }
253 
256  using namespace ViewValGraph;
257  // Tell constraints and also eliminate nodes and edges
258  for (int i = n_view; i--; ) {
259  ViewNode<IntView>* x = view[i];
260  if (!x->fake()) {
261  if (x->matched() && !x->edge_fst()->used(x)) {
262  GECODE_ME_CHECK(x->view().eq(home,x->edge_fst()->val(x)->val()));
263  x->edge_fst()->val(x)->matching(NULL);
264  for (Edge<IntView>* e = x->val_edges(); e != NULL; e=e->next_edge())
265  e->unlink();
266  view[i] = view[--n_view];
267  } else {
268  IterPruneVal<IntView> pv(x);
269  GECODE_ME_CHECK(x->view().minus_v(home,pv,false));
270  }
271  }
272  }
273 
274  return ES_OK;
275  }
276 
277 }}}
278 
279 // STATISTICS: int-prop
280 
void push(const T &x)
Push element x on top of stack.
ViewNode< IntView > ** view
Array of view nodes.
int n_matched
Number of matched edges.
Definition: nvalues.hh:99
void sync(void)
Synchronize graph with new view domains.
Definition: graph.hpp:90
#define GECODE_ASSUME(p)
Assert certain property.
Definition: macros.hpp:114
ValNode< View > * next_val(void) const
Return next value node.
Definition: node.hpp:104
Graph(void)
Construct graph as not yet initialized.
Definition: graph.hpp:37
bool empty(void) const
Test whether stack is empty.
Range iterator for integer variable views
Definition: int.hpp:246
Handle to region.
Definition: region.hpp:55
#define forceinline
Definition: config.hpp:185
Computation spaces.
Definition: core.hpp:1701
T * alloc(long unsigned int n)
Allocate block of n objects of type T from space heap.
Definition: core.hpp:2794
int p
Number of positive literals for node type.
Definition: bool-expr.cpp:232
int n
Number of negative literals for node type.
Definition: bool-expr.cpp:234
Gecode::IntArgs i({1, 2, 3, 4})
Iterator over ranges.
Definition: val-set.hh:78
int size(void) const
Return size (number of values)
Definition: val-set.hpp:81
void revert(Node< View > *d)
Revert edge to node d for matching.
Definition: edge.hpp:57
Value iterator from range iterator.
void init(Space &home, ViewNode< View > *x)
Initialize the edges for the view node x.
Definition: graph.hpp:51
#define GECODE_ME_CHECK(me)
Check whether modification event me is failed, and forward failure.
Definition: macros.hpp:52
Post propagator for SetVar SetOpType SetVar SetRelType r
Definition: set.hh:767
const int v[7]
Definition: distinct.cpp:259
Post propagator for SetVar SetOpType SetVar y
Definition: set.hh:767
void scc(void)
Compute the strongly connected components.
Definition: graph.hpp:142
Edge< View > ** val_edges_ref(void)
Return pointer to first edge fields of all value edges.
Definition: node.hpp:135
ExecStatus
Definition: core.hpp:471
Stack with fixed number of elements.
ValNode< IntView > * val
Array of value nodes.
int size(void) const
Return size of maximal matching (excluding assigned views)
Definition: graph.hpp:41
T pop(void)
Pop topmost element from stack and return it.
Post propagator for SetVar x
Definition: set.hh:767
Execution is okay.
Definition: core.hpp:475
Class for storing values of already assigned views.
Definition: val-set.hh:44
Gecode toplevel namespace
bool match(ViewNodeStack &m, ViewNode< IntView > *x)
Find a matching for node x.
Definition: graph.hpp:87
int size(void) const
Return size of array (number of elements)
Definition: array.hpp:1138
void init(Space &home, const ValSet &vs, const ViewArray< IntView > &x)
Initialize graph including values in vs.
Definition: graph.hpp:46
ExecStatus prune(Space &home)
Prune all values corresponding to unused edges.
Definition: graph.hpp:255