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