← Back to branch summary

~centralelyon2010/inkscape/imagelinks2

« back to all changes in this revision

Viewing changes to src/removeoverlap/solve_VPSC.cpp

  • Committer: tgdwyer
  • Date: 2006-07-12 00:55:58 UTC
  • Revision ID: tgdwyer@users.sourceforge.net-20060712005558-4pqys3ou7f5er3dm
Previously graph layout was done using the Kamada-Kawai layout algorithm 
implemented in Boost.  I am replacing this with a custom implementation of
a constrained stress-majorization algorithm.

The stress-majorization algorithm is more robust and has better convergence
characteristics than Kamada-Kawai, and also simple constraints can be placed
on node position (for example, to enforce downward-pointing edges, non-overlap constraints, or cluster constraints).

Another big advantage is that we no longer need Boost.

I've tested the basic functionality, but I have yet to properly handle
disconnected graphs or to properly scale the resulting layout.

This commit also includes significant refactoring... the quadratic program solver - libvpsc (Variable Placement with Separation Constraints) has been moved to src/libvpsc and the actual graph layout algorithm is in libcola.

Show diffs side-by-side

added added

removed removed

Lines of Context:
src/removeoverlap/solve_VPSC.cpp
1
 
/**
2
 
 * \brief Solve an instance of the "Variable Placement with Separation
3
 
 * Constraints" problem.
4
 
 *
5
 
 * Authors:
6
 
 *   Tim Dwyer <tgdwyer@gmail.com>
7
 
 *
8
 
 * Copyright (C) 2005 Authors
9
 
 *
10
 
 * Released under GNU LGPL.  Read the file 'COPYING' for more information.
11
 
 */
12
 
 
13
 
#include <cassert>
14
 
#include "constraint.h"
15
 
#include "block.h"
16
 
#include "blocks.h"
17
 
#include "solve_VPSC.h"
18
 
#include <math.h>
19
 
#include <sstream>
20
 
#ifdef RECTANGLE_OVERLAP_LOGGING
21
 
#include <fstream>
22
 
using std::ios;
23
 
using std::ofstream;
24
 
using std::endl;
25
 
#endif
26
 
 
27
 
using std::ostringstream;
28
 
using std::list;
29
 
using std::set;
30
 
 
31
 
IncVPSC::IncVPSC(const unsigned n, Variable *vs[], const unsigned m, Constraint *cs[]) 
32
 
        : VPSC(n,vs,m,cs) {
33
 
        inactive.assign(cs,cs+m);
34
 
        for(ConstraintList::iterator i=inactive.begin();i!=inactive.end();++i) {
35
 
                (*i)->active=false;
36
 
        }
37
 
}
38
 
VPSC::VPSC(const unsigned n, Variable *vs[], const unsigned m, Constraint *cs[]) : cs(cs), m(m), vs(vs) {
39
 
        bs=new Blocks(n, vs);
40
 
#ifdef RECTANGLE_OVERLAP_LOGGING
41
 
        printBlocks();
42
 
        assert(!constraintGraphIsCyclic(n,vs));
43
 
#endif
44
 
}
45
 
VPSC::~VPSC() {
46
 
        delete bs;
47
 
}
48
 
 
49
 
// useful in debugging
50
 
void VPSC::printBlocks() {
51
 
#ifdef RECTANGLE_OVERLAP_LOGGING
52
 
        ofstream f(LOGFILE,ios::app);
53
 
        for(set<Block*>::iterator i=bs->begin();i!=bs->end();++i) {
54
 
                Block *b=*i;
55
 
                f<<"  "<<*b<<endl;
56
 
        }
57
 
        for(unsigned i=0;i<m;i++) {
58
 
                f<<"  "<<*cs[i]<<endl;
59
 
        }
60
 
#endif
61
 
}
62
 
/**
63
 
* Produces a feasible - though not necessarily optimal - solution by
64
 
* examining blocks in the partial order defined by the directed acyclic
65
 
* graph of constraints. For each block (when processing left to right) we
66
 
* maintain the invariant that all constraints to the left of the block
67
 
* (incoming constraints) are satisfied. This is done by repeatedly merging
68
 
* blocks into bigger blocks across violated constraints (most violated
69
 
* first) fixing the position of variables inside blocks relative to one
70
 
* another so that constraints internal to the block are satisfied.
71
 
*/
72
 
void VPSC::satisfy() {
73
 
        list<Variable*> *vs=bs->totalOrder();
74
 
        for(list<Variable*>::iterator i=vs->begin();i!=vs->end();++i) {
75
 
                Variable *v=*i;
76
 
                if(!v->block->deleted) {
77
 
                        bs->mergeLeft(v->block);
78
 
                }
79
 
        }
80
 
        bs->cleanup();
81
 
        for(unsigned i=0;i<m;i++) {
82
 
                if(cs[i]->slack()<-0.0000001) {
83
 
#ifdef RECTANGLE_OVERLAP_LOGGING
84
 
                        ofstream f(LOGFILE,ios::app);
85
 
                        f<<"Error: Unsatisfied constraint: "<<*cs[i]<<endl;
86
 
#endif
87
 
                        //assert(cs[i]->slack()>-0.0000001);
88
 
                        throw "Unsatisfied constraint";
89
 
                }
90
 
        }
91
 
        delete vs;
92
 
}
93
 
 
94
 
void VPSC::refine() {
95
 
        bool solved=false;
96
 
        // Solve shouldn't loop indefinately
97
 
        // ... but just to make sure we limit the number of iterations
98
 
        unsigned maxtries=100;
99
 
        while(!solved&&maxtries>0) {
100
 
                solved=true;
101
 
                maxtries--;
102
 
                for(set<Block*>::const_iterator i=bs->begin();i!=bs->end();++i) {
103
 
                        Block *b=*i;
104
 
                        b->setUpInConstraints();
105
 
                        b->setUpOutConstraints();
106
 
                }
107
 
                for(set<Block*>::const_iterator i=bs->begin();i!=bs->end();++i) {
108
 
                        Block *b=*i;
109
 
                        Constraint *c=b->findMinLM();
110
 
                        if(c!=NULL && c->lm<0) {
111
 
#ifdef RECTANGLE_OVERLAP_LOGGING
112
 
                                ofstream f(LOGFILE,ios::app);
113
 
                                f<<"Split on constraint: "<<*c<<endl;
114
 
#endif
115
 
                                // Split on c
116
 
                                Block *l=NULL, *r=NULL;
117
 
                                bs->split(b,l,r,c);
118
 
                                bs->cleanup();
119
 
                                // split alters the block set so we have to restart
120
 
                                solved=false;
121
 
                                break;
122
 
                        }
123
 
                }
124
 
        }
125
 
        for(unsigned i=0;i<m;i++) {
126
 
                if(cs[i]->slack()<-0.0000001) {
127
 
                        assert(cs[i]->slack()>-0.0000001);
128
 
                        throw "Unsatisfied constraint";
129
 
                }
130
 
        }
131
 
}
132
 
/**
133
 
 * Calculate the optimal solution. After using satisfy() to produce a
134
 
 * feasible solution, refine() examines each block to see if further
135
 
 * refinement is possible by splitting the block. This is done repeatedly
136
 
 * until no further improvement is possible.
137
 
 */
138
 
void VPSC::solve() {
139
 
        satisfy();
140
 
        refine();
141
 
}
142
 
 
143
 
void IncVPSC::solve() {
144
 
#ifdef RECTANGLE_OVERLAP_LOGGING
145
 
        ofstream f(LOGFILE,ios::app);
146
 
        f<<"solve_inc()..."<<endl;
147
 
#endif
148
 
        double lastcost,cost = bs->cost();
149
 
        do {
150
 
                lastcost=cost;
151
 
                satisfy();
152
 
                splitBlocks();
153
 
                cost = bs->cost();
154
 
#ifdef RECTANGLE_OVERLAP_LOGGING
155
 
        f<<"  cost="<<cost<<endl;
156
 
#endif
157
 
        } while(fabs(lastcost-cost)>0.0001);
158
 
}
159
 
/**
160
 
 * incremental version of satisfy that allows refinement after blocks are
161
 
 * moved.
162
 
 *
163
 
 *  - move blocks to new positions
164
 
 *  - repeatedly merge across most violated constraint until no more
165
 
 *    violated constraints exist
166
 
 *
167
 
 * Note: there is a special case to handle when the most violated constraint
168
 
 * is between two variables in the same block.  Then, we must split the block
169
 
 * over an active constraint between the two variables.  We choose the 
170
 
 * constraint with the most negative lagrangian multiplier. 
171
 
 */
172
 
void IncVPSC::satisfy() {
173
 
#ifdef RECTANGLE_OVERLAP_LOGGING
174
 
        ofstream f(LOGFILE,ios::app);
175
 
        f<<"satisfy_inc()..."<<endl;
176
 
#endif
177
 
        splitBlocks();
178
 
        long splitCtr = 0;
179
 
        Constraint* v = NULL;
180
 
        while((v=mostViolated(inactive))&&(v->equality || v->slack()<-0.000001)) {
181
 
                assert(!v->active);
182
 
                Block *lb = v->left->block, *rb = v->right->block;
183
 
                if(lb != rb) {
184
 
                        lb->merge(rb,v);
185
 
                } else {
186
 
                        if(splitCtr++>10000) {
187
 
                                throw "Cycle Error!";
188
 
                        }
189
 
                        // constraint is within block, need to split first
190
 
                        inactive.push_back(lb->splitBetween(v->left,v->right,lb,rb));
191
 
                        lb->merge(rb,v);
192
 
                        bs->insert(lb);
193
 
                }
194
 
        }
195
 
#ifdef RECTANGLE_OVERLAP_LOGGING
196
 
        f<<"  finished merges."<<endl;
197
 
#endif
198
 
        bs->cleanup();
199
 
        for(unsigned i=0;i<m;i++) {
200
 
                v=cs[i];
201
 
                if(v->slack()<-0.0000001) {
202
 
                        //assert(cs[i]->slack()>-0.0000001);
203
 
                        ostringstream s;
204
 
                        s<<"Unsatisfied constraint: "<<*v;
205
 
                        throw s.str().c_str();
206
 
                }
207
 
        }
208
 
#ifdef RECTANGLE_OVERLAP_LOGGING
209
 
        f<<"  finished cleanup."<<endl;
210
 
        printBlocks();
211
 
#endif
212
 
}
213
 
void IncVPSC::moveBlocks() {
214
 
#ifdef RECTANGLE_OVERLAP_LOGGING
215
 
        ofstream f(LOGFILE,ios::app);
216
 
        f<<"moveBlocks()..."<<endl;
217
 
#endif
218
 
        for(set<Block*>::const_iterator i(bs->begin());i!=bs->end();++i) {
219
 
                Block *b = *i;
220
 
                b->wposn = b->desiredWeightedPosition();
221
 
                b->posn = b->wposn / b->weight;
222
 
        }
223
 
#ifdef RECTANGLE_OVERLAP_LOGGING
224
 
        f<<"  moved blocks."<<endl;
225
 
#endif
226
 
}
227
 
void IncVPSC::splitBlocks() {
228
 
#ifdef RECTANGLE_OVERLAP_LOGGING
229
 
        ofstream f(LOGFILE,ios::app);
230
 
#endif
231
 
        moveBlocks();
232
 
        splitCnt=0;
233
 
        // Split each block if necessary on min LM
234
 
        for(set<Block*>::const_iterator i(bs->begin());i!=bs->end();++i) {
235
 
                Block* b = *i;
236
 
                Constraint* v=b->findMinLM();
237
 
                if(v!=NULL && v->lm < -0.0000001) {
238
 
                        assert(!v->equality);
239
 
#ifdef RECTANGLE_OVERLAP_LOGGING
240
 
                        f<<"    found split point: "<<*v<<" lm="<<v->lm<<endl;
241
 
#endif
242
 
                        splitCnt++;
243
 
                        Block *b = v->left->block, *l=NULL, *r=NULL;
244
 
                        assert(v->left->block == v->right->block);
245
 
                        double pos = b->posn;
246
 
                        b->split(l,r,v);
247
 
                        l->posn=r->posn=pos;
248
 
                        l->wposn = l->posn * l->weight;
249
 
                        r->wposn = r->posn * r->weight;
250
 
                        bs->insert(l);
251
 
                        bs->insert(r);
252
 
                        b->deleted=true;
253
 
                        inactive.push_back(v);
254
 
#ifdef RECTANGLE_OVERLAP_LOGGING
255
 
                        f<<"  new blocks: "<<*l<<" and "<<*r<<endl;
256
 
#endif
257
 
                }
258
 
        }
259
 
#ifdef RECTANGLE_OVERLAP_LOGGING
260
 
        f<<"  finished splits."<<endl;
261
 
#endif
262
 
        bs->cleanup();
263
 
}
264
 
 
265
 
/**
266
 
 * Scan constraint list for the most violated constraint, or the first equality
267
 
 * constraint
268
 
 */
269
 
Constraint* IncVPSC::mostViolated(ConstraintList &l) {
270
 
        double minSlack = DBL_MAX;
271
 
        Constraint* v=NULL;
272
 
#ifdef RECTANGLE_OVERLAP_LOGGING
273
 
        ofstream f(LOGFILE,ios::app);
274
 
        f<<"Looking for most violated..."<<endl;
275
 
#endif
276
 
        ConstraintList::iterator end = l.end();
277
 
        ConstraintList::iterator deletePoint = end;
278
 
        for(ConstraintList::iterator i=l.begin();i!=end;++i) {
279
 
                Constraint *c=*i;
280
 
                double slack = c->slack();
281
 
                if(c->equality || slack < minSlack) {
282
 
                        minSlack=slack; 
283
 
                        v=c;
284
 
                        deletePoint=i;
285
 
                        if(c->equality) break;
286
 
                }
287
 
        }
288
 
        // Because the constraint list is not order dependent we just
289
 
        // move the last element over the deletePoint and resize
290
 
        // downwards.  There is always at least 1 element in the
291
 
        // vector because of search.
292
 
        if(deletePoint != end && (minSlack<-0.0000001||v->equality)) {
293
 
                *deletePoint = l[l.size()-1];
294
 
                l.resize(l.size()-1);
295
 
        }
296
 
#ifdef RECTANGLE_OVERLAP_LOGGING
297
 
        f<<"  most violated is: "<<*v<<endl;
298
 
#endif
299
 
        return v;
300
 
}
301
 
 
302
 
#include <map>
303
 
using std::map;
304
 
using std::vector;
305
 
struct node {
306
 
        set<node*> in;
307
 
        set<node*> out;
308
 
};
309
 
// useful in debugging - cycles would be BAD
310
 
bool VPSC::constraintGraphIsCyclic(const unsigned n, Variable *vs[]) {
311
 
        map<Variable*, node*> varmap;
312
 
        vector<node*> graph;
313
 
        for(unsigned i=0;i<n;i++) {
314
 
                node *u=new node;
315
 
                graph.push_back(u);
316
 
                varmap[vs[i]]=u;
317
 
        }
318
 
        for(unsigned i=0;i<n;i++) {
319
 
                for(vector<Constraint*>::iterator c=vs[i]->in.begin();c!=vs[i]->in.end();++c) {
320
 
                        Variable *l=(*c)->left;
321
 
                        varmap[vs[i]]->in.insert(varmap[l]);
322
 
                }
323
 
 
324
 
                for(vector<Constraint*>::iterator c=vs[i]->out.begin();c!=vs[i]->out.end();++c) {
325
 
                        Variable *r=(*c)->right;
326
 
                        varmap[vs[i]]->out.insert(varmap[r]);
327
 
                }
328
 
        }
329
 
        while(graph.size()>0) {
330
 
                node *u=NULL;
331
 
                vector<node*>::iterator i=graph.begin();
332
 
                for(;i!=graph.end();++i) {
333
 
                        u=*i;
334
 
                        if(u->in.size()==0) {
335
 
                                break;
336
 
                        }
337
 
                }
338
 
                if(i==graph.end() && graph.size()>0) {
339
 
                        //cycle found!
340
 
                        return true;
341
 
                } else {
342
 
                        graph.erase(i);
343
 
                        for(set<node*>::iterator j=u->out.begin();j!=u->out.end();++j) {
344
 
                                node *v=*j;
345
 
                                v->in.erase(u);
346
 
                        }
347
 
                        delete u;
348
 
                }
349
 
        }
350
 
        for(unsigned i=0; i<graph.size(); ++i) {
351
 
                delete graph[i];
352
 
        }
353
 
        return false;
354
 
}
355
 
 
356
 
// useful in debugging - cycles would be BAD
357
 
bool VPSC::blockGraphIsCyclic() {
358
 
        map<Block*, node*> bmap;
359
 
        vector<node*> graph;
360
 
        for(set<Block*>::const_iterator i=bs->begin();i!=bs->end();++i) {
361
 
                Block *b=*i;
362
 
                node *u=new node;
363
 
                graph.push_back(u);
364
 
                bmap[b]=u;
365
 
        }
366
 
        for(set<Block*>::const_iterator i=bs->begin();i!=bs->end();++i) {
367
 
                Block *b=*i;
368
 
                b->setUpInConstraints();
369
 
                Constraint *c=b->findMinInConstraint();
370
 
                while(c!=NULL) {
371
 
                        Block *l=c->left->block;
372
 
                        bmap[b]->in.insert(bmap[l]);
373
 
                        b->deleteMinInConstraint();
374
 
                        c=b->findMinInConstraint();
375
 
                }
376
 
 
377
 
                b->setUpOutConstraints();
378
 
                c=b->findMinOutConstraint();
379
 
                while(c!=NULL) {
380
 
                        Block *r=c->right->block;
381
 
                        bmap[b]->out.insert(bmap[r]);
382
 
                        b->deleteMinOutConstraint();
383
 
                        c=b->findMinOutConstraint();
384
 
                }
385
 
        }
386
 
        while(graph.size()>0) {
387
 
                node *u=NULL;
388
 
                vector<node*>::iterator i=graph.begin();
389
 
                for(;i!=graph.end();++i) {
390
 
                        u=*i;
391
 
                        if(u->in.size()==0) {
392
 
                                break;
393
 
                        }
394
 
                }
395
 
                if(i==graph.end() && graph.size()>0) {
396
 
                        //cycle found!
397
 
                        return true;
398
 
                } else {
399
 
                        graph.erase(i);
400
 
                        for(set<node*>::iterator j=u->out.begin();j!=u->out.end();++j) {
401
 
                                node *v=*j;
402
 
                                v->in.erase(u);
403
 
                        }
404
 
                        delete u;
405
 
                }
406
 
        }
407
 
        for(unsigned i=0; i<graph.size(); i++) {
408
 
                delete graph[i];
409
 
        }
410
 
        return false;
411
 
}
412