src/libcola/cola.h

   1 #ifndef COLA_H
   2 #define COLA_H
   3
   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"
  13
  14
  15 typedef vector<unsigned> Cluster;
  16 typedef vector<Cluster*> Clusters;
  17 namespace vpsc { class Rectangle; }
  18
  19 namespace cola {
  20     using vpsc::Rectangle;
  21     typedef pair<unsigned, unsigned> Edge;
  22
  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         virtual ~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);
  42
  43     // move the contents of each component so that the components do not
  44     // overlap.
  45     void separateComponents(const vector<Component*> &components);
  46
  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;
 112
 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() {}
 120
 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);
 155
 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         }
 162
 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);
 172
 173         void addLinearConstraints(LinearConstraints* linearConstraints);
 174
 175         void setupDummyVars();
 176
 177         virtual ~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