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
15 #include <vector>
16 class Variable;
17 class Constraint;
18 class Blocks;
20 /**
21 * Variable Placement with Separation Constraints problem instance
22 */
23 class VPSC {
24 public:
25 virtual void satisfy();
26 virtual void solve();
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 };
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