Generated on Sat Jan 12 2019 20:58:51 for Gecode by doxygen 1.8.13
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  }
236  return Rel::Nq<IntView,IntView>::post(home,b[i],b[j]);
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();
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
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 
void push(const T &x)
Push element x on top of stack.
void free(void)
Free allocate memory.
Definition: region.hpp:356
bool adjacent(int i, int j) const
Test whether nodes i and j are adjacent.
void init(A &a, unsigned int sz, bool setbits=false)
Initialize for sz bits and allocator a (only after default constructor)
void empty(int n)
Clear the whole node set for n nodes.
static ExecStatus post(Home home, V0 x0, V1 x1)
Post propagator .
Definition: nq.hpp:49
int size(void) const
Return size of array (number of elements)
Definition: array.hpp:1569
bool in(int i) const
Test whether node i is included.
static const unsigned int bpb
Bits per base.
T * alloc(long unsigned int n)
Allocate block of n objects of type T from region.
Definition: region.hpp:386
Node * node
The nodes in the graph.
Definition: bin-packing.hh:240
unsigned int c
Cardinality of clique.
Definition: bin-packing.hh:273
bool pos(const View &x)
Test whether x is postive.
Definition: mult.hpp:41
bool empty(void) const
Test whether stack is empty.
static ExecStatus post(Home home, ViewArray< View > &x)
Post propagator for views x.
Definition: dom.hpp:45
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.
Handle to region.
Definition: region.hpp:55
#define forceinline
Definition: config.hpp:185
bool get(unsigned int i) const
Access value at bit i.
void copy(int n, const NodeSet &ns)
Copy elements from node set ns with n nodes.
void allocate(A &a, unsigned int sz)
Allocate for sz bits and allocator a (only after default constructor)
ExecStatus clique(void)
Report the current clique.
ExecStatus post(void)
Post additional constraints.
Gecode::IntSet d(v, 7)
#define GECODE_ES_CHECK(es)
Check whether execution status es is failed or subsumed, and forward failure or subsumption.
Definition: macros.hpp:91
Gecode::FloatVal c(-8, 8)
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
Gecode::IntArgs i({1, 2, 3, 4})
Execution has resulted in failure.
Definition: core.hpp:473
unsigned int next(unsigned int i) const
Return position greater or equal i of next set bit (i is allowed to be equal to size) ...
Nodes(const NodeSet &ns)
Initialize for nodes in ns.
bool none(unsigned int sz) const
Test whether no bits are set.
Clique(Region &r, int m)
Constructor for m nodes.
void o(BitSetData a)
Perform "or" with a.
void init(Region &r, int n)
Initialize node set for n nodes.
unsigned int w
Weight (initialized with degree before graph is reduced)
Definition: bin-packing.hh:235
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)
Integer sets.
Definition: int.hh:174
ExecStatus bk(NodeSet &p, NodeSet &x)
Run Bosch-Kerbron algorithm for finding max cliques.
void operator++(void)
Move iterator to next node (if possible)
Passing integer variables.
Definition: int.hh:656
int operator()(void) const
Return current node.
void init(bool setbits=false)
Initialize with all bits set if setbits.
Post propagator for SetVar SetOpType SetVar SetRelType r
Definition: set.hh:767
Example: Bin packing
IntSet maxclique(void) const
Return maximal clique found.
RawBitSetBase(void)
Default constructor (yields empty set)
ExecStatus
Definition: core.hpp:471
void a(BitSetData a)
Perform "and" with a.
Stack with fixed number of elements.
Date item for bitsets.
Definition: bitset-base.hpp:65
Clique max
Largest clique so far.
Definition: bin-packing.hh:296
T pop(void)
Pop topmost element from stack and return it.
int nodes(void) const
Return number of nodes.
Post propagator for SetVar x
Definition: set.hh:767
Execution is okay.
Definition: core.hpp:475
void allocate(Region &r, int n)
Allocate node set for n nodes.
const IntVarArgs & b
Bin variables.
Definition: bin-packing.hh:187
BitSetData * data
Stored bits.
Gecode toplevel namespace
unsigned int bins
Number of bins.
Definition: bin-packing.hh:189
Home class for posting propagators
Definition: core.hpp:853
bool none(void) const
Whether no bits are set.
#define GECODE_NEVER
Assert that this command is never executed.
Definition: macros.hpp:56
void incl(int i, unsigned int w)
Include node i with weight w.
void excl(int i, unsigned int w)
Exclude node i with weight w.
struct Gecode::@593::NNF::@62::@64 a
For atomic nodes.
static bool iwn(NodeSet &iwa, const NodeSet &a, NodeSet &iwb, const NodeSet &b, const NodeSet &c, int n)