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
00037
00038
00039
00040
00041
00042 #ifndef __GECODE_INT_BIN_PACKING_HH__
00043 #define __GECODE_INT_BIN_PACKING_HH__
00044
00045 #include <gecode/int.hh>
00046
00052 namespace Gecode { namespace Int { namespace BinPacking {
00053
00057 class Item : public DerivedView<IntView> {
00058 protected:
00059 using DerivedView<IntView>::x;
00061 int s;
00062 public:
00064 Item(void);
00066 Item(IntView b, int s);
00067
00069 IntView bin(void) const;
00071 void bin(IntView b);
00073 int size(void) const;
00075 void size(int s);
00076
00078 void update(Space& home, bool share, Item& i);
00079 };
00080
00082 bool same(const Item& i, const Item& j);
00084 bool before(const Item& i, const Item& j);
00085
00087 bool operator <(const Item& i, const Item& j);
00088
00089
00091 class SizeSet {
00092 protected:
00094 int n;
00096 int t;
00098 int* s;
00099 public:
00101 SizeSet(void);
00103 SizeSet(Region& region, int n_max);
00105 void add(int s);
00107 int card(void) const;
00109 int total(void) const;
00111 int operator [](int i) const;
00112 };
00113
00115 class SizeSetMinusOne : public SizeSet {
00116 protected:
00118 int p;
00119 public:
00121 SizeSetMinusOne(void);
00123 SizeSetMinusOne(Region& region, int n);
00125 void minus(int s);
00127 int card(void) const;
00129 int total(void) const;
00131 int operator [](int i) const;
00132 };
00133
00134
00145 class Pack : public Propagator {
00146 protected:
00148 ViewArray<OffsetView> l;
00150 ViewArray<Item> bs;
00152 int t;
00154 Pack(Home home, ViewArray<OffsetView>& l, ViewArray<Item>& bs);
00156 Pack(Space& home, bool share, Pack& p);
00157 public:
00159 GECODE_INT_EXPORT
00160 static ExecStatus post(Home home,
00161 ViewArray<OffsetView>& l, ViewArray<Item>& bs);
00163 template<class SizeSet>
00164 bool nosum(const SizeSet& s, int a, int b, int& ap, int& bp);
00166 template<class SizeSet>
00167 bool nosum(const SizeSet& s, int a, int b);
00169 GECODE_INT_EXPORT
00170 virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
00172 GECODE_INT_EXPORT
00173 virtual PropCost cost(const Space& home, const ModEventDelta& med) const;
00175 GECODE_INT_EXPORT
00176 virtual Actor* copy(Space& home, bool share);
00178 virtual size_t dispose(Space& home);
00179 };
00180
00181
00183 class ConflictGraph {
00184 protected:
00186 Space& home;
00188 const IntVarArgs& b;
00190 unsigned int bins;
00192 int nodes(void) const;
00193
00195 class NodeSet : public Support::RawBitSetBase {
00196 public:
00198 NodeSet(void);
00200 NodeSet(Region& r, int n);
00202 NodeSet(Region& r, int n, const NodeSet& ns);
00204 void allocate(Region& r, int n);
00206 void init(Region& r, int n);
00208 bool in(int i) const;
00210 void incl(int i);
00212 void excl(int i);
00214 void copy(int n, const NodeSet& ns);
00216 void empty(int n);
00223 static bool iwn(NodeSet& iwa, const NodeSet& a,
00224 NodeSet& iwb, const NodeSet& b,
00225 const NodeSet& c, int n);
00226 };
00227
00229 class Node {
00230 public:
00232 NodeSet n;
00234 unsigned int d;
00236 unsigned int w;
00238 Node(void);
00239 };
00241 Node* node;
00242
00244 class Nodes {
00245 private:
00247 const NodeSet& ns;
00249 unsigned int c;
00250 public:
00252 Nodes(const NodeSet& ns);
00254
00255
00256 void operator ++(void);
00258
00260
00261
00262 int operator ()(void) const;
00264 };
00265
00267
00268
00269 class Clique {
00270 public:
00272 NodeSet n;
00274 unsigned int c;
00276 unsigned int w;
00278 Clique(Region& r, int m);
00280 void incl(int i, unsigned int w);
00282 void excl(int i, unsigned int w);
00283 };
00284
00286 int pivot(const NodeSet& a, const NodeSet& b) const;
00288 GECODE_INT_EXPORT
00289 ExecStatus bk(NodeSet& p, NodeSet& x);
00291
00293
00294
00295 Clique cur;
00297 Clique max;
00299 ExecStatus clique(void);
00301 ExecStatus clique(int i);
00303 ExecStatus clique(int i, int j);
00305 ExecStatus clique(int i, int j, int k);
00307 public:
00309 ConflictGraph(Space& home, Region& r, const IntVarArgs& b,
00310 int m);
00312 void edge(int i, int j, bool add=true);
00314 bool adjacent(int i, int j) const;
00316 ExecStatus post(void);
00318 IntSet maxclique(void) const;
00320 ~ConflictGraph(void);
00321 };
00322
00323 }}}
00324
00325 #include <gecode/int/bin-packing/propagate.hpp>
00326 #include <gecode/int/bin-packing/conflict-graph.hpp>
00327
00328 #endif
00329
00330
00331