From cca66b9ec4e494c1d919bff0f71a820d8afab1fa Mon Sep 17 00:00:00 2001 From: Daniel Baumann Date: Sun, 7 Apr 2024 20:24:48 +0200 Subject: Adding upstream version 1.2.2. Signed-off-by: Daniel Baumann --- .../adaptagrams/libcola/tests/makefeasible.cpp | 368 +++++++++++++++++++++ 1 file changed, 368 insertions(+) create mode 100644 src/3rdparty/adaptagrams/libcola/tests/makefeasible.cpp (limited to 'src/3rdparty/adaptagrams/libcola/tests/makefeasible.cpp') diff --git a/src/3rdparty/adaptagrams/libcola/tests/makefeasible.cpp b/src/3rdparty/adaptagrams/libcola/tests/makefeasible.cpp new file mode 100644 index 0000000..4bfb082 --- /dev/null +++ b/src/3rdparty/adaptagrams/libcola/tests/makefeasible.cpp @@ -0,0 +1,368 @@ +/* + * 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 +#include +#include +#include +#include +#include +#include + +#include +#include + +#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 &edges, CompoundConstraints &ccs) { + edges.push_back(make_pair(u,v)); + ccs.push_back(new SeparationConstraint(vpsc::YDIM, u,v,5)); +} +vector random_dag(unsigned depth, unsigned maxbranch, unsigned &V, + CompoundConstraints &ccs) { + printf("DAG depth=%d\nmaxbranch=%d\nextraedgeprob%f\n",depth,maxbranch,EXTRAEDGEPROB); + vector edges; + unsigned lstart=0, lend=1; + V=0; + for(unsigned i=0;ifinalPosition==(*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<& edges) { + ofstream outfile("new.txt",ofstream::binary); + for(vector::iterator e=edges.begin();e!=edges.end();++e) { + outfile<<"node"<first<<",node"<second<& edges, + std::vector& routes, + std::vector& 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;igetMinX()+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;igetCentreX(),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 eps; + eps.push_back( new topology::EdgePoint( topologyNodes[e.first], + topology::EdgePoint::CENTRE)); + for(size_t j=1;j+1assertConvexBends(); + 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(nullptr); + //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 es = random_dag(DAGDEPTH,BRANCHFACTOR,V,ccs); + double defaultEdgeLength=40; + + cout << "V="<