src/libvpsc/solve_VPSC.h

   1 /**
   2  * \brief Solve an instance of the "Variable Placement with Separation
   3  * Constraints" problem.
   4  *
   5  * Authors:
   6  *   Tim Dwyer <tgdwyer@gmail.com>
   7  *
   8  * Copyright (C) 2005 Authors
   9  *
  10  * Released under GNU LGPL.  Read the file 'COPYING' for more information.
  11  */
  12
  13 //
  14 // TODO: Really, we should have three classes: VPSC, IncrementalVPSC and
  15 // StaticVPSC, where the latter two inherit from VPSC.  StaticVPSC would be
  16 // the equivalent of what is currently VPSC.
  17 // Also, a lot of the code specific to one or other of these concrete
  18 // implementations should be moved from Block and Blocks: e.g. mergeLeft etc.
  19 //
  20 #ifndef SEEN_REMOVEOVERLAP_SOLVE_VPSC_H
  21 #define SEEN_REMOVEOVERLAP_SOLVE_VPSC_H
  22
  23 #include <vector>
  24 class Variable;
  25 class Constraint;
  26 class Blocks;
  27
  28 /**
  29  * Variable Placement with Separation Constraints problem instance
  30  */
  31 class VPSC {
  32 public:
  33         virtual void satisfy();
  34         virtual void solve();
  35
  36         VPSC(const unsigned n, Variable* const vs[], const unsigned m, Constraint *cs[]);
  37         virtual ~VPSC();
  38         Constraint** getConstraints(unsigned &m) { m=this->m; return cs; }
  39         const Variable* const * getVariables(unsigned &n) { n=this->n; return vs; }
  40 protected:
  41         Blocks *bs;
  42         unsigned m;
  43         Constraint **cs;
  44         unsigned n;
  45         const Variable* const *vs;
  46         void printBlocks();
  47 private:
  48         void refine();
  49         bool constraintGraphIsCyclic(const unsigned n, Variable *vs[]);
  50         bool blockGraphIsCyclic();
  51 };
  52
  53 class IncVPSC : public VPSC {
  54 public:
  55         unsigned splitCnt;
  56         void satisfy();
  57         void solve();
  58         void moveBlocks();
  59         void splitBlocks();
  60         IncVPSC(const unsigned n, Variable* const vs[], const unsigned m, Constraint *cs[]);
  61 private:
  62         typedef std::vector<Constraint*> ConstraintList;
  63         ConstraintList inactive;
  64         Constraint* mostViolated(ConstraintList &l);
  65 };
  66 #endif // SEEN_REMOVEOVERLAP_SOLVE_VPSC_H