Generated on Fri Oct 19 11:25:01 2018 for Gecode by doxygen 1.6.3

conflict-graph.hpp

Go to the documentation of this file.
00001 /* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
00002 /*
00003  *  Main authors:
00004  *     Christian Schulte <schulte@gecode.org>
00005  *     Stefano Gualandi <stefano.gualandi@gmail.com>
00006  *
00007  *  Copyright:
00008  *     Stefano Gualandi, 2013
00009  *     Christian Schulte, 2014
00010  *
00011  *  This file is part of Gecode, the generic constraint
00012  *  development environment:
00013  *     http://www.gecode.org
00014  *
00015  *  Permission is hereby granted, free of charge, to any person obtaining
00016  *  a copy of this software and associated documentation files (the
00017  *  "Software"), to deal in the Software without restriction, including
00018  *  without limitation the rights to use, copy, modify, merge, publish,
00019  *  distribute, sublicense, and/or sell copies of the Software, and to
00020  *  permit persons to whom the Software is furnished to do so, subject to
00021  *  the following conditions:
00022  *
00023  *  The above copyright notice and this permission notice shall be
00024  *  included in all copies or substantial portions of the Software.
00025  *
00026  *  THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
00027  *  EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
00028  *  MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
00029  *  NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
00030  *  LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
00031  *  OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
00032  *  WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
00033  *
00034  */
00035 
00036 #include <gecode/int/rel.hh>
00037 #include <gecode/int/distinct.hh>
00038 
00039 namespace Gecode { namespace Int { namespace BinPacking {
00040 
00041   forceinline int
00042   ConflictGraph::nodes(void) const {
00043     return b.size();
00044   }
00045 
00046   forceinline
00047   ConflictGraph::NodeSet::NodeSet(void) {}
00048   forceinline
00049   ConflictGraph::NodeSet::NodeSet(Region& r, int n)
00050     : Support::RawBitSetBase(r,static_cast<unsigned int>(n)) {}
00051   forceinline
00052   ConflictGraph::NodeSet::NodeSet(Region& r, int n,
00053                                   const NodeSet& ns)
00054     : Support::RawBitSetBase(r,static_cast<unsigned int>(n),ns) {}
00055   forceinline void
00056   ConflictGraph::NodeSet::allocate(Region& r, int n) {
00057     Support::RawBitSetBase::allocate(r,static_cast<unsigned int>(n));
00058   }
00059   forceinline void
00060   ConflictGraph::NodeSet::init(Region& r, int n) {
00061     Support::RawBitSetBase::init(r,static_cast<unsigned int>(n));
00062   }
00063   forceinline bool
00064   ConflictGraph::NodeSet::in(int i) const {
00065     return RawBitSetBase::get(static_cast<unsigned int>(i));
00066   }
00067   forceinline void
00068   ConflictGraph::NodeSet::incl(int i) {
00069     RawBitSetBase::set(static_cast<unsigned int>(i));
00070   }
00071   forceinline void
00072   ConflictGraph::NodeSet::excl(int i) {
00073     RawBitSetBase::clear(static_cast<unsigned int>(i));
00074   }
00075   forceinline void
00076   ConflictGraph::NodeSet::copy(int n, const NodeSet& ns) {
00077     RawBitSetBase::copy(static_cast<unsigned int>(n),ns);
00078   }
00079   forceinline void
00080   ConflictGraph::NodeSet::empty(int n) {
00081     RawBitSetBase::clearall(static_cast<unsigned int>(n));
00082   }
00083   forceinline bool
00084   ConflictGraph::NodeSet::iwn(NodeSet& cwa, const NodeSet& a,
00085                               NodeSet& cwb, const NodeSet& b,
00086                               const NodeSet& c, int _n) {
00087     unsigned int n = static_cast<unsigned int>(_n);
00088     // This excludes the sentinel bit
00089     unsigned int pos = n / bpb;
00090     unsigned int bits = n % bpb;
00091 
00092     // Whether any bit is set
00093     Support::BitSetData abc; abc.init();
00094     for (unsigned int i=0; i<pos; i++) {
00095       cwa.data[i] = Support::BitSetData::a(a.data[i],c.data[i]);
00096       cwb.data[i] = Support::BitSetData::a(b.data[i],c.data[i]);
00097       abc.o(cwa.data[i]);
00098       abc.o(cwb.data[i]);
00099     }
00100     // Note that the sentinel bit is copied as well
00101     cwa.data[pos] = Support::BitSetData::a(a.data[pos],c.data[pos]);
00102     cwb.data[pos] = Support::BitSetData::a(b.data[pos],c.data[pos]);
00103     abc.o(cwa.data[pos],bits);
00104     abc.o(cwb.data[pos],bits);
00105 
00106     assert(cwa.get(n) && cwb.get(n));
00107     return abc.none();
00108   }
00109 
00110 
00111   forceinline
00112   ConflictGraph::Node::Node(void) {}
00113 
00114   forceinline
00115   ConflictGraph::Nodes::Nodes(const NodeSet& ns0)
00116     : ns(ns0), c(ns.next(0)) {}
00117   forceinline void
00118   ConflictGraph::Nodes::operator ++(void) {
00119     c = ns.next(c+1);
00120   }
00121   forceinline int
00122   ConflictGraph::Nodes::operator ()(void) const {
00123     return static_cast<int>(c);
00124   }
00125 
00126   forceinline
00127   ConflictGraph::Clique::Clique(Region& r, int m)
00128     : n(r,m), c(0), w(0) {}
00129   forceinline void
00130   ConflictGraph::Clique::incl(int i, unsigned int wi) {
00131     n.incl(i); c++; w += wi;
00132   }
00133   forceinline void
00134   ConflictGraph::Clique::excl(int i, unsigned int wi) {
00135     n.excl(i); c--; w -= wi;
00136   }
00137 
00138   forceinline
00139   ConflictGraph::ConflictGraph(Home& h, Region& reg,
00140                                const IntVarArgs& b0, int m)
00141     : home(h), b(b0),
00142       bins(static_cast<unsigned int>(m)),
00143       node(reg.alloc<Node>(nodes())),
00144       cur(reg,nodes()), max(reg,nodes()) {
00145     for (int i=0; i<nodes(); i++) {
00146       node[i].n.init(reg,nodes());
00147       node[i].d=node[i].w=0;
00148     }
00149   }
00150 
00151   forceinline
00152   ConflictGraph::~ConflictGraph(void) {
00153   }
00154 
00155   forceinline void
00156   ConflictGraph::edge(int i, int j, bool add) {
00157     if (add) {
00158       assert(!node[i].n.in(j) && !node[j].n.in(i));
00159       node[i].n.incl(j); node[i].d++; node[i].w++;
00160       node[j].n.incl(i); node[j].d++; node[j].w++;
00161     } else {
00162       assert(node[i].n.in(j) && node[j].n.in(i));
00163       node[i].n.excl(j); node[i].d--;
00164       node[j].n.excl(i); node[j].d--;
00165     }
00166   }
00167 
00168   forceinline bool
00169   ConflictGraph::adjacent(int i, int j) const {
00170     assert(node[i].n.in(j) == node[j].n.in(i));
00171     return node[i].n.in(j);
00172   }
00173 
00174   forceinline int
00175   ConflictGraph::pivot(const NodeSet& a, const NodeSet& b) const {
00176     Nodes i(a), j(b);
00177     assert((i() < nodes()) || (j() < nodes()));
00178     int p;
00179     if (i() < nodes()) {
00180       p = i(); ++i;
00181     } else {
00182       p = j(); ++j;
00183     }
00184     unsigned int m = node[p].d;
00185     while (i() < nodes()) {
00186       if (node[i()].d > m) {
00187         p=i(); m=node[p].d;
00188       }
00189       ++i;
00190     }
00191     while (j() < nodes()) {
00192       if (node[j()].d > m) {
00193         p=j(); m=node[p].d;
00194       }
00195       ++j;
00196     }
00197     return p;
00198   }
00199 
00200   forceinline ExecStatus
00201   ConflictGraph::clique(void) {
00202     // Remember clique
00203     if ((cur.c > max.c) || ((cur.c == max.c) && (cur.w > max.w))) {
00204       max.n.copy(nodes(),cur.n); max.c=cur.c; max.w=cur.w;
00205       if (max.c > bins)
00206         return ES_FAILED;
00207     }
00208     // Compute corresponding variables
00209     ViewArray<IntView> bv(home,static_cast<int>(cur.c));
00210     int i=0;
00211     for (Nodes c(cur.n); c() < nodes(); ++c)
00212       bv[i++] = b[c()];
00213     assert(i == static_cast<int>(cur.c));
00214     return Distinct::Dom<IntView>::post(home,bv);
00215   }
00216 
00217   forceinline ExecStatus
00218   ConflictGraph::clique(int i) {
00219     if (1 > max.c) {
00220       assert(max.n.none(nodes()));
00221       max.n.incl(i); max.c=1; max.w=0;
00222     }
00223     return ES_OK;
00224   }
00225 
00226   forceinline ExecStatus
00227   ConflictGraph::clique(int i, int j) {
00228     unsigned int w = node[i].w + node[j].w;
00229     if ((2 > max.c) || ((2 == max.c) && (cur.w > max.w))) {
00230       max.n.empty(nodes());
00231       max.n.incl(i); max.n.incl(j);
00232       max.c=2; max.w=w;
00233       if (max.c > bins)
00234         return ES_FAILED;
00235     }
00236     return Rel::Nq<IntView,IntView>::post(home,b[i],b[j]);
00237   }
00238 
00239   forceinline ExecStatus
00240   ConflictGraph::clique(int i, int j, int k) {
00241     unsigned int w = node[i].w + node[j].w + node[k].w;
00242     if ((3 > max.c) || ((3 == max.c) && (cur.w > max.w))) {
00243       max.n.empty(nodes());
00244       max.n.incl(i); max.n.incl(j); max.n.incl(k);
00245       max.c=3; max.w=w;
00246       if (max.c > bins)
00247         return ES_FAILED;
00248     }
00249     // Compute corresponding variables
00250     ViewArray<IntView> bv(home,3);
00251     bv[0]=b[i]; bv[1]=b[j]; bv[2]=b[k];
00252     return Distinct::Dom<IntView>::post(home,bv);
00253   }
00254 
00255   forceinline ExecStatus
00256   ConflictGraph::post(void) {
00257     // Find some simple cliques of sizes 2 and 3.
00258     Region reg;
00259     {
00260       // Nodes can be entered twice (for degree 2 and later for degree 1)
00261       Support::StaticStack<int,Region> n(reg,2*nodes());
00262       // Make a copy of the degree information to be used as weights
00263       // and record all nodes of degree 1 and 2.
00264       for (int i=0; i<nodes(); i++) {
00265         if ((node[i].d == 1) || (node[i].d == 2))
00266           n.push(i);
00267       }
00268       while (!n.empty()) {
00269         int i = n.pop();
00270         switch (node[i].d) {
00271         case 0:
00272           // Might happen as the edges have already been removed
00273           break;
00274         case 1: {
00275           Nodes ii(node[i].n);
00276           int j=ii();
00277           GECODE_ES_CHECK(clique(i,j));
00278           // Remove edge
00279           edge(i,j,false);
00280           if ((node[j].d == 1) || (node[j].d == 2))
00281             n.push(j);
00282           break;
00283         }
00284         case 2: {
00285           Nodes ii(node[i].n);
00286           int j=ii(); ++ii;
00287           int k=ii();
00288           if (adjacent(j,k)) {
00289             GECODE_ES_CHECK(clique(i,j,k));
00290             // Can the edge j-k still be member of another clique?
00291             if ((node[j].d == 2) || (node[k].d == 2))
00292               edge(j,k,false);
00293           } else {
00294             GECODE_ES_CHECK(clique(i,j));
00295             GECODE_ES_CHECK(clique(i,k));
00296           }
00297           edge(i,j,false);
00298           edge(i,k,false);
00299           if ((node[j].d == 1) || (node[j].d == 2))
00300             n.push(j);
00301           if ((node[k].d == 1) || (node[k].d == 2))
00302             n.push(k);
00303           break;
00304         }
00305         default: GECODE_NEVER;
00306         }
00307       }
00308       reg.free();
00309     }
00310     // Initialize for Bron-Kerbosch
00311     {
00312       NodeSet p(reg,nodes()), x(reg,nodes());
00313       bool empty = true;
00314       for (int i=0; i<nodes(); i++)
00315         if (node[i].d > 0) {
00316           p.incl(i); empty = false;
00317         } else {
00318           // Report clique of size 1
00319           GECODE_ES_CHECK(clique(i));
00320         }
00321       if (empty)
00322         return ES_OK;
00323       GECODE_ES_CHECK(bk(p,x));
00324       reg.free();
00325     }
00326     return ES_OK;
00327   }
00328 
00329   inline IntSet
00330   ConflictGraph::maxclique(void) const {
00331     Region reg;
00332     int* n=reg.alloc<int>(max.c);
00333     int j=0;
00334     for (Nodes i(max.n); i() < nodes(); ++i)
00335       n[j++]=i();
00336     assert(j == static_cast<int>(max.c));
00337     IntSet s(n,static_cast<int>(max.c));
00338     return s;
00339   }
00340 
00341 }}}
00342 
00343 // STATISTICS: int-prop
00344