this repo has no description
dekker.one
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
34namespace Gecode { namespace Int { namespace NValues {
35
36 forceinline
37 Graph::Graph(void)
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],nullptr);
65 // Match edge
66 (*e)->revert(view[i]); nv->matching(*e);
67 i++;
68 }
69 *v = nullptr;
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]);
78 ViewValGraph::Graph<IntView>::init(home,view[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() : nullptr;
105 Edge<IntView>** p = x->val_edges_ref();
106 Edge<IntView>* e = *p;
107 GECODE_ASSUME(e != nullptr);
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 = nullptr;
125 while (e != nullptr) {
126 e->unlink(); e->mark();
127 e = e->next_edge();
128 }
129 if ((m != nullptr) && m->marked()) {
130 // Matching has been deleted!
131 m->val(x)->matching(nullptr);
132 rematch = true;
133 n_matched--;
134 }
135 } else {
136 // Just free edges
137 for (Edge<IntView>* e=x->val_edges(); e != nullptr; 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
160 Support::StaticStack<ValNode<IntView>*,Region> visit(r,n_val);
161
162 // Insert all free value nodes
163 count++;
164 {
165 ValNode<IntView>** v = &val;
166 while (*v != nullptr)
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.
213 Support::StaticStack<ViewNode<IntView>*,Region> visit(r,n_view);
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 != nullptr; 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() != nullptr) {
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
254 forceinline ExecStatus
255 Graph::prune(Space& home) {
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(nullptr);
264 for (Edge<IntView>* e = x->val_edges(); e != nullptr; 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