lemon-0.x: comparison tools/lgf-gen.cc

equal deleted inserted replaced

-:f93af1984178
+:016b8500e6ea
 #include <lemon/counter.h>
 #include <lemon/suurballe.h>
 #include <lemon/graph_to_eps.h>
 #include <lemon/graph_writer.h>
 #include <lemon/arg_parser.h>
+#include <lemon/euler.h>
 #include <cmath>
 #include <algorithm>
 #include <lemon/unionfind.h>
 #include <lemon/time_measure.h>
 ListUGraph g;
 std::vector<Node> nodes;
 ListUGraph::NodeMap<Point> coords(g);
+double totalLen(){
+double tlen=0;
+for(UEdgeIt e(g);e!=INVALID;++e)
+tlen+=sqrt((coords[g.source(e)]-coords[g.target(e)]).normSquare());
+return tlen;
+}
 int tsp_impr_num=0;
 const double EPSILON=1e-8;
 bool tsp_improve(Node u, Node v)
 	  p.a=n;
 	  p.b=m;
 	  p.len=(coords[m]-coords[n]).normSquare();
 	  pedges.push_back(p);
 	}
-en++;
 if(progress && en>=pr*double(N)/100)
 	{
 	  std::cout << pr << "%  \r" << std::flush;
 	  pr++;
 	}
 uf.insert(it);
 for(std::vector<Pedge>::iterator pi=pedges.begin();pi!=pedges.end();++pi)
 {
 if ( uf.join(pi->a,pi->b) ) {
 	g.addEdge(pi->a,pi->b);
+	en++;
 	if(en>=N-1)
 	  break;
 }
 }
 std::cout << T.realTime() << "s: Done\n";
 }
+Node common(UEdge e, UEdge f)
+{
+return (g.source(e)==g.source(f)||g.source(e)==g.target(f))?
+	g.source(e):g.target(e);
+}
+void tsp2()
+{
+std::cout << "Find a tree..." << std::endl;
+minTree();
+std::cout << "Total edge length (tree) : " << totalLen() << std::endl;
+std::cout << "Make it Euler..." << std::endl;
+{
+std::vector<Node> leafs;
+for(NodeIt n(g);n!=INVALID;++n)
+if(countIncEdges(g,n)%2==1) leafs.push_back(n);
+for(unsigned int i=0;i<leafs.size();i+=2)
+g.addEdge(leafs[i],leafs[i+1]);
+}
+for(NodeIt n(g);n!=INVALID;++n)
+if(countIncEdges(g,n)%2)
+std::cout << "GEBASZ!!!" << std::endl;
+std::cout << "Number of edges : " << countUEdges(g) << std::endl;
+//   for(NodeIt n(g);n!=INVALID;++n)
+//     if(countIncEdges(g,n)>2)
+//       std::cout << "+";
+//   std::cout << std::endl;
+std::cout << "Total edge length (euler) : " << totalLen() << std::endl;
+ListUGraph::UEdgeMap<UEdge> enext(g);
+{
+UEulerIt<ListUGraph> e(g);
+UEdge eo=e;
+UEdge ef=e;
+//     std::cout << "Tour edge: " << g.id(UEdge(e)) << std::endl;
+for(++e;e!=INVALID;++e)
+{
+// 	std::cout << "Tour edge: " << g.id(UEdge(e)) << std::endl;
+	enext[eo]=e;
+	eo=e;
+}
+enext[eo]=ef;
+}
+std::cout << "Creating a tour from that..." << std::endl;
+int nnum = countNodes(g);
+int ednum = countUEdges(g);
+for(UEdge p=UEdgeIt(g);ednum>nnum;p=enext[p])
+{
+//       std::cout << "Checking edge " << g.id(p) << std::endl;
+UEdge e=enext[p];
+UEdge f=enext[e];
+Node n2=common(e,f);
+Node n1=g.oppositeNode(n2,e);
+Node n3=g.oppositeNode(n2,f);
+if(countIncEdges(g,n2)>2)
+	{
+// 	  std::cout << "Remove an Edge" << std::endl;
+	  UEdge ff=enext[f];
+	  g.erase(e);
+	  g.erase(f);
+	  UEdge ne=g.addEdge(n1,n3);
+	  enext[p]=ne;
+	  enext[ne]=ff;
+	  ednum--;
+	}
+}
+std::cout << "Total edge length (tour) : " << totalLen() << std::endl;
+tsp_improve();
+std::cout << "Total edge length (2-opt tour) : " << totalLen() << std::endl;
+}
 int main(int argc,const char **argv)
 {
 ArgParser ap(argc,argv);
 	    gauss_d)
 .optionGroup("dist", "gauss")
 //     .mandatoryGroup("dist")
 .onlyOneGroup("dist")
 .boolOption("eps", "Also generate .eps output (prefix.eps)")
+.boolOption("dir", "Directed graph is generated (each edges are replaced by two directed ones)")
 .boolOption("2con", "Create a two connected planar graph")
 .optionGroup("alg","2con")
 .boolOption("tree", "Create a min. cost spanning tree")
 .optionGroup("alg","tree")
 .boolOption("tsp", "Create a TSP tour")
 .optionGroup("alg","tsp")
+.boolOption("tsp2", "Create a TSP tour (tree based)")
+.optionGroup("alg","tsp2")
 .onlyOneGroup("alg")
 .other("[prefix]","Prefix of the output files. Default is 'lgf-gen-out'")
 .run();
 std::string prefix;
 if(ap["tsp"]) {
 tsp();
 std::cout << "#2-opt improvements: " << tsp_impr_num << std::endl;
 }
+if(ap["tsp2"]) {
+tsp2();
+std::cout << "#2-opt improvements: " << tsp_impr_num << std::endl;
+}
 else if(ap["2con"]) {
 std::cout << "Make triangles\n";
 //   triangle();
 sparseTriangle(ap["g"]);
 std::cout << "Make it sparser\n";
 if(ap["eps"])
 graphToEps(g,prefix+".eps").
 scale(600).nodeScale(.2).edgeWidthScale(.001).preScale(false).
 coords(coords).run();
-UGraphWriter<ListUGraph>(prefix+".lgf",g).
+if(ap["dir"])
-writeNodeMap("coordinates_x",scaleMap(xMap(coords),600)).
+GraphWriter<ListUGraph>(prefix+".lgf",g).
-writeNodeMap("coordinates_y",scaleMap(yMap(coords),600)).
+writeNodeMap("coordinates_x",scaleMap(xMap(coords),600)).
-run();
+writeNodeMap("coordinates_y",scaleMap(yMap(coords),600)).
-}
+run();
+else UGraphWriter<ListUGraph>(prefix+".lgf",g).
+	 writeNodeMap("coordinates_x",scaleMap(xMap(coords),600)).
+	 writeNodeMap("coordinates_y",scaleMap(yMap(coords),600)).
+	 run();
+}

changeset 2446	dd20d76eed13
parent 2410	fe46b61da4e3
child 2447	260ce674cc65