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 */
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
23 #include <vector>
25 namespace vpsc {
26 class Variable;
27 class Constraint;
28 class Blocks;
30 /**
31 * Variable Placement with Separation Constraints problem instance
32 */
33 class Solver {
34 public:
35 virtual void satisfy();
36 virtual void solve();
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 };
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