1 /*
2 * vim: ts=4 sw=4 et tw=0 wm=0
3 *
4 * libavoid - Fast, Incremental, Object-avoiding Line Router
5 *
6 * Copyright (C) 2005-2014 Monash University
7 *
8 * This library is free software; you can redistribute it and/or
9 * modify it under the terms of the GNU Lesser General Public
10 * License as published by the Free Software Foundation; either
11 * version 2.1 of the License, or (at your option) any later version.
12 * See the file LICENSE.LGPL distributed with the library.
13 *
14 * Licensees holding a valid commercial license may use this file in
15 * accordance with the commercial license agreement provided with the
16 * library.
17 *
18 * This library is distributed in the hope that it will be useful,
19 * but WITHOUT ANY WARRANTY; without even the implied warranty of
20 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
21 *
22 * Author(s): Tim Dwyer
23 * Michael Wybrow
24 *
25 * --------------
26 *
27 * This file contains a slightly modified version of IncSolver() from libvpsc:
28 * A solver for the problem of Variable Placement with Separation Constraints.
29 * It has the following changes from the Adaptagrams VPSC version:
30 * - The required VPSC code has been consolidated into a single file.
31 * - Unnecessary code (like Solver) has been removed.
32 * - The PairingHeap code has been replaced by a STL priority_queue.
33 *
34 * Modifications: Michael Wybrow
35 *
36 */
37
38 #ifndef LIBAVOID_VPSC_H
39 #define LIBAVOID_VPSC_H
40
41
42 #ifdef USELIBVPSC
43
44 // By default, libavoid will use it's own version of VPSC defined in this file.
45 //
46 // Alternatively, you can directly use IncSolver from libvpsc. This
47 // introduces a dependency on libvpsc but it can be preferable in cases
48 // where you are building all of Adaptagrams together and want to work
49 // with a set of CompoundConstraints or other classes built upon the
50 // base libvpsc Constraint classes.
51
52 // Include necessary headers from libvpsc.
53 #include "libvpsc/variable.h"
54 #include "libvpsc/constraint.h"
55 #include "libvpsc/rectangle.h"
56 #include "libvpsc/solve_VPSC.h"
57
58 // Use the libvpsc versions of things needed by libavoid.
59 using vpsc::Variable;
60 using vpsc::Variables;
61 using vpsc::Constraint;
62 using vpsc::Constraints;
63 using vpsc::IncSolver;
64 using vpsc::delete_object;
65
66 #else
67
68 #include <vector>
69 #include <list>
70 #include <set>
71 #include <queue>
72 #include <iostream>
73 #include <cfloat>
74
75 #include "libavoid/assertions.h"
76
77 namespace Avoid {
78
79 class Variable;
80 class Constraint;
81 class Blocks;
82 typedef std::vector<Variable*> Variables;
83 typedef std::vector<Constraint*> Constraints;
84 class CompareConstraints {
85 public:
86 bool operator() (Constraint *const &l, Constraint *const &r) const;
87 };
88 struct PositionStats {
PositionStatsPositionStats89 PositionStats() : scale(0), AB(0), AD(0), A2(0) {}
90 void addVariable(Variable* const v);
91 double scale;
92 double AB;
93 double AD;
94 double A2;
95 };
96
97 typedef std::priority_queue<Constraint*,std::vector<Constraint*>,
98 CompareConstraints> Heap;
99
100 class Block
101 {
102 typedef Variables::iterator Vit;
103 typedef Constraints::iterator Cit;
104 typedef Constraints::const_iterator Cit_const;
105
106 friend std::ostream& operator <<(std::ostream &os,const Block &b);
107 public:
108 Variables *vars;
109 double posn;
110 //double weight;
111 //double wposn;
112 PositionStats ps;
113 Block(Blocks *blocks, Variable* const v=nullptr);
114 ~Block(void);
115 Constraint* findMinLM();
116 Constraint* findMinLMBetween(Variable* const lv, Variable* const rv);
117 Constraint* findMinInConstraint();
118 Constraint* findMinOutConstraint();
119 void deleteMinInConstraint();
120 void deleteMinOutConstraint();
121 void updateWeightedPosition();
122 void merge(Block *b, Constraint *c, double dist);
123 Block* merge(Block *b, Constraint *c);
124 void mergeIn(Block *b);
125 void mergeOut(Block *b);
126 void split(Block *&l, Block *&r, Constraint *c);
127 Constraint* splitBetween(Variable* vl, Variable* vr, Block* &lb, Block* &rb);
128 void setUpInConstraints();
129 void setUpOutConstraints();
130 double cost();
131 bool deleted;
132 long timeStamp;
133 Heap *in;
134 Heap *out;
135 bool getActivePathBetween(Constraints& path, Variable const* u,
136 Variable const* v, Variable const *w) const;
137 bool isActiveDirectedPathBetween(
138 Variable const* u, Variable const* v) const;
139 bool getActiveDirectedPathBetween(Constraints& path, Variable const * u, Variable const * v) const;
140 private:
141 typedef enum {NONE, LEFT, RIGHT} Direction;
142 typedef std::pair<double, Constraint*> Pair;
143 void reset_active_lm(Variable* const v, Variable* const u);
144 void list_active(Variable* const v, Variable* const u);
145 double compute_dfdv(Variable* const v, Variable* const u);
146 double compute_dfdv(Variable* const v, Variable* const u, Constraint *&min_lm);
147 bool split_path(Variable*, Variable* const, Variable* const,
148 Constraint* &min_lm, bool desperation);
149 bool canFollowLeft(Constraint const* c, Variable const* last) const;
150 bool canFollowRight(Constraint const* c, Variable const* last) const;
151 void populateSplitBlock(Block *b, Variable* v, Variable const* u);
152 void addVariable(Variable* v);
153 void setUpConstraintHeap(Heap* &h,bool in);
154
155 // Parent container, that holds the blockTimeCtr.
156 Blocks *blocks;
157 };
158
159
160 class Constraint;
161 typedef std::vector<Constraint*> Constraints;
162 class Variable
163 {
164 friend std::ostream& operator <<(std::ostream &os, const Variable &v);
165 friend class Block;
166 friend class Constraint;
167 friend class IncSolver;
168 public:
169 int id; // useful in log files
170 double desiredPosition;
171 double finalPosition;
172 double weight; // how much the variable wants to
173 // be at it's desired position
174 double scale; // translates variable to another space
175 double offset;
176 Block *block;
177 bool visited;
178 bool fixedDesiredPosition;
179 Constraints in;
180 Constraints out;
181 inline Variable(const int id, const double desiredPos=-1.0,
182 const double weight=1.0, const double scale=1.0)
id(id)183 : id(id)
184 , desiredPosition(desiredPos)
185 , weight(weight)
186 , scale(scale)
187 , offset(0)
188 , block(nullptr)
189 , visited(false)
190 , fixedDesiredPosition(false)
191 {
192 }
dfdv(void)193 double dfdv(void) const {
194 return 2. * weight * ( position() - desiredPosition );
195 }
196 private:
position(void)197 inline double position(void) const {
198 return (block->ps.scale*block->posn+offset)/scale;
199 }
unscaledPosition(void)200 inline double unscaledPosition(void) const {
201 COLA_ASSERT(block->ps.scale == 1);
202 COLA_ASSERT(scale == 1);
203 return block->posn + offset;
204 }
205 };
206
207
208 class Constraint
209 {
210 public:
211 Constraint(Variable *left, Variable *right, double gap, bool equality=false);
212 ~Constraint();
slack(void)213 inline double slack(void) const
214 {
215 if (unsatisfiable)
216 {
217 return DBL_MAX;
218 }
219 if (needsScaling)
220 {
221 return right->scale * right->position() - gap -
222 left->scale * left->position();
223 }
224 COLA_ASSERT(left->scale == 1);
225 COLA_ASSERT(right->scale == 1);
226 return right->unscaledPosition() - gap - left->unscaledPosition();
227 }
228 std::string toString(void) const;
229
230 friend std::ostream& operator <<(std::ostream &os,const Constraint &c);
231 Variable *left;
232 Variable *right;
233 double gap;
234 double lm;
235 long timeStamp;
236 bool active;
237 const bool equality;
238 bool unsatisfiable;
239 bool needsScaling;
240 void *creator;
241 };
242 /*
243 * A block structure defined over the variables such that each block contains
244 * 1 or more variables, with the invariant that all constraints inside a block
245 * are satisfied by keeping the variables fixed relative to one another
246 */
247 class Blocks
248 {
249 public:
250 Blocks(Variables const &vs);
251 ~Blocks(void);
252 void mergeLeft(Block *r);
253 void mergeRight(Block *l);
254 void split(Block *b, Block *&l, Block *&r, Constraint *c);
255 std::list<Variable*> *totalOrder();
256 void cleanup();
257 double cost();
258
259 size_t size() const;
260 Block *at(size_t index) const;
261 void insert(Block *block);
262
263 long blockTimeCtr;
264 private:
265 void dfsVisit(Variable *v, std::list<Variable*> *order);
266 void removeBlock(Block *doomed);
267
268 std::vector<Block *> m_blocks;
269 Variables const &vs;
270 size_t nvs;
271 };
272
size()273 inline size_t Blocks::size() const
274 {
275 return m_blocks.size();
276 }
277
at(size_t index)278 inline Block *Blocks::at(size_t index) const
279 {
280 return m_blocks[index];
281 }
282
insert(Block * block)283 inline void Blocks::insert(Block *block)
284 {
285 m_blocks.push_back(block);
286 }
287
288 struct UnsatisfiableException {
289 Constraints path;
290 };
291 struct UnsatisfiedConstraint {
UnsatisfiedConstraintUnsatisfiedConstraint292 UnsatisfiedConstraint(Constraint& c):c(c) {}
293 Constraint& c;
294 };
295 /*
296 * Variable Placement with Separation Constraints problem instance
297 */
298 class IncSolver {
299 public:
300 unsigned splitCnt;
301 bool satisfy();
302 bool solve();
303 void moveBlocks();
304 void splitBlocks();
305 IncSolver(Variables const &vs, Constraints const &cs);
306
307 ~IncSolver();
308 void addConstraint(Constraint *constraint);
getVariables()309 Variables const & getVariables() { return vs; }
310 protected:
311 Blocks *bs;
312 size_t m;
313 Constraints const &cs;
314 size_t n;
315 Variables const &vs;
316 bool needsScaling;
317
318 void printBlocks();
319 void copyResult();
320 private:
321 bool constraintGraphIsCyclic(const unsigned n, Variable* const vs[]);
322 bool blockGraphIsCyclic();
323 Constraints inactive;
324 Constraints violated;
325 Constraint* mostViolated(Constraints &l);
326 };
327
328 struct delete_object
329 {
330 template <typename T>
operatordelete_object331 void operator()(T *ptr){ delete ptr;}
332 };
333
334 extern Constraints constraintsRemovingRedundantEqualities(
335 Variables const &vars, Constraints const &constraints);
336
337 }
338
339 #endif // ! USELIBVPSC
340
341 #endif // AVOID_VPSC_H
342