Something went wrong. Try again.
This repository has no description
Something went wrong. Try again.
9.6 kB · 330 lines
C++
at develop
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331/* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- *//* * Main authors: * Christian Schulte <schulte@gecode.org> * * Contributing authors: * Stefano Gualandi <stefano.gualandi@gmail.com> * * Copyright: * Stefano Gualandi, 2013 * Christian Schulte, 2010 * * 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. * */
#ifndef GECODE_INT_BIN_PACKING_HH#define GECODE_INT_BIN_PACKING_HH
#include <gecode/int.hh>
/** * \namespace Gecode::Int::BinPacking * \brief %Bin-packing propagators */
namespace Gecode { namespace Int { namespace BinPacking {
/** * \brief Item combining bin and size information */ class Item : public DerivedView<IntView> { protected: using DerivedView<IntView>::x; /// Size of item int s; public: /// Default constructor Item(void); /// Constructor Item(IntView b, int s);
/// Return bin of item IntView bin(void) const; /// Set bin of item to \a b void bin(IntView b); /// Return size of item int size(void) const; /// Set size of item to \a s void size(int s);
/// Update item during cloning void update(Space& home, Item& i); };
/// Whether two items are the same bool operator ==(const Item& i, const Item& j); /// Whether two items are not the same bool operator !=(const Item& i, const Item& j);
/// Order, also for sorting according to size bool operator <(const Item& i, const Item& j);
/// Size sets class SizeSet { protected: /// Number of size entries in the set int n; /// Total size of the set int t; /// Array of sizes (will have more elements) int* s; public: /// Default constructor SizeSet(void); /// Initialize for at most \a n_max items SizeSet(Region& region, int n_max); /// Add new size \a s void add(int s); /// Return cardinality of set (number of entries) int card(void) const; /// Return total size int total(void) const; /// Return size of item \a i int operator [](int i) const; };
/// Size sets with one element discarded class SizeSetMinusOne : public SizeSet { protected: /// Position of discarded item int p; public: /// Default constructor SizeSetMinusOne(void); /// Initialize for at most \n n_max entries SizeSetMinusOne(Region& region, int n); /// Discard size \a s void minus(int s); /// Return cardinality of set (number of entries) int card(void) const; /// Return total size int total(void) const; /// Return size of item \a i int operator [](int i) const; };
/** * \brief Bin-packing propagator * * The algorithm is taken from: * Paul Shaw. A Constraint for Bin Packing. CP 2004. * * Requires \code #include <gecode/int/bin-packing.hh> \endcode * * \ingroup FuncIntProp */ class Pack : public Propagator { protected: /// Views for load of bins ViewArray<OffsetView> l; /// Items with bin and size ViewArray<Item> bs; /// Total size of all items int t; /// Constructor for posting Pack(Home home, ViewArray<OffsetView>& l, ViewArray<Item>& bs); /// Constructor for cloning \a p Pack(Space& home, Pack& p); public: /// Post propagator for loads \a l and items \a bs GECODE_INT_EXPORT static ExecStatus post(Home home, ViewArray<OffsetView>& l, ViewArray<Item>& bs); /// Detect non-existence of sums in \a a .. \a b template<class SizeSet> bool nosum(const SizeSet& s, int a, int b, int& ap, int& bp); /// Detect non-existence of sums in \a a .. \a b template<class SizeSet> bool nosum(const SizeSet& s, int a, int b); /// Perform propagation GECODE_INT_EXPORT virtual ExecStatus propagate(Space& home, const ModEventDelta& med); /// Cost function GECODE_INT_EXPORT virtual PropCost cost(const Space& home, const ModEventDelta& med) const; /// Schedule function GECODE_INT_EXPORT virtual void reschedule(Space& home); /// Copy propagator during cloning GECODE_INT_EXPORT virtual Actor* copy(Space& home); /// Destructor virtual size_t dispose(Space& home); };
/// Graph containing conflict information class ConflictGraph { protected: /// Home space Home& home; /// Bin variables const IntVarArgs& b; /// Number of bins unsigned int bins; /// Return number of nodes int nodes(void) const;
/// Sets of graph nodes class NodeSet : public Support::RawBitSetBase { public: /// Keep uninitialized NodeSet(void); /// Initialize node set for \a n nodes NodeSet(Region& r, int n); /// Initialize node set as copy of \a ns with \a n nodes NodeSet(Region& r, int n, const NodeSet& ns); /// Allocate node set for \a n nodes void allocate(Region& r, int n); /// Initialize node set for \a n nodes void init(Region& r, int n); /// Test whether node \a i is included bool in(int i) const; /// Include node \a i void incl(int i); /// Exclude node \a i void excl(int i); /// Copy elements from node set \a ns with \a n nodes void copy(int n, const NodeSet& ns); /// Clear the whole node set for \a n nodes void empty(int n); /** * Initialize \a ac as intersection of \a a and \a c, * \a bc as intersection of \a b and \a c where \a n * is the maximal number of nodes. Return whether both \ac * and \a bc are empty. */ static bool iwn(NodeSet& iwa, const NodeSet& a, NodeSet& iwb, const NodeSet& b, const NodeSet& c, int n); };
/// Class for node in graph class Node { public: /// The neighbors NodeSet n; /// Degree unsigned int d; /// Weight (initialized with degree before graph is reduced) unsigned int w; /// Default constructor Node(void); }; /// The nodes in the graph Node* node;
/// Iterator over node sets class Nodes { private: /// The node set to iterate over const NodeSet& ns; /// Current node unsigned int c; public: /// Initialize for nodes in \a ns Nodes(const NodeSet& ns); /// \name Iteration control //@{ /// Move iterator to next node (if possible) void operator ++(void); //@}
/// \name %Node access //@{ /// Return current node int operator ()(void) const; //@} };
/// \name Routines for Bosch-Kerbron algorithm //@{ /// Clique information class Clique { public: /// Nodes in the clique NodeSet n; /// Cardinality of clique unsigned int c; /// Weight of clique unsigned int w; /// Constructor for \a m nodes Clique(Region& r, int m); /// Include node \a i with weight \a w void incl(int i, unsigned int w); /// Exclude node \a i with weight \a w void excl(int i, unsigned int w); };
/// Find a pivot node with maximal degree from \a a or \a b int pivot(const NodeSet& a, const NodeSet& b) const; /// Run Bosch-Kerbron algorithm for finding max cliques GECODE_INT_EXPORT ExecStatus bk(NodeSet& p, NodeSet& x); //@}
/// \name Managing cliques //@{ /// Current clique Clique cur; /// Largest clique so far Clique max; /// Report the current clique ExecStatus clique(void); /// Found a clique of node \a i ExecStatus clique(int i); /// Found a clique of nodes \a i and \a j ExecStatus clique(int i, int j); /// Found a clique of nodes \a i, \a j, and \a k ExecStatus clique(int i, int j, int k); //@} public: /// Initialize graph ConflictGraph(Home& home, Region& r, const IntVarArgs& b, int m); /// Add or remove an edge between nodes \a i and \a j (\a i must be less than \a j) void edge(int i, int j, bool add=true); /// Test whether nodes \a i and \a j are adjacent bool adjacent(int i, int j) const; /// Post additional constraints ExecStatus post(void); /// Return maximal clique found IntSet maxclique(void) const; /// Destructor ~ConflictGraph(void); };
}}}
#include <gecode/int/bin-packing/propagate.hpp>#include <gecode/int/bin-packing/conflict-graph.hpp>
#endif
// STATISTICS: int-prop