src/libavoid/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 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 };
  63
  64 typedef std::priority_queue<Constraint*,std::vector<Constraint*>,
  65         CompareConstraints> Heap;
  66
  67 class Block
  68 {
  69     typedef Variables::iterator Vit;
  70     typedef Constraints::iterator Cit;
  71     typedef Constraints::const_iterator Cit_const;
  72
  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 };
 122
 123
 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 };
 166
 167
 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 };
 206
 207 extern long blockTimeCtr;
 208
 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);
 227
 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 };
 245
 246 struct delete_object
 247 {
 248     template <typename T>
 249     void operator()(T *ptr){ delete ptr;}
 250 };
 251
 252
 253 }
 254
 255 #endif // AVOID_VPSC_H