alpar@507: /* -*- mode: C++; indent-tabs-mode: nil; -*- alpar@507: * alpar@507: * This file is a part of LEMON, a generic C++ optimization library. alpar@507: * alpar@507: * Copyright (C) 2003-2009 alpar@507: * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport alpar@507: * (Egervary Research Group on Combinatorial Optimization, EGRES). alpar@507: * alpar@507: * Permission to use, modify and distribute this software is granted alpar@507: * provided that this copyright notice appears in all copies. For alpar@507: * precise terms see the accompanying LICENSE file. alpar@507: * alpar@507: * This software is provided "AS IS" with no warranty of any kind, alpar@507: * express or implied, and with no claim as to its suitability for any alpar@507: * purpose. alpar@507: * alpar@507: */ alpar@507: alpar@507: /// \ingroup tools alpar@507: /// \file alpar@507: /// \brief Special plane digraph generator. alpar@507: /// alpar@507: /// Graph generator application for various types of plane graphs. alpar@507: /// alpar@507: /// See kpeter@576: /// \code kpeter@576: /// lgf-gen --help kpeter@576: /// \endcode alpar@507: /// for more info on the usage. alpar@507: alpar@507: #include alpar@507: #include ladanyi@562: #include alpar@507: #include alpar@507: #include alpar@507: #include alpar@507: #include alpar@507: #include alpar@507: #include alpar@507: #include alpar@507: #include alpar@507: #include alpar@507: #include alpar@507: #include alpar@507: #include alpar@507: #include alpar@507: alpar@507: using namespace lemon; alpar@507: alpar@507: typedef dim2::Point Point; alpar@507: alpar@507: GRAPH_TYPEDEFS(ListGraph); alpar@507: alpar@507: bool progress=true; alpar@507: alpar@507: int N; alpar@507: // int girth; alpar@507: alpar@507: ListGraph g; alpar@507: alpar@507: std::vector nodes; alpar@507: ListGraph::NodeMap coords(g); alpar@507: alpar@507: alpar@507: double totalLen(){ alpar@507: double tlen=0; alpar@507: for(EdgeIt e(g);e!=INVALID;++e) alpar@604: tlen+=std::sqrt((coords[g.v(e)]-coords[g.u(e)]).normSquare()); alpar@507: return tlen; alpar@507: } alpar@507: alpar@507: int tsp_impr_num=0; alpar@507: alpar@507: const double EPSILON=1e-8; alpar@507: bool tsp_improve(Node u, Node v) alpar@507: { alpar@507: double luv=std::sqrt((coords[v]-coords[u]).normSquare()); alpar@507: Node u2=u; alpar@507: Node v2=v; alpar@507: do { alpar@507: Node n; alpar@507: for(IncEdgeIt e(g,v2);(n=g.runningNode(e))==u2;++e) { } alpar@507: u2=v2; alpar@507: v2=n; alpar@507: if(luv+std::sqrt((coords[v2]-coords[u2]).normSquare())-EPSILON> alpar@507: std::sqrt((coords[u]-coords[u2]).normSquare())+ alpar@507: std::sqrt((coords[v]-coords[v2]).normSquare())) alpar@507: { alpar@507: g.erase(findEdge(g,u,v)); alpar@507: g.erase(findEdge(g,u2,v2)); alpar@507: g.addEdge(u2,u); alpar@507: g.addEdge(v,v2); alpar@507: tsp_impr_num++; alpar@507: return true; alpar@507: } alpar@507: } while(v2!=u); alpar@507: return false; alpar@507: } alpar@507: alpar@507: bool tsp_improve(Node u) alpar@507: { alpar@507: for(IncEdgeIt e(g,u);e!=INVALID;++e) alpar@507: if(tsp_improve(u,g.runningNode(e))) return true; alpar@507: return false; alpar@507: } alpar@507: alpar@507: void tsp_improve() alpar@507: { alpar@507: bool b; alpar@507: do { alpar@507: b=false; alpar@507: for(NodeIt n(g);n!=INVALID;++n) alpar@507: if(tsp_improve(n)) b=true; alpar@507: } while(b); alpar@507: } alpar@507: alpar@507: void tsp() alpar@507: { alpar@507: for(int i=0;i" << l.b; alpar@507: return os; alpar@507: } alpar@507: alpar@507: bool cross(Line a, Line b) alpar@507: { alpar@507: Point ao=rot90(a.b-a.a); alpar@507: Point bo=rot90(b.b-b.a); alpar@507: return (ao*(b.a-a.a))*(ao*(b.b-a.a))<0 && alpar@507: (bo*(a.a-b.a))*(bo*(a.b-b.a))<0; alpar@507: } alpar@507: alpar@507: struct Parc alpar@507: { alpar@507: Node a; alpar@507: Node b; alpar@507: double len; alpar@507: }; alpar@507: alpar@507: bool pedgeLess(Parc a,Parc b) alpar@507: { alpar@507: return a.len arcs; alpar@507: alpar@507: namespace _delaunay_bits { alpar@507: alpar@507: struct Part { alpar@507: int prev, curr, next; alpar@507: alpar@507: Part(int p, int c, int n) : prev(p), curr(c), next(n) {} alpar@507: }; alpar@507: alpar@507: inline std::ostream& operator<<(std::ostream& os, const Part& part) { alpar@507: os << '(' << part.prev << ',' << part.curr << ',' << part.next << ')'; alpar@507: return os; alpar@507: } alpar@507: alpar@507: inline double circle_point(const Point& p, const Point& q, const Point& r) { alpar@507: double a = p.x * (q.y - r.y) + q.x * (r.y - p.y) + r.x * (p.y - q.y); alpar@507: if (a == 0) return std::numeric_limits::quiet_NaN(); alpar@507: alpar@507: double d = (p.x * p.x + p.y * p.y) * (q.y - r.y) + alpar@507: (q.x * q.x + q.y * q.y) * (r.y - p.y) + alpar@507: (r.x * r.x + r.y * r.y) * (p.y - q.y); alpar@507: alpar@507: double e = (p.x * p.x + p.y * p.y) * (q.x - r.x) + alpar@507: (q.x * q.x + q.y * q.y) * (r.x - p.x) + alpar@507: (r.x * r.x + r.y * r.y) * (p.x - q.x); alpar@507: alpar@507: double f = (p.x * p.x + p.y * p.y) * (q.x * r.y - r.x * q.y) + alpar@507: (q.x * q.x + q.y * q.y) * (r.x * p.y - p.x * r.y) + alpar@507: (r.x * r.x + r.y * r.y) * (p.x * q.y - q.x * p.y); alpar@507: alpar@604: return d / (2 * a) + std::sqrt((d * d + e * e) / (4 * a * a) + f / a); alpar@507: } alpar@507: alpar@507: inline bool circle_form(const Point& p, const Point& q, const Point& r) { alpar@507: return rot90(q - p) * (r - q) < 0.0; alpar@507: } alpar@507: alpar@507: inline double intersection(const Point& p, const Point& q, double sx) { alpar@507: const double epsilon = 1e-8; alpar@507: alpar@507: if (p.x == q.x) return (p.y + q.y) / 2.0; alpar@507: alpar@507: if (sx < p.x + epsilon) return p.y; alpar@507: if (sx < q.x + epsilon) return q.y; alpar@507: alpar@507: double a = q.x - p.x; alpar@507: double b = (q.x - sx) * p.y - (p.x - sx) * q.y; alpar@507: double d = (q.x - sx) * (p.x - sx) * (p - q).normSquare(); alpar@604: return (b - std::sqrt(d)) / a; alpar@507: } alpar@507: alpar@507: struct YLess { alpar@507: alpar@507: alpar@507: YLess(const std::vector& points, double& sweep) alpar@507: : _points(points), _sweep(sweep) {} alpar@507: alpar@507: bool operator()(const Part& l, const Part& r) const { alpar@507: const double epsilon = 1e-8; alpar@507: alpar@507: // std::cerr << l << " vs " << r << std::endl; alpar@507: double lbx = l.prev != -1 ? alpar@507: intersection(_points[l.prev], _points[l.curr], _sweep) : alpar@507: - std::numeric_limits::infinity(); alpar@507: double rbx = r.prev != -1 ? alpar@507: intersection(_points[r.prev], _points[r.curr], _sweep) : alpar@507: - std::numeric_limits::infinity(); alpar@507: double lex = l.next != -1 ? alpar@507: intersection(_points[l.curr], _points[l.next], _sweep) : alpar@507: std::numeric_limits::infinity(); alpar@507: double rex = r.next != -1 ? alpar@507: intersection(_points[r.curr], _points[r.next], _sweep) : alpar@507: std::numeric_limits::infinity(); alpar@507: alpar@507: if (lbx > lex) std::swap(lbx, lex); alpar@507: if (rbx > rex) std::swap(rbx, rex); alpar@507: alpar@507: if (lex < epsilon + rex && lbx + epsilon < rex) return true; alpar@507: if (rex < epsilon + lex && rbx + epsilon < lex) return false; alpar@507: return lex < rex; alpar@507: } alpar@507: alpar@507: const std::vector& _points; alpar@507: double& _sweep; alpar@507: }; alpar@507: alpar@507: struct BeachIt; alpar@507: alpar@507: typedef std::multimap SpikeHeap; alpar@507: alpar@507: typedef std::multimap Beach; alpar@507: alpar@507: struct BeachIt { alpar@507: Beach::iterator it; alpar@507: alpar@507: BeachIt(Beach::iterator iter) : it(iter) {} alpar@507: }; alpar@507: alpar@507: } alpar@507: alpar@507: inline void delaunay() { alpar@507: Counter cnt("Number of arcs added: "); alpar@507: alpar@507: using namespace _delaunay_bits; alpar@507: alpar@507: typedef _delaunay_bits::Part Part; alpar@507: typedef std::vector > SiteHeap; alpar@507: alpar@507: alpar@507: std::vector points; alpar@507: std::vector nodes; alpar@507: alpar@507: for (NodeIt it(g); it != INVALID; ++it) { alpar@507: nodes.push_back(it); alpar@507: points.push_back(coords[it]); alpar@507: } alpar@507: alpar@507: SiteHeap siteheap(points.size()); alpar@507: alpar@507: double sweep; alpar@507: alpar@507: alpar@507: for (int i = 0; i < int(siteheap.size()); ++i) { alpar@507: siteheap[i] = std::make_pair(points[i].x, i); alpar@507: } alpar@507: alpar@507: std::sort(siteheap.begin(), siteheap.end()); alpar@507: sweep = siteheap.front().first; alpar@507: alpar@507: YLess yless(points, sweep); alpar@507: Beach beach(yless); alpar@507: alpar@507: SpikeHeap spikeheap; alpar@507: alpar@507: std::set > arcs; alpar@507: alpar@507: int siteindex = 0; alpar@507: { alpar@507: SiteHeap front; alpar@507: alpar@507: while (siteindex < int(siteheap.size()) && alpar@507: siteheap[0].first == siteheap[siteindex].first) { alpar@507: front.push_back(std::make_pair(points[siteheap[siteindex].second].y, alpar@507: siteheap[siteindex].second)); alpar@507: ++siteindex; alpar@507: } alpar@507: alpar@507: std::sort(front.begin(), front.end()); alpar@507: alpar@507: for (int i = 0; i < int(front.size()); ++i) { alpar@507: int prev = (i == 0 ? -1 : front[i - 1].second); alpar@507: int curr = front[i].second; alpar@507: int next = (i + 1 == int(front.size()) ? -1 : front[i + 1].second); alpar@507: alpar@507: beach.insert(std::make_pair(Part(prev, curr, next), alpar@507: spikeheap.end())); alpar@507: } alpar@507: } alpar@507: alpar@507: while (siteindex < int(points.size()) || !spikeheap.empty()) { alpar@507: alpar@507: SpikeHeap::iterator spit = spikeheap.begin(); alpar@507: alpar@507: if (siteindex < int(points.size()) && alpar@507: (spit == spikeheap.end() || siteheap[siteindex].first < spit->first)) { alpar@507: int site = siteheap[siteindex].second; alpar@507: sweep = siteheap[siteindex].first; alpar@507: alpar@507: Beach::iterator bit = beach.upper_bound(Part(site, site, site)); alpar@507: alpar@507: if (bit->second != spikeheap.end()) { alpar@507: spikeheap.erase(bit->second); alpar@507: } alpar@507: alpar@507: int prev = bit->first.prev; alpar@507: int curr = bit->first.curr; alpar@507: int next = bit->first.next; alpar@507: alpar@507: beach.erase(bit); alpar@507: alpar@507: SpikeHeap::iterator pit = spikeheap.end(); alpar@507: if (prev != -1 && alpar@507: circle_form(points[prev], points[curr], points[site])) { alpar@507: double x = circle_point(points[prev], points[curr], points[site]); alpar@507: pit = spikeheap.insert(std::make_pair(x, BeachIt(beach.end()))); alpar@507: pit->second.it = alpar@507: beach.insert(std::make_pair(Part(prev, curr, site), pit)); alpar@507: } else { alpar@507: beach.insert(std::make_pair(Part(prev, curr, site), pit)); alpar@507: } alpar@507: alpar@507: beach.insert(std::make_pair(Part(curr, site, curr), spikeheap.end())); alpar@507: alpar@507: SpikeHeap::iterator nit = spikeheap.end(); alpar@507: if (next != -1 && alpar@507: circle_form(points[site], points[curr],points[next])) { alpar@507: double x = circle_point(points[site], points[curr], points[next]); alpar@507: nit = spikeheap.insert(std::make_pair(x, BeachIt(beach.end()))); alpar@507: nit->second.it = alpar@507: beach.insert(std::make_pair(Part(site, curr, next), nit)); alpar@507: } else { alpar@507: beach.insert(std::make_pair(Part(site, curr, next), nit)); alpar@507: } alpar@507: alpar@507: ++siteindex; alpar@507: } else { alpar@507: sweep = spit->first; alpar@507: alpar@507: Beach::iterator bit = spit->second.it; alpar@507: alpar@507: int prev = bit->first.prev; alpar@507: int curr = bit->first.curr; alpar@507: int next = bit->first.next; alpar@507: alpar@507: { alpar@507: std::pair arc; alpar@507: alpar@507: arc = prev < curr ? alpar@507: std::make_pair(prev, curr) : std::make_pair(curr, prev); alpar@507: alpar@507: if (arcs.find(arc) == arcs.end()) { alpar@507: arcs.insert(arc); alpar@507: g.addEdge(nodes[prev], nodes[curr]); alpar@507: ++cnt; alpar@507: } alpar@507: alpar@507: arc = curr < next ? alpar@507: std::make_pair(curr, next) : std::make_pair(next, curr); alpar@507: alpar@507: if (arcs.find(arc) == arcs.end()) { alpar@507: arcs.insert(arc); alpar@507: g.addEdge(nodes[curr], nodes[next]); alpar@507: ++cnt; alpar@507: } alpar@507: } alpar@507: alpar@507: Beach::iterator pbit = bit; --pbit; alpar@507: int ppv = pbit->first.prev; alpar@507: Beach::iterator nbit = bit; ++nbit; alpar@507: int nnt = nbit->first.next; alpar@507: alpar@507: if (bit->second != spikeheap.end()) spikeheap.erase(bit->second); alpar@507: if (pbit->second != spikeheap.end()) spikeheap.erase(pbit->second); alpar@507: if (nbit->second != spikeheap.end()) spikeheap.erase(nbit->second); alpar@507: alpar@507: beach.erase(nbit); alpar@507: beach.erase(bit); alpar@507: beach.erase(pbit); alpar@507: alpar@507: SpikeHeap::iterator pit = spikeheap.end(); alpar@507: if (ppv != -1 && ppv != next && alpar@507: circle_form(points[ppv], points[prev], points[next])) { alpar@507: double x = circle_point(points[ppv], points[prev], points[next]); alpar@507: if (x < sweep) x = sweep; alpar@507: pit = spikeheap.insert(std::make_pair(x, BeachIt(beach.end()))); alpar@507: pit->second.it = alpar@507: beach.insert(std::make_pair(Part(ppv, prev, next), pit)); alpar@507: } else { alpar@507: beach.insert(std::make_pair(Part(ppv, prev, next), pit)); alpar@507: } alpar@507: alpar@507: SpikeHeap::iterator nit = spikeheap.end(); alpar@507: if (nnt != -1 && prev != nnt && alpar@507: circle_form(points[prev], points[next], points[nnt])) { alpar@507: double x = circle_point(points[prev], points[next], points[nnt]); alpar@507: if (x < sweep) x = sweep; alpar@507: nit = spikeheap.insert(std::make_pair(x, BeachIt(beach.end()))); alpar@507: nit->second.it = alpar@507: beach.insert(std::make_pair(Part(prev, next, nnt), nit)); alpar@507: } else { alpar@507: beach.insert(std::make_pair(Part(prev, next, nnt), nit)); alpar@507: } alpar@507: alpar@507: } alpar@507: } alpar@507: alpar@507: for (Beach::iterator it = beach.begin(); it != beach.end(); ++it) { alpar@507: int curr = it->first.curr; alpar@507: int next = it->first.next; alpar@507: alpar@507: if (next == -1) continue; alpar@507: alpar@507: std::pair arc; alpar@507: alpar@507: arc = curr < next ? alpar@507: std::make_pair(curr, next) : std::make_pair(next, curr); alpar@507: alpar@507: if (arcs.find(arc) == arcs.end()) { alpar@507: arcs.insert(arc); alpar@507: g.addEdge(nodes[curr], nodes[next]); alpar@507: ++cnt; alpar@507: } alpar@507: } alpar@507: } alpar@507: alpar@507: void sparse(int d) alpar@507: { alpar@507: Counter cnt("Number of arcs removed: "); alpar@507: Bfs bfs(g); alpar@507: for(std::vector::reverse_iterator ei=arcs.rbegin(); alpar@507: ei!=arcs.rend();++ei) alpar@507: { alpar@507: Node a=g.u(*ei); alpar@507: Node b=g.v(*ei); alpar@507: g.erase(*ei); alpar@507: bfs.run(a,b); alpar@507: if(bfs.predArc(b)==INVALID || bfs.dist(b)>d) alpar@507: g.addEdge(a,b); alpar@507: else cnt++; alpar@507: } alpar@507: } alpar@507: alpar@507: void sparse2(int d) alpar@507: { alpar@507: Counter cnt("Number of arcs removed: "); alpar@507: for(std::vector::reverse_iterator ei=arcs.rbegin(); alpar@507: ei!=arcs.rend();++ei) alpar@507: { alpar@507: Node a=g.u(*ei); alpar@507: Node b=g.v(*ei); alpar@507: g.erase(*ei); alpar@507: ConstMap cegy(1); kpeter@615: Suurballe > sur(g,cegy); kpeter@615: int k=sur.run(a,b,2); alpar@507: if(k<2 || sur.totalLength()>d) alpar@507: g.addEdge(a,b); alpar@507: else cnt++; alpar@507: // else std::cout << "Remove arc " << g.id(a) << "-" << g.id(b) << '\n'; alpar@507: } alpar@507: } alpar@507: alpar@507: void sparseTriangle(int d) alpar@507: { alpar@507: Counter cnt("Number of arcs added: "); alpar@507: std::vector pedges; alpar@507: for(NodeIt n(g);n!=INVALID;++n) alpar@507: for(NodeIt m=++(NodeIt(n));m!=INVALID;++m) alpar@507: { alpar@507: Parc p; alpar@507: p.a=n; alpar@507: p.b=m; alpar@507: p.len=(coords[m]-coords[n]).normSquare(); alpar@507: pedges.push_back(p); alpar@507: } alpar@507: std::sort(pedges.begin(),pedges.end(),pedgeLess); alpar@507: for(std::vector::iterator pi=pedges.begin();pi!=pedges.end();++pi) alpar@507: { alpar@507: Line li(pi->a,pi->b); alpar@507: EdgeIt e(g); alpar@507: for(;e!=INVALID && !cross(e,li);++e) ; alpar@507: Edge ne; alpar@507: if(e==INVALID) { alpar@507: ConstMap cegy(1); kpeter@615: Suurballe > sur(g,cegy); kpeter@615: int k=sur.run(pi->a,pi->b,2); alpar@507: if(k<2 || sur.totalLength()>d) alpar@507: { alpar@507: ne=g.addEdge(pi->a,pi->b); alpar@507: arcs.push_back(ne); alpar@507: cnt++; alpar@507: } alpar@507: } alpar@507: } alpar@507: } alpar@507: alpar@507: template alpar@507: class LengthSquareMap { alpar@507: public: alpar@507: typedef typename Graph::Edge Key; alpar@507: typedef typename CoordMap::Value::Value Value; alpar@507: alpar@507: LengthSquareMap(const Graph& graph, const CoordMap& coords) alpar@507: : _graph(graph), _coords(coords) {} alpar@507: alpar@507: Value operator[](const Key& key) const { alpar@507: return (_coords[_graph.v(key)] - alpar@507: _coords[_graph.u(key)]).normSquare(); alpar@507: } alpar@507: alpar@507: private: alpar@507: alpar@507: const Graph& _graph; alpar@507: const CoordMap& _coords; alpar@507: }; alpar@507: alpar@507: void minTree() { alpar@507: std::vector pedges; alpar@507: Timer T; alpar@507: std::cout << T.realTime() << "s: Creating delaunay triangulation...\n"; alpar@507: delaunay(); alpar@507: std::cout << T.realTime() << "s: Calculating spanning tree...\n"; alpar@507: LengthSquareMap > ls(g, coords); alpar@507: ListGraph::EdgeMap tree(g); alpar@507: kruskal(g, ls, tree); alpar@507: std::cout << T.realTime() << "s: Removing non tree arcs...\n"; alpar@507: std::vector remove; alpar@507: for (EdgeIt e(g); e != INVALID; ++e) { alpar@507: if (!tree[e]) remove.push_back(e); alpar@507: } alpar@507: for(int i = 0; i < int(remove.size()); ++i) { alpar@507: g.erase(remove[i]); alpar@507: } alpar@507: std::cout << T.realTime() << "s: Done\n"; alpar@507: } alpar@507: alpar@507: void tsp2() alpar@507: { alpar@507: std::cout << "Find a tree..." << std::endl; alpar@507: alpar@507: minTree(); alpar@507: alpar@507: std::cout << "Total arc length (tree) : " << totalLen() << std::endl; alpar@507: alpar@507: std::cout << "Make it Euler..." << std::endl; alpar@507: alpar@507: { alpar@507: std::vector leafs; alpar@507: for(NodeIt n(g);n!=INVALID;++n) alpar@507: if(countIncEdges(g,n)%2==1) leafs.push_back(n); alpar@507: alpar@507: // for(unsigned int i=0;i pedges; alpar@507: for(unsigned int i=0;i enext(g); alpar@507: { alpar@507: EulerIt e(g); alpar@507: Arc eo=e; alpar@507: Arc ef=e; alpar@507: // std::cout << "Tour arc: " << g.id(Edge(e)) << std::endl; alpar@507: for(++e;e!=INVALID;++e) alpar@507: { alpar@507: // std::cout << "Tour arc: " << g.id(Edge(e)) << std::endl; alpar@507: enext[eo]=e; alpar@507: eo=e; alpar@507: } alpar@507: enext[eo]=ef; alpar@507: } alpar@507: alpar@507: std::cout << "Creating a tour from that..." << std::endl; alpar@507: alpar@507: int nnum = countNodes(g); alpar@507: int ednum = countEdges(g); alpar@507: alpar@507: for(Arc p=enext[EdgeIt(g)];ednum>nnum;p=enext[p]) alpar@507: { alpar@507: // std::cout << "Checking arc " << g.id(p) << std::endl; alpar@507: Arc e=enext[p]; alpar@507: Arc f=enext[e]; alpar@507: Node n2=g.source(f); alpar@507: Node n1=g.oppositeNode(n2,e); alpar@507: Node n3=g.oppositeNode(n2,f); alpar@507: if(countIncEdges(g,n2)>2) alpar@507: { alpar@507: // std::cout << "Remove an Arc" << std::endl; alpar@507: Arc ff=enext[f]; alpar@507: g.erase(e); alpar@507: g.erase(f); alpar@507: if(n1!=n3) alpar@507: { alpar@507: Arc ne=g.direct(g.addEdge(n1,n3),n1); alpar@507: enext[p]=ne; alpar@507: enext[ne]=ff; alpar@507: ednum--; alpar@507: } alpar@507: else { alpar@507: enext[p]=ff; alpar@507: ednum-=2; alpar@507: } alpar@507: } alpar@507: } alpar@507: alpar@507: std::cout << "Total arc length (tour) : " << totalLen() << std::endl; alpar@507: alpar@507: std::cout << "2-opt the tour..." << std::endl; alpar@507: alpar@507: tsp_improve(); alpar@507: alpar@507: std::cout << "Total arc length (2-opt tour) : " << totalLen() << std::endl; alpar@507: } alpar@507: alpar@507: alpar@507: int main(int argc,const char **argv) alpar@507: { alpar@507: ArgParser ap(argc,argv); alpar@507: alpar@507: // bool eps; alpar@507: bool disc_d, square_d, gauss_d; alpar@507: // bool tsp_a,two_a,tree_a; alpar@507: int num_of_cities=1; alpar@507: double area=1; alpar@507: N=100; alpar@507: // girth=10; alpar@507: std::string ndist("disc"); alpar@507: ap.refOption("n", "Number of nodes (default is 100)", N) alpar@507: .intOption("g", "Girth parameter (default is 10)", 10) alpar@507: .refOption("cities", "Number of cities (default is 1)", num_of_cities) alpar@507: .refOption("area", "Full relative area of the cities (default is 1)", area) alpar@507: .refOption("disc", "Nodes are evenly distributed on a unit disc (default)",disc_d) alpar@507: .optionGroup("dist", "disc") alpar@507: .refOption("square", "Nodes are evenly distributed on a unit square", square_d) alpar@507: .optionGroup("dist", "square") alpar@507: .refOption("gauss", alpar@507: "Nodes are located according to a two-dim gauss distribution", alpar@507: gauss_d) alpar@507: .optionGroup("dist", "gauss") alpar@507: // .mandatoryGroup("dist") alpar@507: .onlyOneGroup("dist") alpar@507: .boolOption("eps", "Also generate .eps output (prefix.eps)") alpar@508: .boolOption("nonodes", "Draw the edges only in the generated .eps") alpar@507: .boolOption("dir", "Directed digraph is generated (each arcs are replaced by two directed ones)") alpar@507: .boolOption("2con", "Create a two connected planar digraph") alpar@507: .optionGroup("alg","2con") alpar@507: .boolOption("tree", "Create a min. cost spanning tree") alpar@507: .optionGroup("alg","tree") alpar@507: .boolOption("tsp", "Create a TSP tour") alpar@507: .optionGroup("alg","tsp") alpar@507: .boolOption("tsp2", "Create a TSP tour (tree based)") alpar@507: .optionGroup("alg","tsp2") alpar@507: .boolOption("dela", "Delaunay triangulation digraph") alpar@507: .optionGroup("alg","dela") alpar@507: .onlyOneGroup("alg") alpar@507: .boolOption("rand", "Use time seed for random number generator") alpar@507: .optionGroup("rand", "rand") alpar@507: .intOption("seed", "Random seed", -1) alpar@507: .optionGroup("rand", "seed") alpar@507: .onlyOneGroup("rand") alpar@507: .other("[prefix]","Prefix of the output files. Default is 'lgf-gen-out'") alpar@507: .run(); alpar@507: alpar@507: if (ap["rand"]) { kpeter@608: int seed = int(time(0)); alpar@507: std::cout << "Random number seed: " << seed << std::endl; alpar@507: rnd = Random(seed); alpar@507: } alpar@507: if (ap.given("seed")) { alpar@507: int seed = ap["seed"]; alpar@507: std::cout << "Random number seed: " << seed << std::endl; alpar@507: rnd = Random(seed); alpar@507: } alpar@507: alpar@507: std::string prefix; alpar@507: switch(ap.files().size()) alpar@507: { alpar@507: case 0: alpar@507: prefix="lgf-gen-out"; alpar@507: break; alpar@507: case 1: alpar@507: prefix=ap.files()[0]; alpar@507: break; alpar@507: default: alpar@507: std::cerr << "\nAt most one prefix can be given\n\n"; alpar@507: exit(1); alpar@507: } alpar@507: alpar@507: double sum_sizes=0; alpar@507: std::vector sizes; alpar@507: std::vector cum_sizes; alpar@507: for(int s=0;s(g,prefix+".lgf"). alpar@507: nodeMap("coordinates_x",scaleMap(xMap(coords),600)). alpar@507: nodeMap("coordinates_y",scaleMap(yMap(coords),600)). alpar@507: run(); alpar@507: else GraphWriter(g,prefix+".lgf"). alpar@507: nodeMap("coordinates_x",scaleMap(xMap(coords),600)). alpar@507: nodeMap("coordinates_y",scaleMap(yMap(coords),600)). alpar@507: run(); alpar@507: } alpar@507: