conflict-graph.hpp
Go to the documentation of this file.
/* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
/*
* Main authors:
* Christian Schulte <schulte@gecode.org>
* Stefano Gualandi <stefano.gualandi@gmail.com>
*
* Copyright:
* Stefano Gualandi, 2013
* Christian Schulte, 2014
*
* This file is part of Gecode, the generic constraint
* development environment:
* http://www.gecode.org
*
* Permission is hereby granted, free of charge, to any person obtaining
* a copy of this software and associated documentation files (the
* "Software"), to deal in the Software without restriction, including
* without limitation the rights to use, copy, modify, merge, publish,
* distribute, sublicense, and/or sell copies of the Software, and to
* permit persons to whom the Software is furnished to do so, subject to
* the following conditions:
*
* The above copyright notice and this permission notice shall be
* included in all copies or substantial portions of the Software.
*
* THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
* EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
* MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
* NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
* LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
* OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
* WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
*
*/
#include <gecode/int/rel.hh>
#include <gecode/int/distinct.hh>
namespace Gecode { namespace Int { namespace BinPacking {
forceinline int
ConflictGraph::nodes(void) const {
return b.size();
}
forceinline
ConflictGraph::NodeSet::NodeSet(void) {}
forceinline
ConflictGraph::NodeSet::NodeSet(Region& r, int n)
: Support::RawBitSetBase(r,static_cast<unsigned int>(n)) {}
forceinline
ConflictGraph::NodeSet::NodeSet(Region& r, int n,
const NodeSet& ns)
: Support::RawBitSetBase(r,static_cast<unsigned int>(n),ns) {}
forceinline void
ConflictGraph::NodeSet::allocate(Region& r, int n) {
Support::RawBitSetBase::allocate(r,static_cast<unsigned int>(n));
}
forceinline void
ConflictGraph::NodeSet::init(Region& r, int n) {
Support::RawBitSetBase::init(r,static_cast<unsigned int>(n));
}
forceinline bool
ConflictGraph::NodeSet::in(int i) const {
return RawBitSetBase::get(static_cast<unsigned int>(i));
}
forceinline void
ConflictGraph::NodeSet::incl(int i) {
RawBitSetBase::set(static_cast<unsigned int>(i));
}
forceinline void
ConflictGraph::NodeSet::excl(int i) {
RawBitSetBase::clear(static_cast<unsigned int>(i));
}
forceinline void
ConflictGraph::NodeSet::copy(int n, const NodeSet& ns) {
RawBitSetBase::copy(static_cast<unsigned int>(n),ns);
}
forceinline void
ConflictGraph::NodeSet::empty(int n) {
RawBitSetBase::clearall(static_cast<unsigned int>(n));
}
forceinline bool
ConflictGraph::NodeSet::iwn(NodeSet& cwa, const NodeSet& a,
NodeSet& cwb, const NodeSet& b,
const NodeSet& c, int _n) {
unsigned int n = static_cast<unsigned int>(_n);
// This excludes the sentinel bit
unsigned int pos = n / bpb;
unsigned int bits = n % bpb;
// Whether any bit is set
Support::BitSetData abc; abc.init();
for (unsigned int i=0; i<pos; i++) {
cwa.data[i] = Support::BitSetData::a(a.data[i],c.data[i]);
cwb.data[i] = Support::BitSetData::a(b.data[i],c.data[i]);
abc.o(cwa.data[i]);
abc.o(cwb.data[i]);
}
// Note that the sentinel bit is copied as well
cwa.data[pos] = Support::BitSetData::a(a.data[pos],c.data[pos]);
cwb.data[pos] = Support::BitSetData::a(b.data[pos],c.data[pos]);
abc.o(cwa.data[pos],bits);
abc.o(cwb.data[pos],bits);
assert(cwa.get(n) && cwb.get(n));
return abc.none();
}
forceinline
ConflictGraph::Node::Node(void) {}
forceinline
ConflictGraph::Nodes::Nodes(const NodeSet& ns0)
: ns(ns0), c(ns.next(0)) {}
forceinline void
ConflictGraph::Nodes::operator ++(void) {
c = ns.next(c+1);
}
forceinline int
ConflictGraph::Nodes::operator ()(void) const {
return static_cast<int>(c);
}
forceinline
ConflictGraph::Clique::Clique(Region& r, int m)
: n(r,m), c(0), w(0) {}
forceinline void
ConflictGraph::Clique::incl(int i, unsigned int wi) {
n.incl(i); c++; w += wi;
}
forceinline void
ConflictGraph::Clique::excl(int i, unsigned int wi) {
n.excl(i); c--; w -= wi;
}
forceinline
ConflictGraph::ConflictGraph(Home& h, Region& reg,
const IntVarArgs& b0, int m)
: home(h), b(b0),
bins(static_cast<unsigned int>(m)),
node(reg.alloc<Node>(nodes())),
cur(reg,nodes()), max(reg,nodes()) {
for (int i=0; i<nodes(); i++) {
node[i].n.init(reg,nodes());
node[i].d=node[i].w=0;
}
}
forceinline
ConflictGraph::~ConflictGraph(void) {
}
forceinline void
ConflictGraph::edge(int i, int j, bool add) {
if (add) {
assert(!node[i].n.in(j) && !node[j].n.in(i));
node[i].n.incl(j); node[i].d++; node[i].w++;
node[j].n.incl(i); node[j].d++; node[j].w++;
} else {
assert(node[i].n.in(j) && node[j].n.in(i));
node[i].n.excl(j); node[i].d--;
node[j].n.excl(i); node[j].d--;
}
}
forceinline bool
ConflictGraph::adjacent(int i, int j) const {
assert(node[i].n.in(j) == node[j].n.in(i));
return node[i].n.in(j);
}
forceinline int
ConflictGraph::pivot(const NodeSet& a, const NodeSet& b) const {
Nodes i(a), j(b);
assert((i() < nodes()) || (j() < nodes()));
int p;
if (i() < nodes()) {
p = i(); ++i;
} else {
p = j(); ++j;
}
unsigned int m = node[p].d;
while (i() < nodes()) {
if (node[i()].d > m) {
p=i(); m=node[p].d;
}
++i;
}
while (j() < nodes()) {
if (node[j()].d > m) {
p=j(); m=node[p].d;
}
++j;
}
return p;
}
forceinline ExecStatus
ConflictGraph::clique(void) {
// Remember clique
if ((cur.c > max.c) || ((cur.c == max.c) && (cur.w > max.w))) {
max.n.copy(nodes(),cur.n); max.c=cur.c; max.w=cur.w;
if (max.c > bins)
return ES_FAILED;
}
// Compute corresponding variables
ViewArray<IntView> bv(home,static_cast<int>(cur.c));
int i=0;
for (Nodes c(cur.n); c() < nodes(); ++c)
bv[i++] = b[c()];
assert(i == static_cast<int>(cur.c));
return Distinct::Dom<IntView>::post(home,bv);
}
forceinline ExecStatus
ConflictGraph::clique(int i) {
if (1 > max.c) {
assert(max.n.none(nodes()));
max.n.incl(i); max.c=1; max.w=0;
}
return ES_OK;
}
forceinline ExecStatus
ConflictGraph::clique(int i, int j) {
unsigned int w = node[i].w + node[j].w;
if ((2 > max.c) || ((2 == max.c) && (cur.w > max.w))) {
max.n.empty(nodes());
max.n.incl(i); max.n.incl(j);
max.c=2; max.w=w;
if (max.c > bins)
return ES_FAILED;
}
return Rel::Nq<IntView,IntView>::post(home,b[i],b[j]);
}
forceinline ExecStatus
ConflictGraph::clique(int i, int j, int k) {
unsigned int w = node[i].w + node[j].w + node[k].w;
if ((3 > max.c) || ((3 == max.c) && (cur.w > max.w))) {
max.n.empty(nodes());
max.n.incl(i); max.n.incl(j); max.n.incl(k);
max.c=3; max.w=w;
if (max.c > bins)
return ES_FAILED;
}
// Compute corresponding variables
ViewArray<IntView> bv(home,3);
bv[0]=b[i]; bv[1]=b[j]; bv[2]=b[k];
return Distinct::Dom<IntView>::post(home,bv);
}
forceinline ExecStatus
ConflictGraph::post(void) {
// Find some simple cliques of sizes 2 and 3.
Region reg;
{
// Nodes can be entered twice (for degree 2 and later for degree 1)
Support::StaticStack<int,Region> n(reg,2*nodes());
// Make a copy of the degree information to be used as weights
// and record all nodes of degree 1 and 2.
for (int i=0; i<nodes(); i++) {
if ((node[i].d == 1) || (node[i].d == 2))
n.push(i);
}
while (!n.empty()) {
int i = n.pop();
switch (node[i].d) {
case 0:
// Might happen as the edges have already been removed
break;
case 1: {
Nodes ii(node[i].n);
int j=ii();
GECODE_ES_CHECK(clique(i,j));
// Remove edge
edge(i,j,false);
if ((node[j].d == 1) || (node[j].d == 2))
n.push(j);
break;
}
case 2: {
Nodes ii(node[i].n);
int j=ii(); ++ii;
int k=ii();
if (adjacent(j,k)) {
GECODE_ES_CHECK(clique(i,j,k));
// Can the edge j-k still be member of another clique?
if ((node[j].d == 2) || (node[k].d == 2))
edge(j,k,false);
} else {
GECODE_ES_CHECK(clique(i,j));
GECODE_ES_CHECK(clique(i,k));
}
edge(i,j,false);
edge(i,k,false);
if ((node[j].d == 1) || (node[j].d == 2))
n.push(j);
if ((node[k].d == 1) || (node[k].d == 2))
n.push(k);
break;
}
default: GECODE_NEVER;
}
}
reg.free();
}
// Initialize for Bron-Kerbosch
{
NodeSet p(reg,nodes()), x(reg,nodes());
bool empty = true;
for (int i=0; i<nodes(); i++)
if (node[i].d > 0) {
p.incl(i); empty = false;
} else {
// Report clique of size 1
GECODE_ES_CHECK(clique(i));
}
if (empty)
return ES_OK;
GECODE_ES_CHECK(bk(p,x));
reg.free();
}
return ES_OK;
}
inline IntSet
ConflictGraph::maxclique(void) const {
Region reg;
int* n=reg.alloc<int>(max.c);
int j=0;
for (Nodes i(max.n); i() < nodes(); ++i)
n[j++]=i();
assert(j == static_cast<int>(max.c));
IntSet s(n,static_cast<int>(max.c));
return s;
}
}}}
// STATISTICS: int-prop
Gecode::Home
Home class for posting propagators
Definition core.hpp:856
Gecode::IntSet
Integer sets.
Definition int.hh:174
Gecode::IntVarArgs
Passing integer variables.
Definition int.hh:656
Gecode::Int::BinPacking::ConflictGraph::Clique::Clique
Clique(Region &r, int m)
Constructor for m nodes.
Definition conflict-graph.hpp:127
Gecode::Int::BinPacking::ConflictGraph::Clique::excl
void excl(int i, unsigned int w)
Exclude node i with weight w.
Definition conflict-graph.hpp:134
Gecode::Int::BinPacking::ConflictGraph::Clique::n
NodeSet n
Nodes in the clique.
Definition bin-packing.hh:271
Gecode::Int::BinPacking::ConflictGraph::Clique::incl
void incl(int i, unsigned int w)
Include node i with weight w.
Definition conflict-graph.hpp:130
Gecode::Int::BinPacking::ConflictGraph::Clique::c
unsigned int c
Cardinality of clique.
Definition bin-packing.hh:273
Gecode::Int::BinPacking::ConflictGraph::Clique::w
unsigned int w
Weight of clique.
Definition bin-packing.hh:275
Gecode::Int::BinPacking::ConflictGraph::NodeSet
Sets of graph nodes.
Definition bin-packing.hh:194
Gecode::Int::BinPacking::ConflictGraph::NodeSet::empty
void empty(int n)
Clear the whole node set for n nodes.
Definition conflict-graph.hpp:80
Gecode::Int::BinPacking::ConflictGraph::NodeSet::incl
void incl(int i)
Include node i.
Definition conflict-graph.hpp:68
Gecode::Int::BinPacking::ConflictGraph::NodeSet::NodeSet
NodeSet(void)
Keep uninitialized.
Definition conflict-graph.hpp:47
Gecode::Int::BinPacking::ConflictGraph::NodeSet::iwn
static bool iwn(NodeSet &iwa, const NodeSet &a, NodeSet &iwb, const NodeSet &b, const NodeSet &c, int n)
Definition conflict-graph.hpp:84
Gecode::Int::BinPacking::ConflictGraph::NodeSet::init
void init(Region &r, int n)
Initialize node set for n nodes.
Definition conflict-graph.hpp:60
Gecode::Int::BinPacking::ConflictGraph::NodeSet::in
bool in(int i) const
Test whether node i is included.
Definition conflict-graph.hpp:64
Gecode::Int::BinPacking::ConflictGraph::NodeSet::allocate
void allocate(Region &r, int n)
Allocate node set for n nodes.
Definition conflict-graph.hpp:56
Gecode::Int::BinPacking::ConflictGraph::NodeSet::copy
void copy(int n, const NodeSet &ns)
Copy elements from node set ns with n nodes.
Definition conflict-graph.hpp:76
Gecode::Int::BinPacking::ConflictGraph::NodeSet::excl
void excl(int i)
Exclude node i.
Definition conflict-graph.hpp:72
Gecode::Int::BinPacking::ConflictGraph::Node
Class for node in graph.
Definition bin-packing.hh:228
Gecode::Int::BinPacking::ConflictGraph::Node::Node
Node(void)
Default constructor.
Definition conflict-graph.hpp:112
Gecode::Int::BinPacking::ConflictGraph::Nodes
Iterator over node sets.
Definition bin-packing.hh:243
Gecode::Int::BinPacking::ConflictGraph::Nodes::operator++
void operator++(void)
Move iterator to next node (if possible).
Definition conflict-graph.hpp:118
Gecode::Int::BinPacking::ConflictGraph::Nodes::Nodes
Nodes(const NodeSet &ns)
Initialize for nodes in ns.
Definition conflict-graph.hpp:115
Gecode::Int::BinPacking::ConflictGraph::Nodes::operator()
int operator()(void) const
Return current node.
Definition conflict-graph.hpp:122
Gecode::Int::BinPacking::ConflictGraph::cur
Clique cur
Current clique.
Definition bin-packing.hh:294
Gecode::Int::BinPacking::ConflictGraph::clique
ExecStatus clique(void)
Report the current clique.
Definition conflict-graph.hpp:201
Gecode::Int::BinPacking::ConflictGraph::nodes
int nodes(void) const
Return number of nodes.
Definition conflict-graph.hpp:42
Gecode::Int::BinPacking::ConflictGraph::post
ExecStatus post(void)
Post additional constraints.
Definition conflict-graph.hpp:256
Gecode::Int::BinPacking::ConflictGraph::ConflictGraph
ConflictGraph(Home &home, Region &r, const IntVarArgs &b, int m)
Initialize graph.
Definition conflict-graph.hpp:139
Gecode::Int::BinPacking::ConflictGraph::home
Home & home
Home space.
Definition bin-packing.hh:185
Gecode::Int::BinPacking::ConflictGraph::pivot
int pivot(const NodeSet &a, const NodeSet &b) const
Find a pivot node with maximal degree from a or b.
Definition conflict-graph.hpp:175
Gecode::Int::BinPacking::ConflictGraph::~ConflictGraph
~ConflictGraph(void)
Destructor.
Definition conflict-graph.hpp:152
Gecode::Int::BinPacking::ConflictGraph::adjacent
bool adjacent(int i, int j) const
Test whether nodes i and j are adjacent.
Definition conflict-graph.hpp:169
Gecode::Int::BinPacking::ConflictGraph::node
Node * node
The nodes in the graph.
Definition bin-packing.hh:240
Gecode::Int::BinPacking::ConflictGraph::bk
ExecStatus bk(NodeSet &p, NodeSet &x)
Run Bosch-Kerbron algorithm for finding max cliques.
Definition conflict-graph.cpp:39
Gecode::Int::BinPacking::ConflictGraph::bins
unsigned int bins
Number of bins.
Definition bin-packing.hh:189
Gecode::Int::BinPacking::ConflictGraph::edge
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).
Definition conflict-graph.hpp:156
Gecode::Int::BinPacking::ConflictGraph::b
const IntVarArgs & b
Bin variables.
Definition bin-packing.hh:187
Gecode::Int::BinPacking::ConflictGraph::max
Clique max
Largest clique so far.
Definition bin-packing.hh:296
Gecode::Int::BinPacking::ConflictGraph::maxclique
IntSet maxclique(void) const
Return maximal clique found.
Definition conflict-graph.hpp:330
Gecode::Int::Distinct::Dom::post
static ExecStatus post(Home home, ViewArray< View > &x)
Post propagator for views x.
Definition dom.hpp:45
Gecode::Int::Rel::Nq::post
static ExecStatus post(Home home, V0 x0, V1 x1)
Post propagator .
Definition nq.hpp:49
Gecode::Region
Handle to region.
Definition region.hpp:55
Gecode::Region::free
void free(void)
Free allocate memory.
Definition region.hpp:356
Gecode::Region::alloc
T * alloc(long unsigned int n)
Allocate block of n objects of type T from region.
Definition region.hpp:386
Gecode::Support::BitSetData
Date item for bitsets.
Definition bitset-base.hpp:65
Gecode::Support::BitSetData::init
void init(bool setbits=false)
Initialize with all bits set if setbits.
Definition bitset-base.hpp:246
Gecode::Support::BitSetData::a
void a(BitSetData a)
Perform "and" with a.
Definition bitset-base.hpp:346
Gecode::Support::BitSetData::none
bool none(void) const
Whether no bits are set.
Definition bitset-base.hpp:303
Gecode::Support::BitSetData::o
void o(BitSetData a)
Perform "or" with a.
Definition bitset-base.hpp:362
Gecode::Support::RawBitSetBase::get
bool get(unsigned int i) const
Access value at bit i.
Definition bitset-base.hpp:399
Gecode::Support::RawBitSetBase::init
void init(A &a, unsigned int sz, bool setbits=false)
Initialize for sz bits and allocator a (only after default constructor).
Definition bitset-base.hpp:469
Gecode::Support::RawBitSetBase::bpb
static const unsigned int bpb
Bits per base.
Definition bitset-base.hpp:140
Gecode::Support::RawBitSetBase::allocate
void allocate(A &a, unsigned int sz)
Allocate for sz bits and allocator a (only after default constructor).
Definition bitset-base.hpp:462
Gecode::Support::RawBitSetBase::data
BitSetData * data
Stored bits.
Definition bitset-base.hpp:142
Gecode::Support::StaticStack
Stack with fixed number of elements.
Definition static-stack.hpp:42
Gecode::Support::StaticStack::push
void push(const T &x)
Push element x on top of stack.
Definition static-stack.hpp:137
Gecode::Support::StaticStack::pop
T pop(void)
Pop topmost element from stack and return it.
Definition static-stack.hpp:116
Gecode::Support::StaticStack::empty
bool empty(void) const
Test whether stack is empty.
Definition static-stack.hpp:98
Gecode::ViewArray
View arrays.
Definition array.hpp:253
GECODE_ES_CHECK
#define GECODE_ES_CHECK(es)
Check whether execution status es is failed or subsumed, and forward failure or subsumption.
Definition macros.hpp:91
distinct.hh
rel.hh
Gecode::Int::BinPacking
Bin-packing propagators
Gecode::Int
Finite domain integers.
Gecode::Support
Support algorithms and datastructures
Gecode
Gecode toplevel namespace
Gecode::ExecStatus
ExecStatus
Definition core.hpp:472
Gecode::ES_OK
@ ES_OK
Execution is okay.
Definition core.hpp:476
Gecode::ES_FAILED
@ ES_FAILED
Execution has resulted in failure.
Definition core.hpp:474
forceinline
#define forceinline
Definition config.hpp:187
GECODE_NEVER
#define GECODE_NEVER
Assert that this command is never executed.
Definition macros.hpp:56