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 * Stefano Gualandi <stefano.gualandi@gmail.com>
6 *
7 * Copyright:
8 * Stefano Gualandi, 2013
9 * Christian Schulte, 2014
10 *
11 * This file is part of Gecode, the generic constraint
12 * development environment:
13 * http://www.gecode.org
14 *
15 * Permission is hereby granted, free of charge, to any person obtaining
16 * a copy of this software and associated documentation files (the
17 * "Software"), to deal in the Software without restriction, including
18 * without limitation the rights to use, copy, modify, merge, publish,
19 * distribute, sublicense, and/or sell copies of the Software, and to
20 * permit persons to whom the Software is furnished to do so, subject to
21 * the following conditions:
22 *
23 * The above copyright notice and this permission notice shall be
24 * included in all copies or substantial portions of the Software.
25 *
26 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
27 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
28 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
29 * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
30 * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
31 * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
32 * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
33 *
34 */
35
36#include <gecode/int/rel.hh>
37#include <gecode/int/distinct.hh>
38
39namespace Gecode { namespace Int { namespace BinPacking {
40
41 forceinline int
42 ConflictGraph::nodes(void) const {
43 return b.size();
44 }
45
46 forceinline
47 ConflictGraph::NodeSet::NodeSet(void) {}
48 forceinline
49 ConflictGraph::NodeSet::NodeSet(Region& r, int n)
50 : Support::RawBitSetBase(r,static_cast<unsigned int>(n)) {}
51 forceinline
52 ConflictGraph::NodeSet::NodeSet(Region& r, int n,
53 const NodeSet& ns)
54 : Support::RawBitSetBase(r,static_cast<unsigned int>(n),ns) {}
55 forceinline void
56 ConflictGraph::NodeSet::allocate(Region& r, int n) {
57 Support::RawBitSetBase::allocate(r,static_cast<unsigned int>(n));
58 }
59 forceinline void
60 ConflictGraph::NodeSet::init(Region& r, int n) {
61 Support::RawBitSetBase::init(r,static_cast<unsigned int>(n));
62 }
63 forceinline bool
64 ConflictGraph::NodeSet::in(int i) const {
65 return RawBitSetBase::get(static_cast<unsigned int>(i));
66 }
67 forceinline void
68 ConflictGraph::NodeSet::incl(int i) {
69 RawBitSetBase::set(static_cast<unsigned int>(i));
70 }
71 forceinline void
72 ConflictGraph::NodeSet::excl(int i) {
73 RawBitSetBase::clear(static_cast<unsigned int>(i));
74 }
75 forceinline void
76 ConflictGraph::NodeSet::copy(int n, const NodeSet& ns) {
77 RawBitSetBase::copy(static_cast<unsigned int>(n),ns);
78 }
79 forceinline void
80 ConflictGraph::NodeSet::empty(int n) {
81 RawBitSetBase::clearall(static_cast<unsigned int>(n));
82 }
83 forceinline bool
84 ConflictGraph::NodeSet::iwn(NodeSet& cwa, const NodeSet& a,
85 NodeSet& cwb, const NodeSet& b,
86 const NodeSet& c, int _n) {
87 unsigned int n = static_cast<unsigned int>(_n);
88 // This excludes the sentinel bit
89 unsigned int pos = n / bpb;
90 unsigned int bits = n % bpb;
91
92 // Whether any bit is set
93 Support::BitSetData abc; abc.init();
94 for (unsigned int i=0; i<pos; i++) {
95 cwa.data[i] = Support::BitSetData::a(a.data[i],c.data[i]);
96 cwb.data[i] = Support::BitSetData::a(b.data[i],c.data[i]);
97 abc.o(cwa.data[i]);
98 abc.o(cwb.data[i]);
99 }
100 // Note that the sentinel bit is copied as well
101 cwa.data[pos] = Support::BitSetData::a(a.data[pos],c.data[pos]);
102 cwb.data[pos] = Support::BitSetData::a(b.data[pos],c.data[pos]);
103 abc.o(cwa.data[pos],bits);
104 abc.o(cwb.data[pos],bits);
105
106 assert(cwa.get(n) && cwb.get(n));
107 return abc.none();
108 }
109
110
111 forceinline
112 ConflictGraph::Node::Node(void) {}
113
114 forceinline
115 ConflictGraph::Nodes::Nodes(const NodeSet& ns0)
116 : ns(ns0), c(ns.next(0)) {}
117 forceinline void
118 ConflictGraph::Nodes::operator ++(void) {
119 c = ns.next(c+1);
120 }
121 forceinline int
122 ConflictGraph::Nodes::operator ()(void) const {
123 return static_cast<int>(c);
124 }
125
126 forceinline
127 ConflictGraph::Clique::Clique(Region& r, int m)
128 : n(r,m), c(0), w(0) {}
129 forceinline void
130 ConflictGraph::Clique::incl(int i, unsigned int wi) {
131 n.incl(i); c++; w += wi;
132 }
133 forceinline void
134 ConflictGraph::Clique::excl(int i, unsigned int wi) {
135 n.excl(i); c--; w -= wi;
136 }
137
138 forceinline
139 ConflictGraph::ConflictGraph(Home& h, Region& reg,
140 const IntVarArgs& b0, int m)
141 : home(h), b(b0),
142 bins(static_cast<unsigned int>(m)),
143 node(reg.alloc<Node>(nodes())),
144 cur(reg,nodes()), max(reg,nodes()) {
145 for (int i=0; i<nodes(); i++) {
146 node[i].n.init(reg,nodes());
147 node[i].d=node[i].w=0;
148 }
149 }
150
151 forceinline
152 ConflictGraph::~ConflictGraph(void) {
153 }
154
155 forceinline void
156 ConflictGraph::edge(int i, int j, bool add) {
157 if (add) {
158 assert(!node[i].n.in(j) && !node[j].n.in(i));
159 node[i].n.incl(j); node[i].d++; node[i].w++;
160 node[j].n.incl(i); node[j].d++; node[j].w++;
161 } else {
162 assert(node[i].n.in(j) && node[j].n.in(i));
163 node[i].n.excl(j); node[i].d--;
164 node[j].n.excl(i); node[j].d--;
165 }
166 }
167
168 forceinline bool
169 ConflictGraph::adjacent(int i, int j) const {
170 assert(node[i].n.in(j) == node[j].n.in(i));
171 return node[i].n.in(j);
172 }
173
174 forceinline int
175 ConflictGraph::pivot(const NodeSet& a, const NodeSet& b) const {
176 Nodes i(a), j(b);
177 assert((i() < nodes()) || (j() < nodes()));
178 int p;
179 if (i() < nodes()) {
180 p = i(); ++i;
181 } else {
182 p = j(); ++j;
183 }
184 unsigned int m = node[p].d;
185 while (i() < nodes()) {
186 if (node[i()].d > m) {
187 p=i(); m=node[p].d;
188 }
189 ++i;
190 }
191 while (j() < nodes()) {
192 if (node[j()].d > m) {
193 p=j(); m=node[p].d;
194 }
195 ++j;
196 }
197 return p;
198 }
199
200 forceinline ExecStatus
201 ConflictGraph::clique(void) {
202 // Remember clique
203 if ((cur.c > max.c) || ((cur.c == max.c) && (cur.w > max.w))) {
204 max.n.copy(nodes(),cur.n); max.c=cur.c; max.w=cur.w;
205 if (max.c > bins)
206 return ES_FAILED;
207 }
208 // Compute corresponding variables
209 ViewArray<IntView> bv(home,static_cast<int>(cur.c));
210 int i=0;
211 for (Nodes c(cur.n); c() < nodes(); ++c)
212 bv[i++] = b[c()];
213 assert(i == static_cast<int>(cur.c));
214 return Distinct::Dom<IntView>::post(home,bv);
215 }
216
217 forceinline ExecStatus
218 ConflictGraph::clique(int i) {
219 if (1 > max.c) {
220 assert(max.n.none(nodes()));
221 max.n.incl(i); max.c=1; max.w=0;
222 }
223 return ES_OK;
224 }
225
226 forceinline ExecStatus
227 ConflictGraph::clique(int i, int j) {
228 unsigned int w = node[i].w + node[j].w;
229 if ((2 > max.c) || ((2 == max.c) && (cur.w > max.w))) {
230 max.n.empty(nodes());
231 max.n.incl(i); max.n.incl(j);
232 max.c=2; max.w=w;
233 if (max.c > bins)
234 return ES_FAILED;
235 }
236 return Rel::Nq<IntView,IntView>::post(home,b[i],b[j]);
237 }
238
239 forceinline ExecStatus
240 ConflictGraph::clique(int i, int j, int k) {
241 unsigned int w = node[i].w + node[j].w + node[k].w;
242 if ((3 > max.c) || ((3 == max.c) && (cur.w > max.w))) {
243 max.n.empty(nodes());
244 max.n.incl(i); max.n.incl(j); max.n.incl(k);
245 max.c=3; max.w=w;
246 if (max.c > bins)
247 return ES_FAILED;
248 }
249 // Compute corresponding variables
250 ViewArray<IntView> bv(home,3);
251 bv[0]=b[i]; bv[1]=b[j]; bv[2]=b[k];
252 return Distinct::Dom<IntView>::post(home,bv);
253 }
254
255 forceinline ExecStatus
256 ConflictGraph::post(void) {
257 // Find some simple cliques of sizes 2 and 3.
258 Region reg;
259 {
260 // Nodes can be entered twice (for degree 2 and later for degree 1)
261 Support::StaticStack<int,Region> n(reg,2*nodes());
262 // Make a copy of the degree information to be used as weights
263 // and record all nodes of degree 1 and 2.
264 for (int i=0; i<nodes(); i++) {
265 if ((node[i].d == 1) || (node[i].d == 2))
266 n.push(i);
267 }
268 while (!n.empty()) {
269 int i = n.pop();
270 switch (node[i].d) {
271 case 0:
272 // Might happen as the edges have already been removed
273 break;
274 case 1: {
275 Nodes ii(node[i].n);
276 int j=ii();
277 GECODE_ES_CHECK(clique(i,j));
278 // Remove edge
279 edge(i,j,false);
280 if ((node[j].d == 1) || (node[j].d == 2))
281 n.push(j);
282 break;
283 }
284 case 2: {
285 Nodes ii(node[i].n);
286 int j=ii(); ++ii;
287 int k=ii();
288 if (adjacent(j,k)) {
289 GECODE_ES_CHECK(clique(i,j,k));
290 // Can the edge j-k still be member of another clique?
291 if ((node[j].d == 2) || (node[k].d == 2))
292 edge(j,k,false);
293 } else {
294 GECODE_ES_CHECK(clique(i,j));
295 GECODE_ES_CHECK(clique(i,k));
296 }
297 edge(i,j,false);
298 edge(i,k,false);
299 if ((node[j].d == 1) || (node[j].d == 2))
300 n.push(j);
301 if ((node[k].d == 1) || (node[k].d == 2))
302 n.push(k);
303 break;
304 }
305 default: GECODE_NEVER;
306 }
307 }
308 reg.free();
309 }
310 // Initialize for Bron-Kerbosch
311 {
312 NodeSet p(reg,nodes()), x(reg,nodes());
313 bool empty = true;
314 for (int i=0; i<nodes(); i++)
315 if (node[i].d > 0) {
316 p.incl(i); empty = false;
317 } else {
318 // Report clique of size 1
319 GECODE_ES_CHECK(clique(i));
320 }
321 if (empty)
322 return ES_OK;
323 GECODE_ES_CHECK(bk(p,x));
324 reg.free();
325 }
326 return ES_OK;
327 }
328
329 inline IntSet
330 ConflictGraph::maxclique(void) const {
331 Region reg;
332 int* n=reg.alloc<int>(max.c);
333 int j=0;
334 for (Nodes i(max.n); i() < nodes(); ++i)
335 n[j++]=i();
336 assert(j == static_cast<int>(max.c));
337 IntSet s(n,static_cast<int>(max.c));
338 return s;
339 }
340
341}}}
342
343// STATISTICS: int-prop
344