Changeset 2448:ab899ae3505f in lemon-0.x for tools/lgf-gen.cc

Timestamp:

06/05/07 16:48:20 (17 years ago)

Author:

Alpar Juttner

Branch:

default

Phase:

public

Convert:

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

Message:

Bugfix and improvement in -tsp2 algorithm

File:

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

tools/lgf-gen.cc

@@ -533 +533 @@
 }
 
-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() 
 {
@@ -553 +547 @@
     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(unsigned int i=0;i<leafs.size();i+=2)
+//       g.addEdge(leafs[i],leafs[i+1]);
+
+    std::vector<Pedge> pedges;
+    for(unsigned int i=0;i<leafs.size()-1;i++)
+      for(unsigned int j=i+1;j<leafs.size();j++)
+        {
+          Node n=leafs[i];
+          Node m=leafs[j];
+          Pedge p;
+          p.a=n;
+          p.b=m;
+          p.len=(coords[m]-coords[n]).normSquare();
+          pedges.push_back(p);
+        }
+    std::sort(pedges.begin(),pedges.end(),pedgeLess);
+    for(unsigned int i=0;i<pedges.size();i++)
+      if(countIncEdges(g,pedges[i].a)%2 &&
+         countIncEdges(g,pedges[i].b)%2)
+        g.addEdge(pedges[i].a,pedges[i].b);
   }
 
   for(NodeIt n(g);n!=INVALID;++n)
-    if(countIncEdges(g,n)%2)
+    if(countIncEdges(g,n)%2 || countIncEdges(g,n)==0 )
       std::cout << "GEBASZ!!!" << std::endl;
   
+  for(UEdgeIt e(g);e!=INVALID;++e)
+    if(g.source(e)==g.target(e))
+      std::cout << "LOOP 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);
+  ListUGraph::UEdgeMap<Edge> enext(g);
   {
     UEulerIt<ListUGraph> e(g);
-    UEdge eo=e;
-    UEdge ef=e;
+    Edge eo=e;
+    Edge ef=e;
 //     std::cout << "Tour edge: " << g.id(UEdge(e)) << std::endl;      
     for(++e;e!=INVALID;++e)
@@ -584 +596 @@
     enext[eo]=ef;
   }
-  
+    
   std::cout << "Creating a tour from that..." << std::endl;
   
@@ -590 +602 @@
   int ednum = countUEdges(g);
   
-  for(UEdge p=UEdgeIt(g);ednum>nnum;p=enext[p]) 
+  for(Edge p=enext[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);
+      Edge e=enext[p];
+      Edge f=enext[e];
+      Node n2=g.source(f);
       Node n1=g.oppositeNode(n2,e);
       Node n3=g.oppositeNode(n2,f);
@@ -601 +613 @@
         {
 //        std::cout << "Remove an Edge" << std::endl;
-          UEdge ff=enext[f];
+          Edge ff=enext[f];
           g.erase(e);
           g.erase(f);
-          UEdge ne=g.addEdge(n1,n3);
-          enext[p]=ne;
-          enext[ne]=ff;
-          ednum--;
+          if(n1!=n3)
+            {
+              Edge ne=g.direct(g.addEdge(n1,n3),n1);
+              enext[p]=ne;
+              enext[ne]=ff;
+              ednum--;
+            }
+          else {
+            enext[p]=ff;
+            ednum-=2;
+          }
         }
     }
@@ -613 +632 @@
   std::cout << "Total edge length (tour) : " << totalLen() << std::endl;
 
+  std::cout << "2-opt the tour..." << std::endl;
+  
   tsp_improve();
   
@@ -762 +783 @@
     tlen+=sqrt((coords[g.source(e)]-coords[g.target(e)]).normSquare());
   std::cout << "Total edge length  : " << tlen << std::endl;
+
   if(ap["eps"])
     graphToEps(g,prefix+".eps").
       scale(600).nodeScale(.2).edgeWidthScale(.001).preScale(false).
       coords(coords).run();
-
+  
   if(ap["dir"])
     GraphWriter<ListUGraph>(prefix+".lgf",g).