Something went wrong. Try again.
This repository has no description
Something went wrong. Try again.
10 kB · 344 lines
C++
at develop
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345/* -*- 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