← Back to branch summary

~centralelyon2010/inkscape/imagelinks2

« back to all changes in this revision

Viewing changes to src/removeoverlap/blocks.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/blocks.cpp
1
 
/**
2
 
 * \brief A block structure defined over the variables
3
 
 *
4
 
 * A block structure defined over the variables such that each block contains
5
 
 * 1 or more variables, with the invariant that all constraints inside a block
6
 
 * are satisfied by keeping the variables fixed relative to one another
7
 
 *
8
 
 * Authors:
9
 
 *   Tim Dwyer <tgdwyer@gmail.com>
10
 
 *
11
 
 * Copyright (C) 2005 Authors
12
 
 *
13
 
 * Released under GNU LGPL.  Read the file 'COPYING' for more information.
14
 
 */
15
 
 
16
 
#include "blocks.h"
17
 
#include "block.h"
18
 
#include "constraint.h"
19
 
#ifdef RECTANGLE_OVERLAP_LOGGING
20
 
#include <fstream>
21
 
using std::ios;
22
 
using std::ofstream;
23
 
using std::endl;
24
 
#endif
25
 
using std::set;
26
 
using std::vector;
27
 
using std::iterator;
28
 
using std::list;
29
 
using std::copy;
30
 
 
31
 
long blockTimeCtr;
32
 
 
33
 
Blocks::Blocks(const int n, Variable *vs[]) : vs(vs),nvs(n) {
34
 
        blockTimeCtr=0;
35
 
        for(int i=0;i<nvs;i++) {
36
 
                insert(new Block(vs[i]));
37
 
        }
38
 
}
39
 
Blocks::~Blocks(void)
40
 
{
41
 
        blockTimeCtr=0;
42
 
        for(set<Block*>::iterator i=begin();i!=end();++i) {
43
 
                delete *i;
44
 
        }
45
 
        clear();
46
 
}
47
 
 
48
 
/**
49
 
 * returns a list of variables with total ordering determined by the constraint 
50
 
 * DAG
51
 
 */
52
 
list<Variable*> *Blocks::totalOrder() {
53
 
        list<Variable*> *order = new list<Variable*>;
54
 
        for(int i=0;i<nvs;i++) {
55
 
                vs[i]->visited=false;
56
 
        }
57
 
        for(int i=0;i<nvs;i++) {
58
 
                if(vs[i]->in.size()==0) {
59
 
                        dfsVisit(vs[i],order);
60
 
                }
61
 
        }
62
 
        return order;
63
 
}
64
 
// Recursive depth first search giving total order by pushing nodes in the DAG
65
 
// onto the front of the list when we finish searching them
66
 
void Blocks::dfsVisit(Variable *v, list<Variable*> *order) {
67
 
        v->visited=true;
68
 
        vector<Constraint*>::iterator it=v->out.begin();
69
 
        for(;it!=v->out.end();++it) {
70
 
                Constraint *c=*it;
71
 
                if(!c->right->visited) {
72
 
                        dfsVisit(c->right, order);
73
 
                }
74
 
        }       
75
 
#ifdef RECTANGLE_OVERLAP_LOGGING
76
 
        ofstream f(LOGFILE,ios::app);
77
 
        f<<"  order="<<*v<<endl;
78
 
#endif
79
 
        order->push_front(v);
80
 
}
81
 
/**
82
 
 * Processes incoming constraints, most violated to least, merging with the
83
 
 * neighbouring (left) block until no more violated constraints are found
84
 
 */
85
 
void Blocks::mergeLeft(Block *r) {      
86
 
#ifdef RECTANGLE_OVERLAP_LOGGING
87
 
        ofstream f(LOGFILE,ios::app);
88
 
        f<<"mergeLeft called on "<<*r<<endl;
89
 
#endif
90
 
        r->timeStamp=++blockTimeCtr;
91
 
        r->setUpInConstraints();
92
 
        Constraint *c=r->findMinInConstraint();
93
 
        while (c != NULL && c->slack()<0) {
94
 
#ifdef RECTANGLE_OVERLAP_LOGGING
95
 
                f<<"mergeLeft on constraint: "<<*c<<endl;
96
 
#endif
97
 
                r->deleteMinInConstraint();
98
 
                Block *l = c->left->block;              
99
 
                if (l->in==NULL) l->setUpInConstraints();
100
 
                double dist = c->right->offset - c->left->offset - c->gap;
101
 
                if (r->vars->size() < l->vars->size()) {
102
 
                        dist=-dist;
103
 
                        std::swap(l, r);
104
 
                }
105
 
                blockTimeCtr++;
106
 
                r->merge(l, c, dist);
107
 
                r->mergeIn(l);
108
 
                r->timeStamp=blockTimeCtr;
109
 
                removeBlock(l);
110
 
                c=r->findMinInConstraint();
111
 
        }               
112
 
#ifdef RECTANGLE_OVERLAP_LOGGING
113
 
        f<<"merged "<<*r<<endl;
114
 
#endif
115
 
}       
116
 
/**
117
 
 * Symmetrical to mergeLeft
118
 
 */
119
 
void Blocks::mergeRight(Block *l) {     
120
 
#ifdef RECTANGLE_OVERLAP_LOGGING
121
 
        ofstream f(LOGFILE,ios::app);
122
 
        f<<"mergeRight called on "<<*l<<endl;
123
 
#endif  
124
 
        l->setUpOutConstraints();
125
 
        Constraint *c = l->findMinOutConstraint();
126
 
        while (c != NULL && c->slack()<0) {             
127
 
#ifdef RECTANGLE_OVERLAP_LOGGING
128
 
                f<<"mergeRight on constraint: "<<*c<<endl;
129
 
#endif
130
 
                l->deleteMinOutConstraint();
131
 
                Block *r = c->right->block;
132
 
                r->setUpOutConstraints();
133
 
                double dist = c->left->offset + c->gap - c->right->offset;
134
 
                if (l->vars->size() > r->vars->size()) {
135
 
                        dist=-dist;
136
 
                        std::swap(l, r);
137
 
                }
138
 
                l->merge(r, c, dist);
139
 
                l->mergeOut(r);
140
 
                removeBlock(r);
141
 
                c=l->findMinOutConstraint();
142
 
        }       
143
 
#ifdef RECTANGLE_OVERLAP_LOGGING
144
 
        f<<"merged "<<*l<<endl;
145
 
#endif
146
 
}
147
 
void Blocks::removeBlock(Block *doomed) {
148
 
        doomed->deleted=true;
149
 
        //erase(doomed);
150
 
}
151
 
void Blocks::cleanup() {
152
 
        vector<Block*> bcopy(begin(),end());
153
 
        for(vector<Block*>::iterator i=bcopy.begin();i!=bcopy.end();++i) {
154
 
                Block *b=*i;
155
 
                if(b->deleted) {
156
 
                        erase(b);
157
 
                        delete b;
158
 
                }
159
 
        }
160
 
}
161
 
/**
162
 
 * Splits block b across constraint c into two new blocks, l and r (c's left
163
 
 * and right sides respectively)
164
 
 */
165
 
void Blocks::split(Block *b, Block *&l, Block *&r, Constraint *c) {
166
 
        b->split(l,r,c);
167
 
#ifdef RECTANGLE_OVERLAP_LOGGING
168
 
        ofstream f(LOGFILE,ios::app);
169
 
        f<<"Split left: "<<*l<<endl;
170
 
        f<<"Split right: "<<*r<<endl;
171
 
#endif
172
 
        r->posn = b->posn;
173
 
        r->wposn = r->posn * r->weight;
174
 
        mergeLeft(l);
175
 
        // r may have been merged!
176
 
        r = c->right->block;
177
 
        r->wposn = r->desiredWeightedPosition();
178
 
        r->posn = r->wposn / r->weight;
179
 
        mergeRight(r);
180
 
        removeBlock(b);
181
 
 
182
 
        insert(l);
183
 
        insert(r);
184
 
}
185
 
/**
186
 
 * returns the cost total squared distance of variables from their desired
187
 
 * positions
188
 
 */
189
 
double Blocks::cost() {
190
 
        double c = 0;
191
 
        for(set<Block*>::iterator i=begin();i!=end();++i) {
192
 
                c += (*i)->cost();
193
 
        }
194
 
        return c;
195
 
}
196