summaryrefslogtreecommitdiffstats
path: root/src/libcola/tests/makefeasible.cpp
diff options
context:
space:
mode:
Diffstat (limited to 'src/libcola/tests/makefeasible.cpp')
-rw-r--r--src/libcola/tests/makefeasible.cpp366
1 files changed, 0 insertions, 366 deletions
diff --git a/src/libcola/tests/makefeasible.cpp b/src/libcola/tests/makefeasible.cpp
deleted file mode 100644
index a67936de8..000000000
--- a/src/libcola/tests/makefeasible.cpp
+++ /dev/null
@@ -1,366 +0,0 @@
-/*
- * 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-2008 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.
- *
- * 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. See the GNU
- * Lesser General Public License for more details.
- *
- * You should have received a copy of the GNU Lesser General Public
- * License along with this library in the file LICENSE; if not,
- * write to the Free Software Foundation, Inc., 59 Temple Place,
- * Suite 330, Boston, MA 02111-1307 USA
- *
-*/
-
-#include <iostream>
-#include <vector>
-#include <cmath>
-#include <time.h>
-#include <valarray>
-#include <fstream>
-#include <libavoid/libavoid.h>
-#include <libavoid/router.h>
-
-#include "graphlayouttest.h"
-
-using namespace std;
-using namespace cola;
-using namespace vpsc;
-
-/*
-// |V|=12, |E|=23
-static const unsigned DAGDEPTH = 3;
-static const unsigned BRANCHFACTOR = 3;
-static const double EXTRAEDGEPROB = 0.5;
-*/
-/*
-// |V|=26, |E|=61
-static const unsigned DAGDEPTH = 3;
-static const unsigned BRANCHFACTOR = 4;
-static const double EXTRAEDGEPROB = 0.1;
-*/
-
-/*
-// |V|=62, |E|=85
-static const unsigned DAGDEPTH = 4;
-static const unsigned BRANCHFACTOR = 4;
-static const double EXTRAEDGEPROB = 0.01;
-*/
-/*
-// |V|=131, |E|=166
-static const unsigned DAGDEPTH = 5;
-static const unsigned BRANCHFACTOR = 4;
-static const double EXTRAEDGEPROB = 0.005;
-*/
-
-static const unsigned DAGDEPTH = 6;
-static const unsigned BRANCHFACTOR = 4;
-static const double EXTRAEDGEPROB = 0.002;
-/*
-// |V|=343, |E|=487
-seed=1208390913;
-static const unsigned DAGDEPTH = 6;
-static const unsigned BRANCHFACTOR = 4;
-static const double EXTRAEDGEPROB = 0.002;
-*/
-
-void makeEdge(unsigned u, unsigned v,
- vector<Edge> &edges, CompoundConstraints &ccs) {
- edges.push_back(make_pair(u,v));
- ccs.push_back(new SeparationConstraint(vpsc::YDIM, u,v,5));
-}
-vector<Edge> random_dag(unsigned depth, unsigned maxbranch, unsigned &V,
- CompoundConstraints &ccs) {
- printf("DAG depth=%d\nmaxbranch=%d\nextraedgeprob%f\n",depth,maxbranch,EXTRAEDGEPROB);
- vector<Edge> edges;
- unsigned lstart=0, lend=1;
- V=0;
- for(unsigned i=0;i<depth;i++) {
- for(unsigned j=lstart;j<lend;j++) {
- //makeEdge(j,++V,edges,cy);
- //makeEdge(j,++V,edges,cy);
- for(unsigned k=0;k<maxbranch;k++) {
- double r=(double)rand()/(double)RAND_MAX;
- if(r < 0.5) {
- makeEdge(j,++V,edges,ccs);
- }
- }
- }
- lstart=lend;
- lend=V+1;
- }
- V++;
- /*
- DFS::Graph dfs(V,edges);
- for(unsigned i=1;i<dfs.order.size();i++) {
- cx.push_back(
- new SeparationConstraint(dfs.order[i-1],dfs.order[i],0.5));
- }
- */
- for(unsigned i=0;i<V;++i) {
- for(unsigned j=i+1;j<V;++j) {
- double r=(double)rand()/(double)RAND_MAX;
- if(r < EXTRAEDGEPROB) {
- makeEdge(i,j,edges,ccs);
- }
- }
- }
- /*
- for(unsigned i=0;i<dfs.leaves.size();i++) {
- for(unsigned j=1;j<dfs.leaves[i].size();j++) {
- cx.push_back( new SeparationConstraint(dfs.leaves[i][j-1],dfs.leaves[i][j],10));
- }
- }
- */
- return edges;
-}
-void removeoverlaps(vpsc::Rectangles &rs, bool bothaxes) {
- double xBorder=0, yBorder=0;
- static const double EXTRA_GAP=1e-5;
- unsigned n=rs.size();
- try {
- // The extra gap avoids numerical imprecision problems
- Rectangle::setXBorder(xBorder+EXTRA_GAP);
- Rectangle::setYBorder(yBorder+EXTRA_GAP);
- vpsc::Variables vs(n);
- unsigned i=0;
- for(Variables::iterator v=vs.begin();v!=vs.end();++v,++i) {
- *v=new Variable(i,0,1);
- }
- vpsc::Constraints cs;
- vpsc::generateXConstraints(rs,vs,cs,bothaxes);
- vpsc::IncSolver vpsc_x(vs,cs);
- vpsc_x.solve();
- vpsc::Rectangles::iterator r=rs.begin();
- for(Variables::iterator v=vs.begin();v!=vs.end();++v,++r) {
- assert((*v)->finalPosition==(*v)->finalPosition);
- (*r)->moveCentreX((*v)->finalPosition);
- }
- assert(r==rs.end());
- for_each(cs.begin(),cs.end(),vpsc::delete_object());
- cs.clear();
- if(bothaxes) {
- // Removing the extra gap here ensures things that were moved to be adjacent to one another above are not considered overlapping
- Rectangle::setXBorder(Rectangle::xBorder-EXTRA_GAP);
- vpsc::generateYConstraints(rs,vs,cs);
- vpsc::IncSolver vpsc_y(vs,cs);
- vpsc_y.solve();
- r=rs.begin();
- for(Variables::iterator v=vs.begin();v!=vs.end();++v,++r) {
- (*r)->moveCentreY((*v)->finalPosition);
- }
- for_each(cs.begin(),cs.end(),vpsc::delete_object());
- cs.clear();
- Rectangle::setYBorder(Rectangle::yBorder-EXTRA_GAP);
- vpsc::generateXConstraints(rs,vs,cs,false);
- vpsc::IncSolver vpsc_x2(vs,cs);
- vpsc_x2.solve();
- r=rs.begin();
- for(Variables::iterator v=vs.begin();v!=vs.end();++v,++r) {
- (*r)->moveCentreX((*v)->finalPosition);
- }
- for_each(cs.begin(),cs.end(),vpsc::delete_object());
- }
- for_each(vs.begin(),vs.end(),vpsc::delete_object());
- } catch (char *str) {
- std::cerr<<str<<std::endl;
- for(vpsc::Rectangles::iterator r=rs.begin();r!=rs.end();++r) {
- std::cerr << **r <<std::endl;
- }
- }
- Rectangle::setXBorder(xBorder);
- Rectangle::setYBorder(yBorder);
-}
-/*
-void writeTextFile(vector<cola::Edge>& edges) {
- ofstream outfile("new.txt",ofstream::binary);
- for(vector<cola::Edge>::iterator e=edges.begin();e!=edges.end();++e) {
- outfile<<"node"<<e->first<<",node"<<e->second<<endl;
- }
- outfile.close();
-}
-*/
-/*
- * Make feasible:
- * - remove overlaps between rectangular boundaries of nodes/clusters
- * (respecting structural constraints)
- * - perform routing (preserve previous topology using rubber banding)
- */
-void makeFeasible(vpsc::Rectangles& rs, vector<cola::Edge>& edges,
- std::vector<topology::Edge*>& routes,
- std::vector<topology::Node*>& topologyNodes, double defaultEdgeLength) {
- printf("Removing overlaps...\n");
- removeoverlaps(rs,false);
- printf("done.\n");
- printf("Running libavoid to compute routes...\n");
- clock_t libavoidstarttime=clock();
- // find feasible routes for edges
- Avoid::Router *router = new Avoid::Router(Avoid::PolyLineRouting);
- // Use rotational sweep for point visibility
- router->UseLeesAlgorithm = true;
- // Don't use invisibility graph.
- router->InvisibilityGrph = false;
- double g=0; // make shape that libavoid sees slightly smaller
- for(unsigned i=0;i<rs.size();++i) {
- vpsc::Rectangle* r=rs[i];
- double x=r->getMinX()+g;
- double X=r->getMaxX()-g;
- double y=r->getMinY()+g;
- double Y=r->getMaxY()-g;
- // Create the ShapeRef:
- Avoid::Polygon shapePoly(4);
- // AntiClockwise!
- shapePoly.ps[0] = Avoid::Point(X,y);
- shapePoly.ps[1] = Avoid::Point(X,Y);
- shapePoly.ps[2] = Avoid::Point(x,Y);
- shapePoly.ps[3] = Avoid::Point(x,y);
- //if(i==4||i==13||i==9) {
- //printf("rect[%d]:{%f,%f,%f,%f}\n",i,x,y,X,Y);
- //}
- unsigned int shapeID = i + 1;
- Avoid::ShapeRef *shapeRef = new Avoid::ShapeRef(router, shapePoly,
- shapeID);
- // ShapeRef constructor makes a copy of polygon so we can free it:
- router->addShape(shapeRef);
- }
- for(unsigned i=0;i<edges.size();++i) {
- cola::Edge e=edges[i];
- Avoid::ConnRef *connRef;
- unsigned int connID = i + rs.size() + 1;
- Rectangle* r0=rs[e.first], *r1=rs[e.second];
- Avoid::Point srcPt(r0->getCentreX(),r0->getCentreY());
- Avoid::Point dstPt(r1->getCentreX(),r1->getCentreY());
- connRef = new Avoid::ConnRef(router, srcPt, dstPt, connID);
- router->processTransaction();
- const Avoid::Polygon& route = connRef->route();
- vector<topology::EdgePoint*> eps;
- eps.push_back( new topology::EdgePoint( topologyNodes[e.first],
- topology::EdgePoint::CENTRE));
- for(size_t j=1;j+1<route.size();j++) {
- const Avoid::Point& p = route.ps[j];
- const unsigned nodeID=p.id-1;
- topology::Node* node=topologyNodes[nodeID];
- topology::EdgePoint::RectIntersect ri;
- switch(p.vn) {
- case 0: ri=topology::EdgePoint::BR;
- break;
- case 1: ri=topology::EdgePoint::TR;
- break;
- case 2: ri=topology::EdgePoint::TL;
- break;
- case 3: ri=topology::EdgePoint::BL;
- break;
- default: ri=topology::EdgePoint::CENTRE;
- }
- eps.push_back(new topology::EdgePoint(node,ri));
- }
- eps.push_back(new topology::EdgePoint(topologyNodes[e.second],
- topology::EdgePoint::CENTRE));
- topology::Edge* edgeRoute=new topology::Edge(i,defaultEdgeLength, eps);
- edgeRoute->assertConvexBends();
- routes.push_back(edgeRoute);
-
- }
- writeFile(topologyNodes,routes,"beautify0.svg");
- assert(topology::assertNoSegmentRectIntersection(topologyNodes,routes));
- double libavoidtime=double(clock()-libavoidstarttime)/double(CLOCKS_PER_SEC);
- cout << "done. Libavoid ran in " << libavoidtime << " seconds" << endl;
- delete router;
-}
-int main() {
- unsigned V;
- CompoundConstraints ccs;
-
- int seed = time(NULL);
- //seed=1207906420;
- //seed=1207920674;
- //seed=1207982613;
- //seed=1207984219;
- seed=1207984299;
- //seed=1207984743;
- //seed=1207985027; // very short edge which seems to cause problems
- //seed=1207986026; // error if we don't check neighbour is actually on scanline when determining visibility when generating straight constraints
- //seed=1207991731;
- //seed=1208303930;
- //seed=1208304508;
- //seed=1208316284;
- //seed=1208319019;
- //seed=1208321702;
- printf("random seed=%d\n",seed);
- srand(seed);
- vector<Edge> es = random_dag(DAGDEPTH,BRANCHFACTOR,V,ccs);
- double defaultEdgeLength=40;
-
- cout << "V="<<V<<endl;
- cout << "E="<<es.size()<<endl;
- double width=700;
- double height=700;
- vector<pair<double,double> > startpos(V);
- for(unsigned i=0;i<V;i++) {
- double x=getRand(width), y=getRand(height);
- startpos[i]=make_pair(x,y);
- }
- vector<vpsc::Rectangle*> rs;
- vector<topology::Node*> topologyNodes;
- vector<topology::Edge*> routes;
- for(unsigned i=0;i<V;i++) {
- double x=getRand(width), y=getRand(height);
- vpsc::Rectangle* r =new vpsc::Rectangle(x,x+30,y,y+10);
- rs.push_back(r);
- topologyNodes.push_back(new topology::Node(i,r));
- }
- CheckProgress test(0.01,100);
- clock_t unconstrainedstarttime=clock();
- //writeTextFile(es);
- es.clear();
- ConstrainedFDLayout alg2(rs,es,defaultEdgeLength,NULL,test);
- //alg2.setConstraints(&ccs);
-
- alg2.makeFeasible(true);
- alg2.run();
-
- alg2.outputInstanceToSVG();
-#if 0
- double totaltime=0;
- double unconstrainedtime=double(clock()-unconstrainedstarttime)/double(CLOCKS_PER_SEC);
- totaltime+=unconstrainedstarttime;
- cout<<"unconstrained layout ran in "<<unconstrainedtime<<" seconds"<<endl;
- clock_t makefeasiblestarttime=clock();
- makeFeasible(rs,es,routes,topologyNodes,defaultEdgeLength);
- double makefeasibletime=double(clock()-makefeasiblestarttime)/double(CLOCKS_PER_SEC);
- totaltime+=makefeasibletime;
- cout<<"makefeasible ran in "<<makefeasibletime<<" seconds"<<endl;
- clock_t beautifystarttime=clock();
- test.reset();
- alg2.setTopology(&topologyNodes, &routes);
- writeFile(topologyNodes,routes,"beautify1.svg");
- char dunnartfile[50];
- sprintf(dunnartfile, "v%de%d.svg", V, (int) es.size());
- writeDunnartFile(topologyNodes,es,dunnartfile);
-
- alg2.run();
- double beautifytime=double(clock()-beautifystarttime)/double(CLOCKS_PER_SEC);
- totaltime+=beautifytime;
- cout<<"beautify ran in "<<beautifytime<<" seconds"<<endl;
- cout<<"TOTAL="<<totaltime<<endl;
- cout <<"---------------------------------------------"<< endl;
- cout <<V<<" & "<<es.size()<<" & "<<unconstrainedtime<<" & "<<makefeasibletime<<" & "<<beautifytime<<" & "<<totaltime<<" \\\\ % Seed: "<< seed <<endl;
- writeFile(topologyNodes,routes,"beautify2.svg");
-#endif
- for(unsigned i=0;i<V;i++) {
- delete rs[i];
- }
- return 0;
-}
-// vim: filetype=cpp:expandtab:shiftwidth=4:tabstop=4:softtabstop=4:textwidth=99 :
generated by cgit v1.2.3 (git 2.25.1) at 2026-05-19 17:06:22 +0000