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