Changeset 2446:dd20d76eed13 in lemon-0.x for tools

Timestamp:

06/05/07 12:59:16 (17 years ago)

Author:

Alpar Juttner

Branch:

default

Phase:

public

Convert:

svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@3283

Message:

A minimum spanning tree based TSP algorithm is added (-tsp2)

File:

• tools/lgf-gen.cc (modified) (9 diffs)

tools/lgf-gen.cc

@@ -27 +27 @@
 #include <lemon/graph_writer.h>
 #include <lemon/arg_parser.h>
+#include <lemon/euler.h>
 #include <cmath>
 #include <algorithm>
@@ -47 +48 @@
 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 +262 @@
           pedges.push_back(p);
         }
-      en++;
       if(progress && en>=pr*double(N)/100) 
         {
@@ -271 +279 @@
       if ( uf.join(pi->a,pi->b) ) {
         g.addEdge(pi->a,pi->b);
+        en++;
         if(en>=N-1)
           break;
@@ -278 +287 @@
 }
 
+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 +400 @@
     .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 +407 @@
     .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 +469 @@
     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 +496 @@
       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();
+}
+