00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023
00024
00025
00026
00027
00028
00029
00030
00031
00032
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
00089 unsigned int pos = n / bpb;
00090 unsigned int bits = n % bpb;
00091
00092
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
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=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
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
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
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
00258 Region reg;
00259 {
00260
00261 Support::StaticStack<int,Region> n(reg,2*nodes());
00262
00263
00264 for (int 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
00273 break;
00274 case 1: {
00275 Nodes ii(node[i].n);
00276 int j=ii();
00277 GECODE_ES_CHECK(clique(i,j));
00278
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
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
00311 {
00312 NodeSet p(reg,nodes()), x(reg,nodes());
00313 bool empty = true;
00314 for (int i=nodes(); i--; )
00315 if (node[i].d > 0) {
00316 p.incl(i); empty = false;
00317 } else {
00318
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
00344