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