src/removeoverlap/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 #ifndef SEEN_REMOVEOVERLAP_SOLVE_VPSC_H
  13 #define SEEN_REMOVEOVERLAP_SOLVE_VPSC_H
  14
  15 #include <vector>
  16 class Variable;
  17 class Constraint;
  18 class Blocks;
  19
  20 /**
  21  * Variable Placement with Separation Constraints problem instance
  22  */
  23 class VPSC {
  24 public:
  25         virtual void satisfy();
  26         virtual void solve();
  27
  28         VPSC(const unsigned n, Variable *vs[], const unsigned m, Constraint *cs[]);
  29         virtual ~VPSC();
  30         Constraint** getConstraints() { return cs; }
  31         Variable** getVariables() { return vs; }
  32 protected:
  33         Blocks *bs;
  34         Constraint **cs;
  35         unsigned m;
  36         Variable **vs;
  37         void printBlocks();
  38 private:
  39         void refine();
  40         bool constraintGraphIsCyclic(const unsigned n, Variable *vs[]);
  41         bool blockGraphIsCyclic();
  42 };
  43
  44 class IncVPSC : public VPSC {
  45 public:
  46         unsigned splitCnt;
  47         void satisfy();
  48         void solve();
  49         void moveBlocks();
  50         void splitBlocks();
  51         IncVPSC(const unsigned n, Variable *vs[], const unsigned m, Constraint *cs[]);
  52 private:
  53         typedef std::vector<Constraint*> ConstraintList;
  54         ConstraintList inactive;
  55         Constraint* mostViolated(ConstraintList &l);
  56 };
  57 #endif // SEEN_REMOVEOVERLAP_SOLVE_VPSC_H