1 #ifndef COLA_H
2 #define COLA_H
4 #include <utility>
5 #include <iterator>
6 #include <vector>
7 #include <algorithm>
8 #include <cmath>
9 #include <iostream>
10 #include <cassert>
11 #include "gradient_projection.h"
12 #include "straightener.h"
15 typedef vector<unsigned> Cluster;
16 typedef vector<Cluster*> Clusters;
17 namespace vpsc { class Rectangle; }
19 namespace cola {
20 using vpsc::Rectangle;
21 typedef pair<unsigned, unsigned> Edge;
23 // a graph component with a list of node_ids giving indices for some larger list of nodes
24 // for the nodes in this component, and a list of edges - node indices relative to this component
25 class Component {
26 public:
27 vector<unsigned> node_ids;
28 vector<Rectangle*> rects;
29 vector<Edge> edges;
30 SimpleConstraints scx, scy;
31 ~Component();
32 void moveRectangles(double x, double y);
33 Rectangle* getBoundingBox();
34 };
35 // for a graph of n nodes, return connected components
36 void connectedComponents(
37 const vector<Rectangle*> &rs,
38 const vector<Edge> &es,
39 const SimpleConstraints &scx,
40 const SimpleConstraints &scy,
41 vector<Component*> &components);
43 // move the contents of each component so that the components do not
44 // overlap.
45 void separateComponents(const vector<Component*> &components);
47 // defines references to three variables for which the goal function
48 // will be altered to prefer points u-b-v are in a linear arrangement
49 // such that b is placed at u+t(v-u).
50 struct LinearConstraint {
51 LinearConstraint(unsigned u, unsigned v, unsigned b, double w,
52 double frac_ub, double frac_bv,
53 double* X, double* Y)
54 : u(u),v(v),b(b),w(w),frac_ub(frac_ub),frac_bv(frac_bv),
55 tAtProjection(true)
56 {
57 assert(frac_ub<=1.0);
58 assert(frac_bv<=1.0);
59 assert(frac_ub>=0);
60 assert(frac_bv>=0);
61 if(tAtProjection) {
62 double uvx = X[v] - X[u],
63 uvy = Y[v] - Y[u],
64 vbx = X[b] - X[u],
65 vby = Y[b] - Y[u];
66 t = uvx * vbx + uvy * vby;
67 t/= uvx * uvx + uvy * uvy;
68 // p is the projection point of b on line uv
69 //double px = scalarProj * uvx + X[u];
70 //double py = scalarProj * uvy + Y[u];
71 // take t=|up|/|uv|
72 } else {
73 double numerator=X[b]-X[u];
74 double denominator=X[v]-X[u];
75 if(fabs(denominator)<0.001) {
76 // if line is close to vertical then use Y coords to compute T
77 numerator=Y[b]-Y[u];
78 denominator=Y[v]-Y[u];
79 }
80 if(fabs(denominator)<0.0001) {
81 denominator=1;
82 }
83 t=numerator/denominator;
84 }
85 duu=(1-t)*(1-t);
86 duv=t*(1-t);
87 dub=t-1;
88 dvv=t*t;
89 dvb=-t;
90 dbb=1;
91 //printf("New LC: t=%f\n",t);
92 }
93 unsigned u;
94 unsigned v;
95 unsigned b;
96 double w; // weight
97 double t;
98 // 2nd partial derivatives of the goal function
99 // (X[b] - (1-t) X[u] - t X[v])^2
100 double duu;
101 double duv;
102 double dub;
103 double dvv;
104 double dvb;
105 double dbb;
106 // Length of each segment as a fraction of the total edge length
107 double frac_ub;
108 double frac_bv;
109 bool tAtProjection;
110 };
111 typedef vector<LinearConstraint*> LinearConstraints;
113 class TestConvergence {
114 public:
115 double old_stress;
116 TestConvergence(const double& tolerance = 0.001, const unsigned maxiterations = 1000)
117 : tolerance(tolerance),
118 maxiterations(maxiterations) { reset(); }
119 virtual ~TestConvergence() {}
121 virtual bool operator()(double new_stress, double* X, double* Y) {
122 //std::cout<<"iteration="<<iterations<<", new_stress="<<new_stress<<std::endl;
123 if (old_stress == DBL_MAX) {
124 old_stress = new_stress;
125 if(++iterations>=maxiterations) {;
126 return true;
127 } else {
128 return false;
129 }
130 }
131 bool converged =
132 fabs(new_stress - old_stress) / (new_stress + 1e-10) < tolerance
133 || ++iterations > maxiterations;
134 old_stress = new_stress;
135 return converged;
136 }
137 void reset() {
138 old_stress = DBL_MAX;
139 iterations = 0;
140 }
141 private:
142 const double tolerance;
143 const unsigned maxiterations;
144 unsigned iterations;
145 };
146 static TestConvergence defaultTest(0.0001,100);
147 class ConstrainedMajorizationLayout {
148 public:
149 ConstrainedMajorizationLayout(
150 vector<Rectangle*>& rs,
151 vector<Edge>& es,
152 double* eweights,
153 double idealLength,
154 TestConvergence& done=defaultTest);
156 void moveBoundingBoxes() {
157 for(unsigned i=0;i<lapSize;i++) {
158 boundingBoxes[i]->moveCentreX(X[i]);
159 boundingBoxes[i]->moveCentreY(Y[i]);
160 }
161 }
163 void setupConstraints(
164 AlignmentConstraints* acsx, AlignmentConstraints* acsy,
165 bool avoidOverlaps,
166 PageBoundaryConstraints* pbcx = NULL,
167 PageBoundaryConstraints* pbcy = NULL,
168 SimpleConstraints* scx = NULL,
169 SimpleConstraints* scy = NULL,
170 Clusters* cs = NULL,
171 vector<straightener::Edge*>* straightenEdges = NULL);
173 void addLinearConstraints(LinearConstraints* linearConstraints);
175 void setupDummyVars();
177 ~ConstrainedMajorizationLayout() {
178 if(boundingBoxes) {
179 delete [] boundingBoxes;
180 }
181 if(constrainedLayout) {
182 delete gpX;
183 delete gpY;
184 }
185 for(unsigned i=0;i<lapSize;i++) {
186 delete [] lap2[i];
187 delete [] Dij[i];
188 }
189 delete [] lap2;
190 delete [] Dij;
191 delete [] X;
192 delete [] Y;
193 }
194 bool run();
195 void straighten(vector<straightener::Edge*>&, Dim);
196 bool avoidOverlaps;
197 bool constrainedLayout;
198 private:
199 double euclidean_distance(unsigned i, unsigned j) {
200 return sqrt(
201 (X[i] - X[j]) * (X[i] - X[j]) +
202 (Y[i] - Y[j]) * (Y[i] - Y[j]));
203 }
204 double compute_stress(double **Dij);
205 void majlayout(double** Dij,GradientProjection* gp, double* coords);
206 void majlayout(double** Dij,GradientProjection* gp, double* coords,
207 double* b);
208 unsigned n; // is lapSize + dummyVars
209 unsigned lapSize; // lapSize is the number of variables for actual nodes
210 double** lap2; // graph laplacian
211 double** Q; // quadratic terms matrix used in computations
212 double** Dij;
213 double tol;
214 TestConvergence& done;
215 Rectangle** boundingBoxes;
216 double *X, *Y;
217 Clusters* clusters;
218 double edge_length;
219 LinearConstraints *linearConstraints;
220 GradientProjection *gpX, *gpY;
221 vector<straightener::Edge*>* straightenEdges;
222 };
223 }
224 #endif // COLA_H
225 // vim: filetype=cpp:expandtab:shiftwidth=4:tabstop=4:softtabstop=4