Generated on Thu Jan 16 2025 00:00:00 for Gecode by doxygen 1.14.0
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
36namespace 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
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
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
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 }
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 }
237
238 template<class View>
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(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
Graph(void)
Construct graph as not yet initialized.
Definition graph.hpp:40
bool mark(void)
Mark edges in graph, return true if pruning is at all possible.
Definition graph.hpp:176
bool sync(void)
Synchronize graph with new view domains.
Definition graph.hpp:112
ExecStatus init(Space &home, ViewArray< View > &x)
Initialize graph.
Definition graph.hpp:44
ExecStatus prune(Space &home, bool &assigned)
Prune unmarked edges, assigned is true if a view got assigned.
Definition graph.hpp:240
Range iterator for integer views.
Definition view.hpp:54
int min(void) const
Return smallest value of range.
unsigned int width(void) const
Return width of range (distance between minimum and maximum)
Support::StaticStack< ViewNode< View > *, Region > ViewNodeStack
Stack used during matching.
void init(Space &home, ViewNode< View > *x)
Initialize the edges for the view node x.
Definition graph.hpp:51
unsigned int count
Marking counter.
ViewNode< View > ** view
Array of view nodes.
bool match(ViewNodeStack &m, ViewNode< View > *x)
Find a matching for node x.
Definition graph.hpp:87
int n_view
Number of view nodes.
int n_val
Number of value nodes.
void scc(void)
Compute the strongly connected components.
Definition graph.hpp:142
ValNode< View > * val
Array of value nodes.
Value iterator for integer views.
Definition view.hpp:94
Handle to region.
Definition region.hpp:55
Computation spaces.
Definition core.hpp:1744
T * alloc(long unsigned int n)
Allocate block of n objects of type T from space heap.
Definition core.hpp:2841
Stack with fixed number of elements.
void push(const T &x)
Push element x on top of stack.
T pop(void)
Pop topmost element from stack and return it.
bool empty(void) const
Test whether stack is empty.
View arrays.
Definition array.hpp:253
#define GECODE_ME_CHECK(me)
Check whether modification event me is failed, and forward failure.
Definition macros.hpp:52
Distinct propagators
Support classes for propagators using a view-value graph.
Finite domain integers.
Gecode toplevel namespace
Post propagator for SetVar SetOpType SetVar SetRelType r
Definition set.hh:773
void min(Home home, FloatVar x0, FloatVar x1, FloatVar x2)
Post propagator for .
ExecStatus
Definition core.hpp:472
@ ES_OK
Execution is okay.
Definition core.hpp:476
@ ES_FAILED
Execution has resulted in failure.
Definition core.hpp:474
void max(Home home, FloatVar x0, FloatVar x1, FloatVar x2)
Post propagator for .
Post propagator for SetVar x
Definition set.hh:773
#define forceinline
Definition config.hpp:194
#define GECODE_ASSUME(p)
Assert certain property.
Definition macros.hpp:114