summaryrefslogtreecommitdiffstats
path: root/src/3rdparty/adaptagrams/libcola/cola.cpp
diff options
context:
space:
mode:
Diffstat (limited to 'src/3rdparty/adaptagrams/libcola/cola.cpp')
-rw-r--r--src/3rdparty/adaptagrams/libcola/cola.cpp700
1 files changed, 700 insertions, 0 deletions
diff --git a/src/3rdparty/adaptagrams/libcola/cola.cpp b/src/3rdparty/adaptagrams/libcola/cola.cpp
new file mode 100644
index 0000000..739c6ea
--- /dev/null
+++ b/src/3rdparty/adaptagrams/libcola/cola.cpp
@@ -0,0 +1,700 @@
+/*
+ * vim: ts=4 sw=4 et tw=0 wm=0
+ *
+ * libcola - A library providing force-directed network layout using the
+ * stress-majorization method subject to separation constraints.
+ *
+ * Copyright (C) 2006-2014 Monash University
+ *
+ * This library is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU Lesser General Public
+ * License as published by the Free Software Foundation; either
+ * version 2.1 of the License, or (at your option) any later version.
+ * See the file LICENSE.LGPL distributed with the library.
+ *
+ * This library is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
+ *
+ * Author(s): Tim Dwyer
+*/
+
+#include <cmath>
+
+#include "libvpsc/assertions.h"
+#include "libcola/commondefs.h"
+#include "libcola/cola.h"
+#include "libcola/conjugate_gradient.h"
+#include "libcola/straightener.h"
+#include "libcola/shortest_paths.h"
+#include "libcola/cluster.h"
+
+using namespace std;
+using namespace vpsc;
+using straightener::generateClusterBoundaries;
+
+namespace cola {
+
+ConstrainedMajorizationLayout
+::ConstrainedMajorizationLayout(
+ vector<Rectangle*>& rs,
+ const vector<Edge>& es,
+ RootCluster *clusterHierarchy,
+ const double idealLength,
+ EdgeLengths eLengths,
+ TestConvergence *doneTest,
+ PreIteration* preIteration,
+ bool useNeighbourStress)
+ : n(rs.size()),
+ lap2(valarray<double>(n*n)),
+ Dij(valarray<double>(n*n)),
+ tol(1e-7),
+ done(doneTest),
+ using_default_done(false),
+ preIteration(preIteration),
+ X(valarray<double>(n)), Y(valarray<double>(n)),
+ stickyNodes(false),
+ startX(valarray<double>(n)), startY(valarray<double>(n)),
+ constrainedLayout(false),
+ nonOverlappingClusters(false),
+ clusterHierarchy(clusterHierarchy),
+ gpX(nullptr), gpY(nullptr),
+ ccs(nullptr),
+ unsatisfiableX(nullptr), unsatisfiableY(nullptr),
+ avoidOverlaps(None),
+ straightenEdges(nullptr),
+ bendWeight(0.1), potBendWeight(0.1),
+ xSkipping(true),
+ scaling(true),
+ externalSolver(false),
+ majorization(true)
+{
+ if (done == nullptr)
+ {
+ done = new TestConvergence();
+ using_default_done = true;
+ }
+
+ boundingBoxes.resize(rs.size());
+ copy(rs.begin(),rs.end(),boundingBoxes.begin());
+
+ done->reset();
+
+ COLA_ASSERT(!straightenEdges||straightenEdges->size()==es.size());
+
+ double** D=new double*[n];
+ for(unsigned i=0;i<n;i++) {
+ D[i]=new double[n];
+ }
+
+ std::valarray<double> edgeLengths(eLengths.data(), eLengths.size());
+ // Correct zero or negative entries in eLengths array.
+ for (size_t i = 0; i < edgeLengths.size(); ++i)
+ {
+ if (edgeLengths[i] <= 0)
+ {
+ fprintf(stderr, "Warning: ignoring non-positive length at index %d "
+ "in ideal edge length array.\n", (int) i);
+ edgeLengths[i] = 1;
+ }
+ }
+
+ if (useNeighbourStress) {
+ for(unsigned i=0;i<n;i++) {
+ for(unsigned j=0;j<n;j++) {
+ D[i][j]=std::numeric_limits<double>::max();
+ }
+ }
+ bool haveLengths = edgeLengths.size() == es.size();
+ for (unsigned i = 0; i < es.size(); i++) {
+ unsigned source = es[i].first;
+ unsigned target = es[i].second;
+ D[source][target] = D[target][source] = (haveLengths ? edgeLengths[i] : 1.0);
+ }
+ } else {
+ shortest_paths::johnsons(n,D,es,edgeLengths);
+ //shortest_paths::neighbours(n,D,es,edgeLengths);
+ }
+
+ edge_length = idealLength;
+ if(clusterHierarchy) {
+ for(Clusters::const_iterator i=clusterHierarchy->clusters.begin();
+ i!=clusterHierarchy->clusters.end();i++) {
+ Cluster *c=*i;
+ for(set<unsigned>::iterator j=c->nodes.begin();j!=c->nodes.end();j++) {
+ for(set<unsigned>::iterator k=c->nodes.begin();k!=c->nodes.end();k++) {
+ unsigned a=*j, b=*k;
+ if(a==b) continue;
+ D[a][b]/=c->internalEdgeWeightFactor;
+ }
+ }
+ }
+ }
+ // Lij_{i!=j}=1/(Dij^2)
+ //
+ for(unsigned i = 0; i<n; i++) {
+ X[i]=rs[i]->getCentreX();
+ Y[i]=rs[i]->getCentreY();
+ double degree = 0;
+ for(unsigned j=0;j<n;j++) {
+ double d = edge_length * D[i][j];
+ Dij[i*n + j] = d;
+ if(i==j) continue;
+ double lij=0;
+ if(d!=0 && !std::isinf(d)) {
+ lij=1./(d*d);
+ }
+ degree += lap2[i*n + j] = lij;
+ }
+ lap2[i*n + i]=-degree;
+ delete [] D[i];
+ }
+ //GradientProjection::dumpSquareMatrix(Dij);
+ delete [] D;
+}
+// stickyNodes adds a small force attracting nodes
+// back to their starting positions
+void ConstrainedMajorizationLayout::setStickyNodes(
+ const double stickyWeight,
+ valarray<double> const & startX,
+ valarray<double> const & startY) {
+ COLA_ASSERT( startX.size()==n && startY.size()==n);
+ stickyNodes = true;
+ // not really constrained but we want to use GP solver rather than
+ // ConjugateGradient
+ constrainedLayout = true;
+ this->stickyWeight=stickyWeight;
+ this->startX = startX;
+ this->startY = startY;
+ for(unsigned i = 0; i<n; i++) {
+ lap2[i*n+i]-=stickyWeight;
+ }
+}
+
+void ConstrainedMajorizationLayout::majorize(
+ valarray<double> const & Dij, GradientProjection* gp,
+ valarray<double>& coords,
+ valarray<double> const & startCoords)
+{
+ double L_ij,dist_ij,degree;
+ /* compute the vector b */
+ /* multiply on-the-fly with distance-based laplacian */
+ valarray<double> b(n);
+ for (unsigned i = 0; i < n; i++) {
+ b[i] = degree = 0;
+ for (unsigned j = 0; j < n; j++) {
+ if (j == i) continue;
+ dist_ij = euclidean_distance(i, j);
+ /* skip zero distances */
+ if (dist_ij > 1e-30 && Dij[i*n+j] > 1e-30 && Dij[i*n+j] < 1e10) {
+ /* calculate L_ij := w_{ij}*d_{ij}/dist_{ij} */
+ L_ij = 1.0 / (dist_ij * Dij[i*n+j]);
+ degree -= L_ij;
+ b[i] += L_ij * coords[j];
+ }
+ }
+ if(stickyNodes) {
+ //double l = startCoords[i]-coords[i];
+ //l/=10.;
+ //b[i]-=stickyWeight*(coords[i]+l);
+ b[i] -= stickyWeight*startCoords[i];
+ }
+ b[i] += degree * coords[i];
+ COLA_ASSERT(!std::isnan(b[i]));
+ }
+ if(constrainedLayout) {
+ //printf("GP iteration...\n");
+ gp->solve(b,coords);
+ } else {
+ //printf("CG iteration...\n");
+ conjugate_gradient(lap2, coords, b, n, tol, n);
+ }
+ moveBoundingBoxes();
+}
+void ConstrainedMajorizationLayout::newton(
+ valarray<double> const & Dij, GradientProjection* gp,
+ valarray<double>& coords,
+ valarray<double> const & startCoords)
+{
+ COLA_UNUSED(startCoords);
+ /* compute the vector b */
+ /* multiply on-the-fly with distance-based laplacian */
+ valarray<double> b(n);
+ valarray<double> A(n*n);
+ for (unsigned i = 0; i < n; i++) {
+ b[i] = 0;
+ double Aii = 0;
+ for (unsigned j = 0; j < n; j++) {
+ if (j == i) continue;
+ double d = Dij[i*n+j];
+ double l = euclidean_distance(i,j);
+ double dx = coords[i]-coords[j];
+ double dy2 = l*l - dx*dx;
+ /* skip zero distances */
+ if (l > 1e-30
+ && d > 1e-30 && d < 1e10) {
+ if(d>80 && l > d) continue;
+ b[i]+=dx*(l-d)/(l*d*d);
+ Aii-=A[i*n+j]=(d*dy2/(l*l*l)-1)/(d*d);
+ }
+ }
+ A[i*n+i]=Aii;
+ }
+ if(constrainedLayout) {
+ //printf("GP iteration...\n");
+ gp->solve(b,coords);
+ } else {
+ //printf("CG iteration...\n");
+ /*
+ unsigned N=n-1;
+ valarray<double> b2(N);
+ valarray<double> A2(N*N);
+ valarray<double> x(N);
+ for(unsigned i=0;i<N;i++) {
+ b2=b[i];
+ x=coords[i];
+ for(unsigned j=0;j<N;j++) {
+ A2[i*N+j]=A[i*n+j];
+ }
+ }
+ conjugate_gradient(A2, x, b2, N, tol, N);
+ */
+ //valarray<double> x=coords;
+ //x-=x.sum()/n;
+ //conjugate_gradient(A, x, b, n, tol, n);
+ //double stepsize=0.5;
+ valarray<double> x=b;
+ // stepsize = g.g / (g A g)
+ double numerator = 0;
+ for(unsigned i=0;i<n;i++) {
+ numerator+=x[i]*x[i];
+ }
+ double denominator = 0;
+ for(unsigned i=0;i<n;i++) {
+ double r=0;
+ for(unsigned j=0;j<n;j++) {
+ r+=A[i*n+j]*x[j];
+ }
+ denominator+=r*x[i];
+ }
+ double stepsize=numerator/(2*denominator);
+ double oldstress=compute_stress(Dij);
+ valarray<double> oldcoords=coords;
+ while(stepsize>0.00001) {
+ coords=oldcoords-stepsize*x;
+ double stress=compute_stress(Dij);
+ printf(" stress=%f, stepsize=%f\n",stress,stepsize);
+ if(oldstress>=stress) {
+ break;
+ }
+ coords=oldcoords;
+ stepsize*=0.5;
+ }
+ }
+ moveBoundingBoxes();
+}
+inline double ConstrainedMajorizationLayout
+::compute_stress(valarray<double> const &Dij) {
+ double sum = 0, d, diff;
+ for (unsigned i = 1; i < n; i++) {
+ for (unsigned j = 0; j < i; j++) {
+ d = Dij[i*n+j];
+ if(!std::isinf(d)&&d!=numeric_limits<double>::max()) {
+ diff = d - euclidean_distance(i,j);
+ if(d>80&&diff<0) continue;
+ sum += diff*diff / (d*d);
+ }
+ }
+ if(stickyNodes) {
+ double l = startX[i]-X[i];
+ sum += stickyWeight*l*l;
+ l = startY[i]-Y[i];
+ sum += stickyWeight*l*l;
+ }
+ }
+ //printf("stress=%f\n",sum);
+ return sum;
+}
+
+void ConstrainedMajorizationLayout::run(bool x, bool y) {
+ if(constrainedLayout) {
+ vector<vpsc::Rectangle*>* pbb = boundingBoxes.empty()?nullptr:&boundingBoxes;
+ SolveWithMosek mosek = Off;
+ if(externalSolver) mosek=Outer;
+ // scaling doesn't currently work with straighten edges because sparse
+ // matrix used with dummy nodes is not properly scaled at the moment.
+ if(straightenEdges) setScaling(false);
+ gpX=new GradientProjection(
+ HORIZONTAL,&lap2,tol,100,ccs,unsatisfiableX,
+ avoidOverlaps,clusterHierarchy,pbb,scaling,mosek);
+ gpY=new GradientProjection(
+ VERTICAL,&lap2,tol,100,ccs,unsatisfiableY,
+ avoidOverlaps,clusterHierarchy,pbb,scaling,mosek);
+ }
+ if(n>0) do {
+ // to enforce clusters with non-intersecting, convex boundaries we
+ // could create cluster boundaries here with chains of dummy nodes (a
+ // dummy node for each vertex of the convex hull) connected by dummy
+ // straightenEdges and we'd then continue on to straightenEdges below.
+ // This should work assuming we already have a feasible (i.e. non
+ // overlapping cluster) state. The former could be enforced by an
+ // earlier stage involving simple rectangular cluster boundaries.
+ vector<straightener::Edge*> cedges;
+ if(!straightenEdges && nonOverlappingClusters) {
+ straightenEdges = &cedges;
+ }
+ if(preIteration) {
+ if ((*preIteration)()) {
+ for(vector<Lock>::iterator l=preIteration->locks.begin();
+ l!=preIteration->locks.end();l++) {
+ unsigned id=l->getID();
+ double x=l->pos(HORIZONTAL), y=l->pos(VERTICAL);
+ X[id]=x;
+ Y[id]=y;
+ if(stickyNodes) {
+ startX[id]=x;
+ startY[id]=y;
+ }
+ boundingBoxes[id]->moveCentre(x,y);
+ if(constrainedLayout) {
+ gpX->fixPos(id,X[id]);
+ gpY->fixPos(id,Y[id]);
+ }
+ }
+ } else { break; }
+ }
+ /* Axis-by-axis optimization: */
+ if(straightenEdges) {
+ if(x) straighten(*straightenEdges,HORIZONTAL);
+ if(y) straighten(*straightenEdges,VERTICAL);
+ } else {
+ if(majorization) {
+ if(x) majorize(Dij,gpX,X,startX);
+ if(y) majorize(Dij,gpY,Y,startY);
+ } else {
+ if(x) newton(Dij,gpX,X,startX);
+ if(y) newton(Dij,gpY,Y,startY);
+ }
+ }
+ if(clusterHierarchy) {
+ for(Clusters::iterator c=clusterHierarchy->clusters.begin();
+ c!=clusterHierarchy->clusters.end();c++) {
+ (*c)->computeBoundary(boundingBoxes);
+ }
+ }
+ if(preIteration && constrainedLayout) {
+ for(vector<Lock>::iterator l=preIteration->locks.begin();
+ l!=preIteration->locks.end();l++) {
+ gpX->unfixPos(l->getID());
+ gpY->unfixPos(l->getID());
+ }
+ }
+ } while(!(*done)(compute_stress(Dij),X,Y));
+}
+double ConstrainedMajorizationLayout::computeStress() {
+ return compute_stress(Dij);
+}
+void ConstrainedMajorizationLayout::runOnce(bool x, bool y) {
+ if(constrainedLayout) {
+ vector<vpsc::Rectangle*>* pbb = boundingBoxes.empty()?nullptr:&boundingBoxes;
+ SolveWithMosek mosek = Off;
+ if(externalSolver) mosek=Outer;
+ // scaling doesn't currently work with straighten edges because sparse
+ // matrix used with dummy nodes is not properly scaled at the moment.
+ if(straightenEdges) setScaling(false);
+ gpX=new GradientProjection(
+ HORIZONTAL,&lap2,tol,100,ccs,unsatisfiableX,
+ avoidOverlaps,clusterHierarchy,pbb,scaling,mosek);
+ gpY=new GradientProjection(
+ VERTICAL,&lap2,tol,100,ccs,unsatisfiableY,
+ avoidOverlaps,clusterHierarchy,pbb,scaling,mosek);
+ }
+ if(n>0) {
+ // to enforce clusters with non-intersecting, convex boundaries we
+ // could create cluster boundaries here with chains of dummy nodes (a
+ // dummy node for each vertex of the convex hull) connected by dummy
+ // straightenEdges and we'd then continue on to straightenEdges below.
+ // This should work assuming we already have a feasible (i.e. non
+ // overlapping cluster) state. The former could be enforced by an
+ // earlier stage involving simple rectangular cluster boundaries.
+ vector<straightener::Edge*> cedges;
+ if(!straightenEdges && nonOverlappingClusters) {
+ straightenEdges = &cedges;
+ }
+ if(preIteration) {
+ if ((*preIteration)()) {
+ for(vector<Lock>::iterator l=preIteration->locks.begin();
+ l!=preIteration->locks.end();l++) {
+ unsigned id=l->getID();
+ double x=l->pos(HORIZONTAL), y=l->pos(VERTICAL);
+ X[id]=x;
+ Y[id]=y;
+ if(stickyNodes) {
+ startX[id]=x;
+ startY[id]=y;
+ }
+ boundingBoxes[id]->moveCentre(x,y);
+ if(constrainedLayout) {
+ gpX->fixPos(id,X[id]);
+ gpY->fixPos(id,Y[id]);
+ }
+ }
+ } else { return; }
+ }
+ /* Axis-by-axis optimization: */
+ if(straightenEdges) {
+ if(x) straighten(*straightenEdges,HORIZONTAL);
+ if(y) straighten(*straightenEdges,VERTICAL);
+ } else {
+ if(majorization) {
+ if(x) majorize(Dij,gpX,X,startX);
+ if(y) majorize(Dij,gpY,Y,startY);
+ } else {
+ if(x) newton(Dij,gpX,X,startX);
+ if(y) newton(Dij,gpY,Y,startY);
+ }
+ }
+ if(clusterHierarchy) {
+ for(Clusters::iterator c=clusterHierarchy->clusters.begin();
+ c!=clusterHierarchy->clusters.end();c++) {
+ (*c)->computeBoundary(boundingBoxes);
+ }
+ }
+ if(preIteration && constrainedLayout) {
+ for(vector<Lock>::iterator l=preIteration->locks.begin();
+ l!=preIteration->locks.end();l++) {
+ gpX->unfixPos(l->getID());
+ gpY->unfixPos(l->getID());
+ }
+ }
+ }
+}
+void ConstrainedMajorizationLayout::straighten(vector<straightener::Edge*>& sedges, Dim dim) {
+ GradientProjection * gp;
+ valarray<double>* coords;
+ valarray<double>* startCoords;
+ if(dim==HORIZONTAL) {
+ gp=gpX;
+ coords=&X;
+ startCoords=&startX;
+ } else {
+ gp=gpY;
+ coords=&Y;
+ startCoords=&startY;
+ }
+ vector<straightener::Node*> snodes;
+ if(dim==HORIZONTAL) {
+ Rectangle::setXBorder(0.0001);
+ }
+ for (unsigned i=0;i<n;i++) {
+ snodes.push_back(new straightener::Node(i,boundingBoxes[i]));
+ }
+ if(dim==HORIZONTAL) {
+ Rectangle::setXBorder(0);
+ }
+ for (unsigned i=n;i<gp->getNumStaticVars();i++) {
+ // insert some dummy nodes
+ snodes.push_back(new straightener::Node(i,-100,-100));
+ }
+ vector<straightener::Cluster*> sclusters;
+
+ if(nonOverlappingClusters && clusterHierarchy) {
+ generateClusterBoundaries(dim,snodes,sedges,boundingBoxes,
+ *clusterHierarchy,sclusters);
+ }
+ vector<SeparationConstraint*> cs;
+ straightener::generateConstraints(dim,snodes,sedges,cs,xSkipping);
+ straightener::LinearConstraints linearConstraints;
+ for(unsigned i=0;i<sedges.size();i++) {
+ sedges[i]->nodePath(snodes,!nonOverlappingClusters);
+ vector<unsigned>& path=sedges[i]->path;
+ vector<unsigned>& activePath=sedges[i]->activePath;
+ // take u and v as the ends of the line
+ // unsigned u=path[0];
+ // unsigned v=path[path.size()-1];
+ double total_length=0;
+ for(unsigned j=1;j<path.size();j++) {
+ unsigned u=path[j-1], v=path[j];
+ total_length+=snodes[u]->euclidean_distance(snodes[v]);
+ }
+ // keep potential bends straight
+ for(unsigned j=1;j<activePath.size();j++) {
+ unsigned uj=activePath[j-1], vj=activePath[j];
+ unsigned u=path[uj], v=path[vj];
+ for(unsigned k=uj+1;k<vj;k++) {
+ unsigned b=path[k];
+ // might be useful to have greater weight for potential bends than actual bends
+ linearConstraints.push_back(new straightener::LinearConstraint(
+ *snodes[u],*snodes[v],*snodes[b],-potBendWeight));
+ }
+ }
+ // straighten actual bends
+ for(unsigned j=1;j<activePath.size()-1;j++) {
+ unsigned u=path[activePath[j-1]],
+ b=path[activePath[j]],
+ v=path[activePath[j+1]];
+ linearConstraints.push_back(new straightener::LinearConstraint(
+ *snodes[u],*snodes[v],*snodes[b],-bendWeight));
+ }
+ }
+ //std::cout << (dim==HORIZONTAL?"X":"Y") << " snodes.size "<<snodes.size()<< " n="<<n<<std::endl;
+ //std::cout << "Generated "<<linearConstraints.size()<< " linear constraints"<<std::endl;
+ SparseMap Q(snodes.size());
+ for(straightener::LinearConstraints::iterator i=linearConstraints.begin();
+ i!= linearConstraints.end();i++) {
+ straightener::LinearConstraint* c=*i;
+ Q(c->u,c->u)+=c->w*c->duu;
+ Q(c->u,c->v)+=c->w*c->duv;
+ Q(c->u,c->b)+=c->w*c->dub;
+ Q(c->v,c->u)+=c->w*c->duv;
+ Q(c->v,c->v)+=c->w*c->dvv;
+ Q(c->v,c->b)+=c->w*c->dvb;
+ Q(c->b,c->b)+=c->w*c->dbb;
+ Q(c->b,c->u)+=c->w*c->dub;
+ Q(c->b,c->v)+=c->w*c->dvb;
+ }
+ double boundaryWeight = 0.0001;
+ for(unsigned i=0;i<sclusters.size();i++) {
+ // for each cluster boundary chain create an attractive force between
+ // each pair of adjacent nodes
+ straightener::Cluster* c = sclusters[i];
+ for(unsigned j=0;j<c->boundary.size();j++) {
+ straightener::Edge* e = c->boundary[j];
+ Q(e->startNode,e->endNode)+=boundaryWeight;
+ Q(e->endNode,e->startNode)+=boundaryWeight;
+ Q(e->startNode,e->startNode)-=boundaryWeight;
+ Q(e->endNode,e->endNode)-=boundaryWeight;
+ }
+ }
+ constrainedLayout = true;
+ SparseMatrix sparseQ(Q);
+ gp->straighten(&sparseQ,cs,snodes);
+ //return;
+ majorize(Dij,gp,*coords,*startCoords);
+ valarray<double> const & r=gp->getFullResult();
+ for(unsigned i=0;i<snodes.size();i++) {
+ snodes[i]->pos[dim] = r[i];
+ }
+ for(unsigned i=0;i<sedges.size();i++) {
+ sedges[i]->createRouteFromPath(snodes);
+ sedges[i]->dummyNodes.clear();
+ sedges[i]->path.clear();
+ }
+ for(unsigned i=0;i<sclusters.size();i++) {
+ straightener::Cluster *sc = sclusters[i];
+ //sc->updateActualBoundary();
+ delete sc;
+ }
+ for(unsigned i=0;i<cs.size();i++) {
+ delete cs[i];
+ }
+ for(unsigned i=0;i<linearConstraints.size();i++) {
+ delete linearConstraints[i];
+ }
+ for(unsigned i=0;i<snodes.size();i++) {
+ delete snodes[i];
+ }
+}
+
+Rectangle bounds(vector<Rectangle*>& rs) {
+ COLA_ASSERT(!rs.empty());
+
+ double left = rs[0]->getMinX(), right = rs[0]->getMaxX(),
+ top = rs[0]->getMinY(), bottom = rs[0]->getMaxY();
+
+ for(unsigned i = 1; i < rs.size(); i++) {
+ left = min(left,rs[i]->getMinX());
+ right = max(right,rs[i]->getMaxX());
+ top = min(top,rs[i]->getMinY());
+ bottom = max(bottom,rs[i]->getMaxY());
+ }
+ return Rectangle(left, right, top, bottom);
+}
+
+#if 0
+ void removeClusterOverlap(RootCluster& clusterHierarchy, vpsc::Rectangles& rs, Locks& locks, vpsc::Dim dim) {
+ if(clusterHierarchy.nodes.size()>0 || clusterHierarchy.clusters.size()>0) {
+ vpsc::Variables vars;
+ vpsc::Constraints cs;
+ for(unsigned i=0;i<rs.size();i++) {
+ vars.push_back(new vpsc::Variable(i, rs[i]->getCentreD(dim)));
+ }
+
+ clusterHierarchy.computeBoundingRect(rs);
+ clusterHierarchy.createVars(dim,rs,vars);
+ clusterHierarchy.generateNonOverlapConstraints(dim, cola::Both, rs, vars, cs);
+
+ /*
+ if(dim==vpsc::HORIZONTAL) {
+ vpsc::Rectangle::setXBorder(0.001);
+ // use rs->size() rather than n because some of the variables may
+ // be dummy vars with no corresponding rectangle
+ generateXConstraints(rs,vars,cs,true);
+ vpsc::Rectangle::setXBorder(0);
+ } else {
+ generateYConstraints(rs,vars,cs);
+ }
+ */
+ for(Locks::iterator l=locks.begin();
+ l!=locks.end();l++) {
+ unsigned id=l->getID();
+ double x=l->pos(HORIZONTAL), y=l->pos(VERTICAL);
+ Variable* v=vars[id];
+ v->desiredPosition = (dim==vpsc::HORIZONTAL)?x:y;
+ v->weight = 1000;
+ }
+ /*
+ vpsc::Solver s(vars,cs);
+ try {
+ s.satisfy();
+ } catch(const char* e) {
+ cerr << "ERROR from solver in GraphData::removeOverlap : " << e << endl;
+ }
+ */
+ vpsc::IncSolver s(vars,cs);
+ try {
+ s.solve();
+ } catch(const char* e) {
+ cerr << "ERROR from solver in GraphData::removeOverlap : " << e << endl;
+ }
+ clusterHierarchy.updateBounds(dim);
+ /*
+ for(unsigned i=0;i<cs.size();++i) {
+ if(cs[i]->unsatisfiable) {
+ cout << "Unsatisfiable constraint: " << *cs[i] << endl;
+ }
+ }
+ */
+ for(unsigned i=0;i<rs.size();i++) {
+ rs[i]->moveCentreD(dim,vars[i]->finalPosition);
+ }
+ for(Locks::iterator l=locks.begin();
+ l!=locks.end();l++) {
+ //unsigned id=l->getID();
+ }
+ for_each(vars.begin(),vars.end(),delete_object());
+ for_each(cs.begin(),cs.end(),delete_object());
+ }
+ }
+ void removeClusterOverlapFast(RootCluster& clusterHierarchy, vpsc::Rectangles& rs, Locks& locks) {
+ removeClusterOverlap(clusterHierarchy, rs, locks, vpsc::HORIZONTAL);
+ removeClusterOverlap(clusterHierarchy, rs, locks, vpsc::VERTICAL);
+ }
+#endif
+
+ ConstrainedMajorizationLayout* simpleCMLFactory(
+ vpsc::Rectangles& rs,
+ std::vector<Edge> const & es,
+ RootCluster* clusterHierarchy,
+ const double idealLength,
+ bool useNeighbourStress
+ ) {
+ cola::EdgeLengths eLengths;
+ for(size_t i = 0; i < es.size(); ++i) {
+ eLengths.push_back(1);
+ }
+ return new ConstrainedMajorizationLayout(rs, es, clusterHierarchy, idealLength,
+ eLengths, nullptr, nullptr, useNeighbourStress);
+ };
+
+} // namespace cola
generated by cgit v1.2.3 (git 2.39.1) at 2024-06-18 03:12:15 +0000