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