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, 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
36namespace Gecode { namespace Int { namespace Distinct {
37
38 template<class View>
39 forceinline
40 Graph<View>::Graph(void) {}
41
42 template<class View>
43 forceinline ExecStatus
44 Graph<View>::init(Space& home, ViewArray<View>& x) {
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]=nullptr;
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] == nullptr)
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 = nullptr;
85 }
86
87 for (unsigned int i=width; i--; )
88 if (val2node[i] != nullptr) {
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++)
97 ViewValGraph::Graph<View>::init(home,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
112 Graph<View>::sync(void) {
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 != nullptr);
121 if (x->view().assigned()) {
122 x->edge_fst()->val(x)->matching(nullptr);
123 for (Edge<View>* e = x->val_edges(); e != nullptr; 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 != nullptr);
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 = nullptr;
149 while (e != nullptr) {
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(nullptr);
156 re.push(x);
157 }
158 x->update();
159 } else {
160 // Just free edges
161 for (Edge<View>* e = x->val_edges(); e != nullptr; 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
176 Graph<View>::mark(void) {
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
185 Support::StaticStack<ValNode<View>*,Region> visit(r,n_val);
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 != nullptr)
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>
239 forceinline ExecStatus
240 Graph<View>::prune(Space& home, bool& assigned) {
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(nullptr);
249 for (Edge<View>* e = x->val_edges(); e != nullptr; 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