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