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
  25 namespace vpsc {
  26 class Variable;
  27 class Constraint;
  28 class Blocks;
  29
  30 /**
  31  * Variable Placement with Separation Constraints problem instance
  32  */
  33 class Solver {
  34 public:
  35         virtual void satisfy();
  36         virtual void solve();
  37
  38         Solver(const unsigned n, Variable* const vs[], const unsigned m, Constraint *cs[]);
  39         virtual ~Solver();
  40         Constraint** getConstraints(unsigned &m) { m=this->m; return cs; }
  41         const Variable* const * getVariables(unsigned &n) { n=this->n; return vs; }
  42 protected:
  43         Blocks *bs;
  44         unsigned m;
  45         Constraint **cs;
  46         unsigned n;
  47         const Variable* const *vs;
  48         void printBlocks();
  49 private:
  50         void refine();
  51         bool constraintGraphIsCyclic(const unsigned n, Variable* const vs[]);
  52         bool blockGraphIsCyclic();
  53 };
  54
  55 class IncSolver : public Solver {
  56 public:
  57         unsigned splitCnt;
  58         void satisfy();
  59         void solve();
  60         void moveBlocks();
  61         void splitBlocks();
  62         IncSolver(const unsigned n, Variable* const vs[], const unsigned m, Constraint *cs[]);
  63 private:
  64         typedef std::vector<Constraint*> ConstraintList;
  65         ConstraintList inactive;
  66         Constraint* mostViolated(ConstraintList &l);
  67 };
  68 }
  69 #endif // SEEN_REMOVEOVERLAP_SOLVE_VPSC_H