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