1 //===---------------- PBQP.cpp --------- PBQP Solver ------------*- C++ -*-===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 // Developed by: Bernhard Scholz
11 // The University of Sydney
12 // http://www.it.usyd.edu.au/~scholz
13 //===----------------------------------------------------------------------===//
17 // * Default to null costs on vector initialisation?
18 // * C++-ify the rest of the solver.
20 #ifndef LLVM_CODEGEN_PBQPSOLVER_H
21 #define LLVM_CODEGEN_PBQPSOLVER_H
29 //! \brief Floating point type to use in PBQP solver.
30 typedef double PBQPNum;
32 //! \brief PBQP Vector class.
36 //! \brief Construct a PBQP vector of the given size.
37 explicit PBQPVector(unsigned length) :
38 length(length), data(new PBQPNum[length]) {
39 std::fill(data, data + length, 0);
42 //! \brief Copy construct a PBQP vector.
43 PBQPVector(const PBQPVector &v) :
44 length(v.length), data(new PBQPNum[length]) {
45 std::copy(v.data, v.data + length, data);
48 ~PBQPVector() { delete[] data; }
50 //! \brief Assignment operator.
51 PBQPVector& operator=(const PBQPVector &v) {
54 data = new PBQPNum[length];
55 std::copy(v.data, v.data + length, data);
59 //! \brief Return the length of the vector
60 unsigned getLength() const throw () {
64 //! \brief Element access.
65 PBQPNum& operator[](unsigned index) {
66 assert(index < length && "PBQPVector element access out of bounds.");
70 //! \brief Const element access.
71 const PBQPNum& operator[](unsigned index) const {
72 assert(index < length && "PBQPVector element access out of bounds.");
76 //! \brief Add another vector to this one.
77 PBQPVector& operator+=(const PBQPVector &v) {
78 assert(length == v.length && "PBQPVector length mismatch.");
79 std::transform(data, data + length, v.data, data, std::plus<PBQPNum>());
83 //! \brief Subtract another vector from this one.
84 PBQPVector& operator-=(const PBQPVector &v) {
85 assert(length == v.length && "PBQPVector length mismatch.");
86 std::transform(data, data + length, v.data, data, std::minus<PBQPNum>());
90 //! \brief Returns the index of the minimum value in this vector
91 unsigned minIndex() const {
92 return std::min_element(data, data + length) - data;
101 //! \brief PBQP Matrix class
105 //! \brief Construct a PBQP Matrix with the given dimensions.
106 PBQPMatrix(unsigned rows, unsigned cols) :
107 rows(rows), cols(cols), data(new PBQPNum[rows * cols]) {
108 std::fill(data, data + (rows * cols), 0);
111 //! \brief Copy construct a PBQP matrix.
112 PBQPMatrix(const PBQPMatrix &m) :
113 rows(m.rows), cols(m.cols), data(new PBQPNum[rows * cols]) {
114 std::copy(m.data, m.data + (rows * cols), data);
117 ~PBQPMatrix() { delete[] data; }
119 //! \brief Assignment operator.
120 PBQPMatrix& operator=(const PBQPMatrix &m) {
122 rows = m.rows; cols = m.cols;
123 data = new PBQPNum[rows * cols];
124 std::copy(m.data, m.data + (rows * cols), data);
128 //! \brief Return the number of rows in this matrix.
129 unsigned getRows() const throw () { return rows; }
131 //! \brief Return the number of cols in this matrix.
132 unsigned getCols() const throw () { return cols; }
134 //! \brief Matrix element access.
135 PBQPNum* operator[](unsigned r) {
136 assert(r < rows && "Row out of bounds.");
137 return data + (r * cols);
140 //! \brief Matrix element access.
141 const PBQPNum* operator[](unsigned r) const {
142 assert(r < rows && "Row out of bounds.");
143 return data + (r * cols);
146 //! \brief Returns the given row as a vector.
147 PBQPVector getRowAsVector(unsigned r) const {
149 for (unsigned c = 0; c < cols; ++c)
150 v[c] = (*this)[r][c];
154 //! \brief Reset the matrix to the given value.
155 PBQPMatrix& reset(PBQPNum val = 0) {
156 std::fill(data, data + (rows * cols), val);
160 //! \brief Set a single row of this matrix to the given value.
161 PBQPMatrix& setRow(unsigned r, PBQPNum val) {
162 assert(r < rows && "Row out of bounds.");
163 std::fill(data + (r * cols), data + ((r + 1) * cols), val);
167 //! \brief Set a single column of this matrix to the given value.
168 PBQPMatrix& setCol(unsigned c, PBQPNum val) {
169 assert(c < cols && "Column out of bounds.");
170 for (unsigned r = 0; r < rows; ++r)
175 //! \brief Matrix transpose.
176 PBQPMatrix transpose() const {
177 PBQPMatrix m(cols, rows);
178 for (unsigned r = 0; r < rows; ++r)
179 for (unsigned c = 0; c < cols; ++c)
180 m[c][r] = (*this)[r][c];
184 //! \brief Returns the diagonal of the matrix as a vector.
186 //! Matrix must be square.
187 PBQPVector diagonalize() const {
188 assert(rows == cols && "Attempt to diagonalize non-square matrix.");
191 for (unsigned r = 0; r < rows; ++r)
192 v[r] = (*this)[r][r];
196 //! \brief Add the given matrix to this one.
197 PBQPMatrix& operator+=(const PBQPMatrix &m) {
198 assert(rows == m.rows && cols == m.cols &&
199 "Matrix dimensions mismatch.");
200 std::transform(data, data + (rows * cols), m.data, data,
201 std::plus<PBQPNum>());
205 //! \brief Returns the minimum of the given row
206 PBQPNum getRowMin(unsigned r) const {
207 assert(r < rows && "Row out of bounds");
208 return *std::min_element(data + (r * cols), data + ((r + 1) * cols));
211 //! \brief Returns the minimum of the given column
212 PBQPNum getColMin(unsigned c) const {
213 PBQPNum minElem = (*this)[0][c];
214 for (unsigned r = 1; r < rows; ++r)
215 if ((*this)[r][c] < minElem) minElem = (*this)[r][c];
219 //! \brief Subtracts the given scalar from the elements of the given row.
220 PBQPMatrix& subFromRow(unsigned r, PBQPNum val) {
221 assert(r < rows && "Row out of bounds");
222 std::transform(data + (r * cols), data + ((r + 1) * cols),
224 std::bind2nd(std::minus<PBQPNum>(), val));
228 //! \brief Subtracts the given scalar from the elements of the given column.
229 PBQPMatrix& subFromCol(unsigned c, PBQPNum val) {
230 for (unsigned r = 0; r < rows; ++r)
231 (*this)[r][c] -= val;
235 //! \brief Returns true if this is a zero matrix.
236 bool isZero() const {
237 return find_if(data, data + (rows * cols),
238 std::bind2nd(std::not_equal_to<PBQPNum>(), 0)) ==
239 data + (rows * cols);
252 typedef struct pbqp pbqp;
259 /* allocate pbqp problem */
260 pbqp *alloc_pbqp(int num);
263 void add_pbqp_nodecosts(pbqp *this_,int u, PBQPVector *costs);
266 void add_pbqp_edgecosts(pbqp *this_,int u,int v,PBQPMatrix *costs);
268 /* solve PBQP problem */
269 void solve_pbqp(pbqp *this_);
271 /* get solution of a node */
272 int get_pbqp_solution(pbqp *this_,int u);
275 pbqp *alloc_pbqp(int num);
278 void free_pbqp(pbqp *this_);
281 bool is_pbqp_optimal(pbqp *this_);