1.1 --- a/tools/lgf-gen.cc Tue Jun 05 10:57:26 2007 +0000
1.2 +++ b/tools/lgf-gen.cc Tue Jun 05 10:59:16 2007 +0000
1.3 @@ -26,6 +26,7 @@
1.4 #include <lemon/graph_to_eps.h>
1.5 #include <lemon/graph_writer.h>
1.6 #include <lemon/arg_parser.h>
1.7 +#include <lemon/euler.h>
1.8 #include <cmath>
1.9 #include <algorithm>
1.10 #include <lemon/unionfind.h>
1.11 @@ -47,6 +48,14 @@
1.12 std::vector<Node> nodes;
1.13 ListUGraph::NodeMap<Point> coords(g);
1.14
1.15 +
1.16 +double totalLen(){
1.17 + double tlen=0;
1.18 + for(UEdgeIt e(g);e!=INVALID;++e)
1.19 + tlen+=sqrt((coords[g.source(e)]-coords[g.target(e)]).normSquare());
1.20 + return tlen;
1.21 +}
1.22 +
1.23 int tsp_impr_num=0;
1.24
1.25 const double EPSILON=1e-8;
1.26 @@ -252,7 +261,6 @@
1.27 p.len=(coords[m]-coords[n]).normSquare();
1.28 pedges.push_back(p);
1.29 }
1.30 - en++;
1.31 if(progress && en>=pr*double(N)/100)
1.32 {
1.33 std::cout << pr << "% \r" << std::flush;
1.34 @@ -270,6 +278,7 @@
1.35 {
1.36 if ( uf.join(pi->a,pi->b) ) {
1.37 g.addEdge(pi->a,pi->b);
1.38 + en++;
1.39 if(en>=N-1)
1.40 break;
1.41 }
1.42 @@ -277,6 +286,90 @@
1.43 std::cout << T.realTime() << "s: Done\n";
1.44 }
1.45
1.46 +Node common(UEdge e, UEdge f)
1.47 +{
1.48 + return (g.source(e)==g.source(f)||g.source(e)==g.target(f))?
1.49 + g.source(e):g.target(e);
1.50 +}
1.51 +
1.52 +void tsp2()
1.53 +{
1.54 + std::cout << "Find a tree..." << std::endl;
1.55 +
1.56 + minTree();
1.57 +
1.58 + std::cout << "Total edge length (tree) : " << totalLen() << std::endl;
1.59 +
1.60 + std::cout << "Make it Euler..." << std::endl;
1.61 +
1.62 + {
1.63 + std::vector<Node> leafs;
1.64 + for(NodeIt n(g);n!=INVALID;++n)
1.65 + if(countIncEdges(g,n)%2==1) leafs.push_back(n);
1.66 + for(unsigned int i=0;i<leafs.size();i+=2)
1.67 + g.addEdge(leafs[i],leafs[i+1]);
1.68 + }
1.69 +
1.70 + for(NodeIt n(g);n!=INVALID;++n)
1.71 + if(countIncEdges(g,n)%2)
1.72 + std::cout << "GEBASZ!!!" << std::endl;
1.73 +
1.74 + std::cout << "Number of edges : " << countUEdges(g) << std::endl;
1.75 +
1.76 +// for(NodeIt n(g);n!=INVALID;++n)
1.77 +// if(countIncEdges(g,n)>2)
1.78 +// std::cout << "+";
1.79 +// std::cout << std::endl;
1.80 +
1.81 + std::cout << "Total edge length (euler) : " << totalLen() << std::endl;
1.82 +
1.83 + ListUGraph::UEdgeMap<UEdge> enext(g);
1.84 + {
1.85 + UEulerIt<ListUGraph> e(g);
1.86 + UEdge eo=e;
1.87 + UEdge ef=e;
1.88 +// std::cout << "Tour edge: " << g.id(UEdge(e)) << std::endl;
1.89 + for(++e;e!=INVALID;++e)
1.90 + {
1.91 +// std::cout << "Tour edge: " << g.id(UEdge(e)) << std::endl;
1.92 + enext[eo]=e;
1.93 + eo=e;
1.94 + }
1.95 + enext[eo]=ef;
1.96 + }
1.97 +
1.98 + std::cout << "Creating a tour from that..." << std::endl;
1.99 +
1.100 + int nnum = countNodes(g);
1.101 + int ednum = countUEdges(g);
1.102 +
1.103 + for(UEdge p=UEdgeIt(g);ednum>nnum;p=enext[p])
1.104 + {
1.105 +// std::cout << "Checking edge " << g.id(p) << std::endl;
1.106 + UEdge e=enext[p];
1.107 + UEdge f=enext[e];
1.108 + Node n2=common(e,f);
1.109 + Node n1=g.oppositeNode(n2,e);
1.110 + Node n3=g.oppositeNode(n2,f);
1.111 + if(countIncEdges(g,n2)>2)
1.112 + {
1.113 +// std::cout << "Remove an Edge" << std::endl;
1.114 + UEdge ff=enext[f];
1.115 + g.erase(e);
1.116 + g.erase(f);
1.117 + UEdge ne=g.addEdge(n1,n3);
1.118 + enext[p]=ne;
1.119 + enext[ne]=ff;
1.120 + ednum--;
1.121 + }
1.122 + }
1.123 +
1.124 + std::cout << "Total edge length (tour) : " << totalLen() << std::endl;
1.125 +
1.126 + tsp_improve();
1.127 +
1.128 + std::cout << "Total edge length (2-opt tour) : " << totalLen() << std::endl;
1.129 +}
1.130
1.131
1.132 int main(int argc,const char **argv)
1.133 @@ -306,12 +399,15 @@
1.134 // .mandatoryGroup("dist")
1.135 .onlyOneGroup("dist")
1.136 .boolOption("eps", "Also generate .eps output (prefix.eps)")
1.137 + .boolOption("dir", "Directed graph is generated (each edges are replaced by two directed ones)")
1.138 .boolOption("2con", "Create a two connected planar graph")
1.139 .optionGroup("alg","2con")
1.140 .boolOption("tree", "Create a min. cost spanning tree")
1.141 .optionGroup("alg","tree")
1.142 .boolOption("tsp", "Create a TSP tour")
1.143 .optionGroup("alg","tsp")
1.144 + .boolOption("tsp2", "Create a TSP tour (tree based)")
1.145 + .optionGroup("alg","tsp2")
1.146 .onlyOneGroup("alg")
1.147 .other("[prefix]","Prefix of the output files. Default is 'lgf-gen-out'")
1.148 .run();
1.149 @@ -372,6 +468,10 @@
1.150 tsp();
1.151 std::cout << "#2-opt improvements: " << tsp_impr_num << std::endl;
1.152 }
1.153 + if(ap["tsp2"]) {
1.154 + tsp2();
1.155 + std::cout << "#2-opt improvements: " << tsp_impr_num << std::endl;
1.156 + }
1.157 else if(ap["2con"]) {
1.158 std::cout << "Make triangles\n";
1.159 // triangle();
1.160 @@ -395,9 +495,14 @@
1.161 scale(600).nodeScale(.2).edgeWidthScale(.001).preScale(false).
1.162 coords(coords).run();
1.163
1.164 - UGraphWriter<ListUGraph>(prefix+".lgf",g).
1.165 - writeNodeMap("coordinates_x",scaleMap(xMap(coords),600)).
1.166 - writeNodeMap("coordinates_y",scaleMap(yMap(coords),600)).
1.167 - run();
1.168 + if(ap["dir"])
1.169 + GraphWriter<ListUGraph>(prefix+".lgf",g).
1.170 + writeNodeMap("coordinates_x",scaleMap(xMap(coords),600)).
1.171 + writeNodeMap("coordinates_y",scaleMap(yMap(coords),600)).
1.172 + run();
1.173 + else UGraphWriter<ListUGraph>(prefix+".lgf",g).
1.174 + writeNodeMap("coordinates_x",scaleMap(xMap(coords),600)).
1.175 + writeNodeMap("coordinates_y",scaleMap(yMap(coords),600)).
1.176 + run();
1.177 }
1.178