Generated on Sat Feb 7 2015 02:01:19 for Gecode by doxygen 1.8.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  * Last modified:
12  * $Date: 2014-08-28 14:29:11 +0200 (Thu, 28 Aug 2014) $ by $Author: schulte $
13  * $Revision: 14203 $
14  *
15  * This file is part of Gecode, the generic constraint
16  * development environment:
17  * http://www.gecode.org
18  *
19  * Permission is hereby granted, free of charge, to any person obtaining
20  * a copy of this software and associated documentation files (the
21  * "Software"), to deal in the Software without restriction, including
22  * without limitation the rights to use, copy, modify, merge, publish,
23  * distribute, sublicense, and/or sell copies of the Software, and to
24  * permit persons to whom the Software is furnished to do so, subject to
25  * the following conditions:
26  *
27  * The above copyright notice and this permission notice shall be
28  * included in all copies or substantial portions of the Software.
29  *
30  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
31  * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
32  * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
33  * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
34  * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
35  * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
36  * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
37  *
38  */
39 
40 #include <gecode/int/rel.hh>
41 #include <gecode/int/distinct.hh>
42 
43 namespace Gecode { namespace Int { namespace BinPacking {
44 
45  forceinline int
46  ConflictGraph::nodes(void) const {
47  return b.size();
48  }
49 
54  : Support::RawBitSetBase(r,static_cast<unsigned int>(n)) {}
57  const NodeSet& ns)
58  : Support::RawBitSetBase(r,static_cast<unsigned int>(n),ns) {}
59  forceinline void
61  Support::RawBitSetBase::allocate(r,static_cast<unsigned int>(n));
62  }
63  forceinline void
65  Support::RawBitSetBase::init(r,static_cast<unsigned int>(n));
66  }
67  forceinline bool
69  return RawBitSetBase::get(static_cast<unsigned int>(i));
70  }
71  forceinline void
73  RawBitSetBase::set(static_cast<unsigned int>(i));
74  }
75  forceinline void
77  RawBitSetBase::clear(static_cast<unsigned int>(i));
78  }
79  forceinline void
81  RawBitSetBase::copy(static_cast<unsigned int>(n),ns);
82  }
83  forceinline void
85  RawBitSetBase::clearall(static_cast<unsigned int>(n));
86  }
87  forceinline bool
89  NodeSet& cwb, const NodeSet& b,
90  const NodeSet& c, int _n) {
91  unsigned int n = static_cast<unsigned int>(_n);
92  // This excludes the sentinel bit
93  unsigned int pos = n / bpb;
94  unsigned int bits = n % bpb;
95 
96  // Whether any bit is set
97  Support::BitSetData abc; abc.init();
98  for (unsigned int i=0; i<pos; i++) {
99  cwa.data[i] = Support::BitSetData::a(a.data[i],c.data[i]);
100  cwb.data[i] = Support::BitSetData::a(b.data[i],c.data[i]);
101  abc.o(cwa.data[i]);
102  abc.o(cwb.data[i]);
103  }
104  // Note that the sentinel bit is copied as well
105  cwa.data[pos] = Support::BitSetData::a(a.data[pos],c.data[pos]);
106  cwb.data[pos] = Support::BitSetData::a(b.data[pos],c.data[pos]);
107  abc.o(cwa.data[pos],bits);
108  abc.o(cwb.data[pos],bits);
109 
110  assert(cwa.get(n) && cwb.get(n));
111  return abc.none();
112  }
113 
114 
117 
120  : ns(ns0), c(ns.next(0)) {}
121  forceinline void
123  c = ns.next(c+1);
124  }
125  forceinline int
127  return static_cast<int>(c);
128  }
129 
132  : n(r,m), c(0), w(0) {}
133  forceinline void
134  ConflictGraph::Clique::incl(int i, unsigned int wi) {
135  n.incl(i); c++; w += wi;
136  }
137  forceinline void
138  ConflictGraph::Clique::excl(int i, unsigned int wi) {
139  n.excl(i); c--; w -= wi;
140  }
141 
144  const IntVarArgs& b0, int m)
145  : home(h), b(b0),
146  bins(static_cast<unsigned int>(m)),
147  node(reg.alloc<Node>(nodes())),
148  cur(reg,nodes()), max(reg,nodes()) {
149  for (int i=nodes(); i--; ) {
150  node[i].n.init(reg,nodes());
151  node[i].d=node[i].w=0;
152  }
153  }
154 
157  }
158 
159  forceinline void
160  ConflictGraph::edge(int i, int j, bool add) {
161  if (add) {
162  assert(!node[i].n.in(j) && !node[j].n.in(i));
163  node[i].n.incl(j); node[i].d++; node[i].w++;
164  node[j].n.incl(i); node[j].d++; node[j].w++;
165  } else {
166  assert(node[i].n.in(j) && node[j].n.in(i));
167  node[i].n.excl(j); node[i].d--;
168  node[j].n.excl(i); node[j].d--;
169  }
170  }
171 
172  forceinline bool
173  ConflictGraph::adjacent(int i, int j) const {
174  assert(node[i].n.in(j) == node[j].n.in(i));
175  return node[i].n.in(j);
176  }
177 
178  forceinline int
179  ConflictGraph::pivot(const NodeSet& a, const NodeSet& b) const {
180  Nodes i(a), j(b);
181  assert((i() < nodes()) || (j() < nodes()));
182  int p;
183  if (i() < nodes()) {
184  p = i(); ++i;
185  } else {
186  p = j(); ++j;
187  }
188  unsigned int m = node[p].d;
189  while (i() < nodes()) {
190  if (node[i()].d > m) {
191  p=i(); m=node[p].d;
192  }
193  ++i;
194  }
195  while (j() < nodes()) {
196  if (node[j()].d > m) {
197  p=j(); m=node[p].d;
198  }
199  ++j;
200  }
201  return p;
202  }
203 
206  // Remember clique
207  if ((cur.c > max.c) || ((cur.c == max.c) && (cur.w > max.w))) {
208  max.n.copy(nodes(),cur.n); max.c=cur.c; max.w=cur.w;
209  if (max.c > bins)
210  return ES_FAILED;
211  }
212  // Compute corresponding variables
214  int i=0;
215  for (Nodes c(cur.n); c() < nodes(); ++c)
216  bv[i++] = b[c()];
217  assert(i == static_cast<int>(cur.c));
219  }
220 
223  if (1 > max.c) {
224  assert(max.n.none(nodes()));
225  max.n.incl(i); max.c=1; max.w=0;
226  }
227  return ES_OK;
228  }
229 
231  ConflictGraph::clique(int i, int j) {
232  unsigned int w = node[i].w + node[j].w;
233  if ((2 > max.c) || ((2 == max.c) && (cur.w > max.w))) {
234  max.n.empty(nodes());
235  max.n.incl(i); max.n.incl(j);
236  max.c=2; max.w=w;
237  if (max.c > bins)
238  return ES_FAILED;
239  }
240  return Rel::Nq<IntView>::post(home,b[i],b[j]);
241  }
242 
244  ConflictGraph::clique(int i, int j, int k) {
245  unsigned int w = node[i].w + node[j].w + node[k].w;
246  if ((3 > max.c) || ((3 == max.c) && (cur.w > max.w))) {
247  max.n.empty(nodes());
248  max.n.incl(i); max.n.incl(j); max.n.incl(k);
249  max.c=3; max.w=w;
250  if (max.c > bins)
251  return ES_FAILED;
252  }
253  // Compute corresponding variables
254  ViewArray<IntView> bv(home,3);
255  bv[0]=b[i]; bv[1]=b[j]; bv[2]=b[k];
257  }
258 
261  // Find some simple cliques of sizes 2 and 3.
262  {
263  Region reg(home);
264  // Nodes can be entered twice (for degree 2 and later for degree 1)
266  // Make a copy of the degree information to be used as weights
267  // and record all nodes of degree 1 and 2.
268  for (int i=nodes(); i--; ) {
269  if ((node[i].d == 1) || (node[i].d == 2))
270  n.push(i);
271  }
272  while (!n.empty()) {
273  int i = n.pop();
274  switch (node[i].d) {
275  case 0:
276  // Might happen as the edges have already been removed
277  break;
278  case 1: {
279  Nodes ii(node[i].n);
280  int j=ii();
281  GECODE_ES_CHECK(clique(i,j));
282  // Remove edge
283  edge(i,j,false);
284  if ((node[j].d == 1) || (node[j].d == 2))
285  n.push(j);
286  break;
287  }
288  case 2: {
289  Nodes ii(node[i].n);
290  int j=ii(); ++ii;
291  int k=ii();
292  if (adjacent(j,k)) {
293  GECODE_ES_CHECK(clique(i,j,k));
294  // Can the edge j-k still be member of another clique?
295  if ((node[j].d == 2) || (node[k].d == 2))
296  edge(j,k,false);
297  } else {
298  GECODE_ES_CHECK(clique(i,j));
299  GECODE_ES_CHECK(clique(i,k));
300  }
301  edge(i,j,false);
302  edge(i,k,false);
303  if ((node[j].d == 1) || (node[j].d == 2))
304  n.push(j);
305  if ((node[k].d == 1) || (node[k].d == 2))
306  n.push(k);
307  break;
308  }
309  default: GECODE_NEVER;
310  }
311  }
312  }
313  // Initialize for Bron-Kerbosch
314  {
315  Region reg(home);
316  NodeSet p(reg,nodes()), x(reg,nodes());
317  bool empty = true;
318  for (int i=nodes(); i--; )
319  if (node[i].d > 0) {
320  p.incl(i); empty = false;
321  } else {
322  // Report clique of size 1
324  }
325  if (empty)
326  return ES_OK;
327  GECODE_ES_CHECK(bk(p,x));
328  }
329  return ES_OK;
330  }
331 
334  Region reg(home);
335  int* n=reg.alloc<int>(max.c);
336  int j=0;
337  for (Nodes i(max.n); i() < nodes(); ++i)
338  n[j++]=i();
339  assert(j == static_cast<int>(max.c));
340  IntSet s(n,max.c);
341  return s;
342  }
343 
344 }}}
345 
346 // STATISTICS: int-prop
347 
void push(const T &x)
Push element x on top of stack.
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.
int nodes(void) const
Return number of nodes.
int size(void) const
Return size of array (number of elements)
Definition: array.hpp:1662
T * alloc(long unsigned int n)
Allocate block of n objects of type T from region.
Definition: region.hpp:326
Node * node
The nodes in the graph.
Definition: bin-packing.hh:241
unsigned int c
Cardinality of clique.
Definition: bin-packing.hh:274
bool pos(const View &x)
Test whether x is postive.
Definition: mult.hpp:45
static ExecStatus post(Home home, ViewArray< View > &x)
Post propagator for views x.
Definition: dom.hpp:49
ConflictGraph(Space &home, Region &r, const IntVarArgs &b, int m)
Initialize graph.
Handle to region.
Definition: region.hpp:61
bool get(unsigned int i) const
Access value at bit i.
Computation spaces.
Definition: core.hpp:1362
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.
IntSet maxclique(void) const
Return maximal clique found.
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:84
Gecode::FloatVal c(-8, 8)
int p
Number of positive literals for node type.
Definition: bool-expr.cpp:236
bool empty(void) const
Test whether stack is empty.
Gecode::IntArgs i(4, 1, 2, 3, 4)
int n
Number of negative literals for node type.
Definition: bool-expr.cpp:238
Execution has resulted in failure.
Definition: core.hpp:525
NNF * r
Right subtree.
Definition: bool-expr.cpp:246
bool adjacent(int i, int j) const
Test whether nodes i and j are adjacent.
Nodes(const NodeSet &ns)
Initialize for nodes in ns.
Clique(Region &r, int m)
Constructor for m nodes.
bool none(unsigned int sz) const
Test whether no bits are set.
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:236
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:171
ExecStatus bk(NodeSet &p, NodeSet &x)
Run Bosch-Kerbron algorithm for finding max cliques.
void operator++(void)
Move iterator to next node (if possible)
bool in(int i) const
Test whether node i is included.
Passing integer variables.
Definition: int.hh:636
void init(bool setbits=false)
Initialize with all bits set if setbits.
Example: Bin packing
Node * x
Pointer to corresponding Boolean expression node.
Definition: bool-expr.cpp:253
ExecStatus
Definition: core.hpp:523
void a(BitSetData a)
Perform "and" with a.
#define forceinline
Definition: config.hpp:132
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:297
T pop(void)
Pop topmost element from stack and return it.
Execution is okay.
Definition: core.hpp:527
void allocate(Region &r, int n)
Allocate node set for n nodes.
bool none(void) const
Whether no bits are set.
const IntVarArgs & b
Bin variables.
Definition: bin-packing.hh:188
BitSetData * data
Stored bits.
struct Gecode::@518::NNF::@57::@58 b
For binary nodes (and, or, eqv)
Gecode toplevel namespace
int operator()(void) const
Return current node.
unsigned int bins
Number of bins.
Definition: bin-packing.hh:190
int pivot(const NodeSet &a, const NodeSet &b) const
Find a pivot node with maximal degree from a or b.
static ExecStatus post(Home home, View x0, View x1)
Post propagator .
Definition: nq.hpp:53
#define GECODE_NEVER
Assert that this command is never executed.
Definition: macros.hpp:60
void incl(int i, unsigned int w)
Include node i with weight w.
struct Gecode::@518::NNF::@57::@59 a
For atomic nodes.
void excl(int i, unsigned int w)
Exclude node i with weight w.
static bool iwn(NodeSet &iwa, const NodeSet &a, NodeSet &iwb, const NodeSet &b, const NodeSet &c, int n)