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-2009 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 <Tim.Dwyer@csse.monash.edu.au>
23 *
24 * --------------
25 *
26 * This file contains a slightly modified version of Solver() from libvpsc:
27 * A solver for the problem of Variable Placement with Separation Constraints.
28 * It has the following changes from the Adaptagrams VPSC version:
29 * - The required VPSC code has been consolidated into a single file.
30 * - Unnecessary code (like Solver) has been removed.
31 * - The PairingHeap code has been replaced by a STL priority_queue.
32 *
33 * Modifications: Michael Wybrow <mjwybrow@users.sourceforge.net>
34 *
35 */
37 #ifndef LIBAVOID_VPSC_H
38 #define LIBAVOID_VPSC_H
40 #include <vector>
41 #include <list>
42 #include <set>
43 #include <queue>
45 namespace Avoid {
47 class Variable;
48 class Constraint;
49 typedef std::vector<Variable*> Variables;
50 typedef std::vector<Constraint*> Constraints;
51 class CompareConstraints {
52 public:
53 bool operator() (Constraint *const &l, Constraint *const &r) const;
54 };
55 struct PositionStats {
56 PositionStats() : scale(0), AB(0), AD(0), A2(0) {}
57 void addVariable(Variable* const v);
58 double scale;
59 double AB;
60 double AD;
61 double A2;
62 };
64 typedef std::priority_queue<Constraint*,std::vector<Constraint*>,
65 CompareConstraints> Heap;
67 class Block
68 {
69 typedef Variables::iterator Vit;
70 typedef Constraints::iterator Cit;
71 typedef Constraints::const_iterator Cit_const;
73 friend std::ostream& operator <<(std::ostream &os,const Block &b);
74 public:
75 Variables *vars;
76 double posn;
77 //double weight;
78 //double wposn;
79 PositionStats ps;
80 Block(Variable* const v=NULL);
81 ~Block(void);
82 Constraint* findMinLM();
83 Constraint* findMinLMBetween(Variable* const lv, Variable* const rv);
84 Constraint* findMinInConstraint();
85 Constraint* findMinOutConstraint();
86 void deleteMinInConstraint();
87 void deleteMinOutConstraint();
88 void updateWeightedPosition();
89 void merge(Block *b, Constraint *c, double dist);
90 Block* merge(Block *b, Constraint *c);
91 void mergeIn(Block *b);
92 void mergeOut(Block *b);
93 void split(Block *&l, Block *&r, Constraint *c);
94 Constraint* splitBetween(Variable* vl, Variable* vr, Block* &lb, Block* &rb);
95 void setUpInConstraints();
96 void setUpOutConstraints();
97 double cost();
98 bool deleted;
99 long timeStamp;
100 Heap *in;
101 Heap *out;
102 bool getActivePathBetween(Constraints& path, Variable const* u,
103 Variable const* v, Variable const *w) const;
104 bool isActiveDirectedPathBetween(
105 Variable const* u, Variable const* v) const;
106 bool getActiveDirectedPathBetween(Constraints& path, Variable const * u, Variable const * v) const;
107 private:
108 typedef enum {NONE, LEFT, RIGHT} Direction;
109 typedef std::pair<double, Constraint*> Pair;
110 void reset_active_lm(Variable* const v, Variable* const u);
111 void list_active(Variable* const v, Variable* const u);
112 double compute_dfdv(Variable* const v, Variable* const u);
113 double compute_dfdv(Variable* const v, Variable* const u, Constraint *&min_lm);
114 bool split_path(Variable*, Variable* const, Variable* const,
115 Constraint* &min_lm, bool desperation);
116 bool canFollowLeft(Constraint const* c, Variable const* last) const;
117 bool canFollowRight(Constraint const* c, Variable const* last) const;
118 void populateSplitBlock(Block *b, Variable* v, Variable const* u);
119 void addVariable(Variable* v);
120 void setUpConstraintHeap(Heap* &h,bool in);
121 };
124 class Constraint;
125 typedef std::vector<Constraint*> Constraints;
126 class Variable
127 {
128 friend std::ostream& operator <<(std::ostream &os, const Variable &v);
129 friend class Block;
130 friend class Constraint;
131 friend class IncSolver;
132 public:
133 int id; // useful in log files
134 double desiredPosition;
135 double finalPosition;
136 double weight; // how much the variable wants to
137 // be at it's desired position
138 double scale; // translates variable to another space
139 double offset;
140 Block *block;
141 bool visited;
142 bool fixedDesiredPosition;
143 Constraints in;
144 Constraints out;
145 char *toString();
146 inline Variable(const int id, const double desiredPos=-1.0,
147 const double weight=1.0, const double scale=1.0)
148 : id(id)
149 , desiredPosition(desiredPos)
150 , weight(weight)
151 , scale(scale)
152 , offset(0)
153 , block(NULL)
154 , visited(false)
155 , fixedDesiredPosition(false)
156 {
157 }
158 double dfdv() const {
159 return 2. * weight * ( position() - desiredPosition );
160 }
161 private:
162 double position() const {
163 return (block->ps.scale*block->posn+offset)/scale;
164 }
165 };
168 class Constraint
169 {
170 friend std::ostream& operator <<(std::ostream &os,const Constraint &c);
171 public:
172 Variable *left;
173 Variable *right;
174 double gap;
175 double lm;
176 Constraint(Variable *left, Variable *right, double gap, bool equality=false);
177 ~Constraint();
178 double slack() const;
179 long timeStamp;
180 bool active;
181 const bool equality;
182 bool unsatisfiable;
183 };
184 /*
185 * A block structure defined over the variables such that each block contains
186 * 1 or more variables, with the invariant that all constraints inside a block
187 * are satisfied by keeping the variables fixed relative to one another
188 */
189 class Blocks : public std::set<Block*>
190 {
191 public:
192 Blocks(Variables const &vs);
193 ~Blocks(void);
194 void mergeLeft(Block *r);
195 void mergeRight(Block *l);
196 void split(Block *b, Block *&l, Block *&r, Constraint *c);
197 std::list<Variable*> *totalOrder();
198 void cleanup();
199 double cost();
200 private:
201 void dfsVisit(Variable *v, std::list<Variable*> *order);
202 void removeBlock(Block *doomed);
203 Variables const &vs;
204 int nvs;
205 };
207 extern long blockTimeCtr;
209 struct UnsatisfiableException {
210 Constraints path;
211 };
212 struct UnsatisfiedConstraint {
213 UnsatisfiedConstraint(Constraint& c):c(c) {}
214 Constraint& c;
215 };
216 /*
217 * Variable Placement with Separation Constraints problem instance
218 */
219 class IncSolver {
220 public:
221 unsigned splitCnt;
222 bool satisfy();
223 bool solve();
224 void moveBlocks();
225 void splitBlocks();
226 IncSolver(Variables const &vs, Constraints const &cs);
228 ~IncSolver();
229 Variables const & getVariables() { return vs; }
230 protected:
231 Blocks *bs;
232 unsigned m;
233 Constraints const &cs;
234 unsigned n;
235 Variables const &vs;
236 void printBlocks();
237 void copyResult();
238 private:
239 bool constraintGraphIsCyclic(const unsigned n, Variable* const vs[]);
240 bool blockGraphIsCyclic();
241 Constraints inactive;
242 Constraints violated;
243 Constraint* mostViolated(Constraints &l);
244 };
246 struct delete_object
247 {
248 template <typename T>
249 void operator()(T *ptr){ delete ptr;}
250 };
253 }
255 #endif // AVOID_VPSC_H