1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
|
/*
* vim: ts=4 sw=4 et tw=0 wm=0
*
* libvpsc - A solver for the problem of Variable Placement with
* Separation Constraints.
*
* Copyright (C) 2005-2013 Monash University
*
* This library is free software; you can redistribute it and/or
* modify it under the terms of the GNU Lesser General Public
* License as published by the Free Software Foundation; either
* version 2.1 of the License, or (at your option) any later version.
* See the file LICENSE.LGPL distributed with the library.
*
* This library is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
*
* Author(s): Tim Dwyer
* Michael Wybrow
*/
//
// TODO: Really, we should have three classes: VPSC, IncrementalVPSC and
// StaticVPSC, where the latter two inherit from VPSC. StaticVPSC would be
// the equivalent of what is currently VPSC.
// Also, a lot of the code specific to one or other of these concrete
// implementations should be moved from Block and Blocks: e.g. mergeLeft etc.
//
#ifndef VPSC_SOLVE_VPSC_H
#define VPSC_SOLVE_VPSC_H
#include <vector>
/**
* @namespace vpsc
* @brief libvpsc: Variable Placement with Separation Constraints
* quadratic program solver library.
*
* You should use VPSC via an instance of the IncSolver or Solver classes.
*/
namespace vpsc {
class Variable;
typedef std::vector<Variable*> Variables;
class Constraint;
class Blocks;
typedef std::vector<Constraint*> Constraints;
/**
* @brief Static solver for Variable Placement with Separation Constraints
* problem instance
*
* This class attempts to solve a least-squares problem subject to a set
* of separation constraints. The solve() and satisfy() methods return true
* if any constraints are active, in both cases false means an unconstrained
* optimum has been found.
*
* @sa IncSolver
*/
class Solver {
public:
//! @brief Results in an approximate solution subject to the constraints.
//! @return true if any constraints are active, or false if an unconstrained
//! optimum has been found.
virtual bool satisfy();
//! @brief Results in an optimum solution subject to the constraints
//! @return true if any constraints are active, or false if an unconstrained
//! optimum has been found.
virtual bool solve();
Solver(Variables const &vs, Constraints const &cs);
virtual ~Solver();
//! @brief Returns the Variables in this problem instance.
//! @returns A vector of Variable objects.
Variables const & getVariables() { return vs; }
protected:
Blocks *bs;
size_t m;
std::vector<Constraint*> const &cs;
size_t n;
std::vector<Variable*> const &vs;
bool needsScaling;
void printBlocks();
void copyResult();
private:
void refine();
bool constraintGraphIsCyclic(const unsigned n, Variable* const vs[]);
bool blockGraphIsCyclic();
};
/**
* @brief Incremental solver for Variable Placement with Separation Constraints
* problem instance
*
* This class attempts to solve a least-squares problem subject to a set
* of sepation constraints. The solve() and satisfy() methods return true
* if any constraints are active, in both cases false means an unconstrained
* optimum has been found. This is an incremental version of that allows
* refinement after blocks are moved. This version is preferred if you are
* using VPSC in an interactive context.
*
* @sa Solver
*/
class IncSolver : public Solver {
public:
IncSolver(Variables const &vs, Constraints const &cs);
//! @brief Results in an approximate solution subject to the constraints.
//! @return true if any constraints are active, or false if an unconstrained
bool satisfy();
//! @brief Results in an optimum solution subject to the constraints
//! @return true if any constraints are active, or false if an unconstrained
//! optimum has been found.
bool solve();
//! @brief Adds a constraint to the existing VPSC solver.
//!
//! @param constraint The new additional constraint to add.
void addConstraint(Constraint *constraint);
private:
void moveBlocks();
void splitBlocks();
unsigned splitCnt;
Constraints inactive;
Constraints violated;
Constraint* mostViolated(Constraints &l);
};
}
#endif // VPSC_SOLVE_VPSC_H
|
