← Back to branch summary

~ubuntu-branches/ubuntu/precise/inkscape/precise-updates

« back to all changes in this revision

Viewing changes to src/libavoid/vpsc.h

  • Committer: Bazaar Package Importer
  • Author(s): Alex Valavanis
  • Date: 2010-09-12 19:44:58 UTC
  • mfrom: (1.1.12 upstream) (45.1.3 maverick)
  • Revision ID: james.westby@ubuntu.com-20100912194458-4sjwmbl7dlsrk5dc
Tags: 0.48.0-1ubuntu1
https://launchpad.net/bugs/628048
https://launchpad.net/bugs/401567
https://launchpad.net/bugs/456248
https://launchpad.net/bugs/463602
https://launchpad.net/bugs/591986
https://launchpad.net/bugs/513319
* Merge with Debian unstable (LP: #628048, LP: #401567, LP: #456248, 
  LP: #463602, LP: #591986)
* debian/control: 
  - Ubuntu maintainers
  - Promote python-lxml, python-numpy, python-uniconvertor to Recommends.
  - Demote pstoedit to Suggests (universe package).
  - Suggests ttf-dejavu instead of ttf-bitstream-vera (LP: #513319)
* debian/rules:
  - Run intltool-update on build (Ubuntu-specific).
  - Add translation domain to .desktop files (Ubuntu-specific).
* debian/dirs:
  - Add usr/share/pixmaps.  Allow inkscape.xpm installation
* drop 50-poppler-API.dpatch (now upstream)
* drop 51-paste-in-unwritable-directory.dpatch (now upstream) 

Show diffs side-by-side

added added

removed removed

Lines of Context:
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