Index: tools/lgf-gen.cc
===================================================================
--- tools/lgf-gen.cc	(revision 2410)
+++ tools/lgf-gen.cc	(revision 2446)
@@ -27,4 +27,5 @@
 #include <lemon/graph_writer.h>
 #include <lemon/arg_parser.h>
+#include <lemon/euler.h>
 #include <cmath>
 #include <algorithm>
@@ -47,4 +48,12 @@
 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;
@@ -253,5 +262,4 @@
 	  pedges.push_back(p);
 	}
-      en++;
       if(progress && en>=pr*double(N)/100) 
 	{
@@ -271,4 +279,5 @@
       if ( uf.join(pi->a,pi->b) ) {
 	g.addEdge(pi->a,pi->b);
+	en++;
 	if(en>=N-1)
 	  break;
@@ -278,4 +287,88 @@
 }
 
+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;
+}
 
 
@@ -307,4 +400,5 @@
     .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")
@@ -313,4 +407,6 @@
     .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'")
@@ -373,4 +469,8 @@
     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";
@@ -396,8 +496,13 @@
       coords(coords).run();
 
-  UGraphWriter<ListUGraph>(prefix+".lgf",g).
-    writeNodeMap("coordinates_x",scaleMap(xMap(coords),600)).
-    writeNodeMap("coordinates_y",scaleMap(yMap(coords),600)).
-    run();
-}
-
+  if(ap["dir"])
+    GraphWriter<ListUGraph>(prefix+".lgf",g).
+      writeNodeMap("coordinates_x",scaleMap(xMap(coords),600)).
+      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();
+}
+
