Generated on Tue Feb 11 2025 17:33:26 for Gecode by doxygen 1.12.0
conflict-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 * 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>
38
39namespace Gecode { namespace Int { namespace BinPacking {
40
41 forceinline int
43 return b.size();
44 }
45
50 : Support::RawBitSetBase(r,static_cast<unsigned int>(n)) {}
53 const NodeSet& ns)
54 : Support::RawBitSetBase(r,static_cast<unsigned int>(n),ns) {}
55 forceinline void
57 Support::RawBitSetBase::allocate(r,static_cast<unsigned int>(n));
58 }
59 forceinline void
61 Support::RawBitSetBase::init(r,static_cast<unsigned int>(n));
62 }
63 forceinline bool
65 return RawBitSetBase::get(static_cast<unsigned int>(i));
66 }
67 forceinline void
69 RawBitSetBase::set(static_cast<unsigned int>(i));
70 }
71 forceinline void
73 RawBitSetBase::clear(static_cast<unsigned int>(i));
74 }
75 forceinline void
77 RawBitSetBase::copy(static_cast<unsigned int>(n),ns);
78 }
79 forceinline void
81 RawBitSetBase::clearall(static_cast<unsigned int>(n));
82 }
83 forceinline bool
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
113
116 : ns(ns0), c(ns.next(0)) {}
117 forceinline void
119 c = ns.next(c+1);
120 }
121 forceinline int
123 return static_cast<int>(c);
124 }
125
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
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
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
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));
215 }
216
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
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 }
237 }
238
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
251 bv[0]=b[i]; bv[1]=b[j]; bv[2]=b[k];
253 }
254
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)
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();
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 {
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
320 }
321 if (empty)
322 return ES_OK;
324 reg.free();
325 }
326 return ES_OK;
327 }
328
329 inline IntSet
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
struct Gecode::@603::NNF::@65::@66 b
For binary nodes (and, or, eqv)
int p
Number of positive literals for node type.
int n
Number of negative literals for node type.
struct Gecode::@603::NNF::@65::@67 a
For atomic nodes.
Example: Bin packing
int size(void) const
Return size of array (number of elements)
Definition array.hpp:1607
Home class for posting propagators
Definition core.hpp:856
Integer sets.
Definition int.hh:174
Passing integer variables.
Definition int.hh:656
Clique(Region &r, int m)
Constructor for m nodes.
void excl(int i, unsigned int w)
Exclude node i with weight w.
void incl(int i, unsigned int w)
Include node i with weight w.
unsigned int c
Cardinality of clique.
void empty(int n)
Clear the whole node set for n nodes.
static bool iwn(NodeSet &iwa, const NodeSet &a, NodeSet &iwb, const NodeSet &b, const NodeSet &c, int n)
void init(Region &r, int n)
Initialize node set for n nodes.
bool in(int i) const
Test whether node i is included.
void allocate(Region &r, int n)
Allocate node set for n nodes.
void copy(int n, const NodeSet &ns)
Copy elements from node set ns with n nodes.
unsigned int w
Weight (initialized with degree before graph is reduced)
void operator++(void)
Move iterator to next node (if possible)
Nodes(const NodeSet &ns)
Initialize for nodes in ns.
int operator()(void) const
Return current node.
ExecStatus clique(void)
Report the current clique.
int nodes(void) const
Return number of nodes.
ExecStatus post(void)
Post additional constraints.
ConflictGraph(Home &home, Region &r, const IntVarArgs &b, int m)
Initialize graph.
int pivot(const NodeSet &a, const NodeSet &b) const
Find a pivot node with maximal degree from a or b.
bool adjacent(int i, int j) const
Test whether nodes i and j are adjacent.
Node * node
The nodes in the graph.
ExecStatus bk(NodeSet &p, NodeSet &x)
Run Bosch-Kerbron algorithm for finding max cliques.
unsigned int bins
Number of bins.
void edge(int i, int j, bool add=true)
Add or remove an edge between nodes i and j (i must be less than j)
const IntVarArgs & b
Bin variables.
Clique max
Largest clique so far.
IntSet maxclique(void) const
Return maximal clique found.
static ExecStatus post(Home home, ViewArray< View > &x)
Post propagator for views x.
Definition dom.hpp:45
static ExecStatus post(Home home, V0 x0, V1 x1)
Post propagator .
Definition nq.hpp:49
Handle to region.
Definition region.hpp:55
void free(void)
Free allocate memory.
Definition region.hpp:356
T * alloc(long unsigned int n)
Allocate block of n objects of type T from region.
Definition region.hpp:386
Date item for bitsets.
void init(bool setbits=false)
Initialize with all bits set if setbits.
void a(BitSetData a)
Perform "and" with a.
bool none(void) const
Whether no bits are set.
void o(BitSetData a)
Perform "or" with a.
bool get(unsigned int i) const
Access value at bit i.
void init(A &a, unsigned int sz, bool setbits=false)
Initialize for sz bits and allocator a (only after default constructor)
void allocate(A &a, unsigned int sz)
Allocate for sz bits and allocator a (only after default constructor)
bool none(unsigned int sz) const
Test whether no bits are set.
BitSetData * data
Stored bits.
Stack with fixed number of elements.
View arrays.
Definition array.hpp:253
#define GECODE_ES_CHECK(es)
Check whether execution status es is failed or subsumed, and forward failure or subsumption.
Definition macros.hpp:91
Gecode toplevel namespace
Post propagator for SetVar SetOpType SetVar SetRelType r
Definition set.hh:767
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
Post propagator for SetVar x
Definition set.hh:767
#define forceinline
Definition config.hpp:187
#define GECODE_NEVER
Assert that this command is never executed.
Definition macros.hpp:56