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