Generated on Wed Jul 21 2021 00:00:00 for Gecode by doxygen 1.9.1
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>
37 #include <gecode/int/distinct.hh>
38 
39 namespace Gecode { namespace Int { namespace BinPacking {
40 
41  forceinline int
42  ConflictGraph::nodes(void) const {
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 
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 
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
250  ViewArray<IntView> bv(home,3);
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;
323  GECODE_ES_CHECK(bk(p,x));
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::@602::NNF::@65::@66 b
For binary nodes (and, or, eqv)
int p
Number of positive literals for node type.
Definition: bool-expr.cpp:232
int n
Number of negative literals for node type.
Definition: bool-expr.cpp:234
Node * x
Pointer to corresponding Boolean expression node.
Definition: bool-expr.cpp:249
struct Gecode::@602::NNF::@65::@67 a
For atomic nodes.
NNF * r
Right subtree.
Definition: bool-expr.cpp:242
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.
Definition: bin-packing.hh:273
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)
Definition: bin-packing.hh:235
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.
Definition: bin-packing.hh:240
ExecStatus bk(NodeSet &p, NodeSet &x)
Run Bosch-Kerbron algorithm for finding max cliques.
unsigned int bins
Number of bins.
Definition: bin-packing.hh:189
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.
Definition: bin-packing.hh:187
Clique max
Largest clique so far.
Definition: bin-packing.hh:296
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.
Definition: bitset-base.hpp:65
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
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
#define GECODE_ES_CHECK(es)
Check whether execution status es is failed or subsumed, and forward failure or subsumption.
Definition: macros.hpp:91
bool pos(const View &x)
Test whether x is postive.
Definition: mult.hpp:41
Gecode::FloatVal c(-8, 8)
Gecode::IntArgs i({1, 2, 3, 4})
Gecode::IntSet d(v, 7)
#define forceinline
Definition: config.hpp:192
#define GECODE_NEVER
Assert that this command is never executed.
Definition: macros.hpp:56