1.1 --- a/tools/lgf-gen.cc	Tue Jun 05 11:49:19 2007 +0000
     1.2 +++ b/tools/lgf-gen.cc	Tue Jun 05 14:48:20 2007 +0000
     1.3 @@ -532,12 +532,6 @@
     1.4    std::cout << T.realTime() << "s: Done\n";
     1.5  }
     1.6  
     1.7 -Node common(UEdge e, UEdge f)
     1.8 -{
     1.9 -  return (g.source(e)==g.source(f)||g.source(e)==g.target(f))?
    1.10 -	g.source(e):g.target(e);
    1.11 -}
    1.12 -
    1.13  void tsp2() 
    1.14  {
    1.15    std::cout << "Find a tree..." << std::endl;
    1.16 @@ -552,28 +546,46 @@
    1.17      std::vector<Node> leafs;
    1.18      for(NodeIt n(g);n!=INVALID;++n)
    1.19        if(countIncEdges(g,n)%2==1) leafs.push_back(n);
    1.20 -    for(unsigned int i=0;i<leafs.size();i+=2)
    1.21 -      g.addEdge(leafs[i],leafs[i+1]);
    1.22 +
    1.23 +//    for(unsigned int i=0;i<leafs.size();i+=2)
    1.24 +//       g.addEdge(leafs[i],leafs[i+1]);
    1.25 +
    1.26 +    std::vector<Pedge> pedges;
    1.27 +    for(unsigned int i=0;i<leafs.size()-1;i++)
    1.28 +      for(unsigned int j=i+1;j<leafs.size();j++)
    1.29 +	{
    1.30 +	  Node n=leafs[i];
    1.31 +	  Node m=leafs[j];
    1.32 +	  Pedge p;
    1.33 +	  p.a=n;
    1.34 +	  p.b=m;
    1.35 +	  p.len=(coords[m]-coords[n]).normSquare();
    1.36 +	  pedges.push_back(p);
    1.37 +	}
    1.38 +    std::sort(pedges.begin(),pedges.end(),pedgeLess);
    1.39 +    for(unsigned int i=0;i<pedges.size();i++)
    1.40 +      if(countIncEdges(g,pedges[i].a)%2 &&
    1.41 +	 countIncEdges(g,pedges[i].b)%2)
    1.42 +	g.addEdge(pedges[i].a,pedges[i].b);
    1.43    }
    1.44  
    1.45    for(NodeIt n(g);n!=INVALID;++n)
    1.46 -    if(countIncEdges(g,n)%2)
    1.47 +    if(countIncEdges(g,n)%2 || countIncEdges(g,n)==0 )
    1.48        std::cout << "GEBASZ!!!" << std::endl;
    1.49    
    1.50 +  for(UEdgeIt e(g);e!=INVALID;++e)
    1.51 +    if(g.source(e)==g.target(e))
    1.52 +      std::cout << "LOOP GEBASZ!!!" << std::endl;
    1.53 +  
    1.54    std::cout << "Number of edges : " << countUEdges(g) << std::endl;
    1.55 -
    1.56 -//   for(NodeIt n(g);n!=INVALID;++n)
    1.57 -//     if(countIncEdges(g,n)>2)
    1.58 -//       std::cout << "+";
    1.59 -//   std::cout << std::endl;
    1.60    
    1.61    std::cout << "Total edge length (euler) : " << totalLen() << std::endl;
    1.62  
    1.63 -  ListUGraph::UEdgeMap<UEdge> enext(g);
    1.64 +  ListUGraph::UEdgeMap<Edge> enext(g);
    1.65    {
    1.66      UEulerIt<ListUGraph> e(g);
    1.67 -    UEdge eo=e;
    1.68 -    UEdge ef=e;
    1.69 +    Edge eo=e;
    1.70 +    Edge ef=e;
    1.71  //     std::cout << "Tour edge: " << g.id(UEdge(e)) << std::endl;      
    1.72      for(++e;e!=INVALID;++e)
    1.73        {
    1.74 @@ -583,35 +595,44 @@
    1.75        }
    1.76      enext[eo]=ef;
    1.77    }
    1.78 -  
    1.79 +    
    1.80    std::cout << "Creating a tour from that..." << std::endl;
    1.81    
    1.82    int nnum = countNodes(g);
    1.83    int ednum = countUEdges(g);
    1.84    
    1.85 -  for(UEdge p=UEdgeIt(g);ednum>nnum;p=enext[p]) 
    1.86 +  for(Edge p=enext[UEdgeIt(g)];ednum>nnum;p=enext[p]) 
    1.87      {
    1.88  //       std::cout << "Checking edge " << g.id(p) << std::endl;      
    1.89 -      UEdge e=enext[p];
    1.90 -      UEdge f=enext[e];
    1.91 -      Node n2=common(e,f);
    1.92 +      Edge e=enext[p];
    1.93 +      Edge f=enext[e];
    1.94 +      Node n2=g.source(f);
    1.95        Node n1=g.oppositeNode(n2,e);
    1.96        Node n3=g.oppositeNode(n2,f);
    1.97        if(countIncEdges(g,n2)>2)
    1.98  	{
    1.99  // 	  std::cout << "Remove an Edge" << std::endl;
   1.100 -	  UEdge ff=enext[f];
   1.101 +	  Edge ff=enext[f];
   1.102  	  g.erase(e);
   1.103  	  g.erase(f);
   1.104 -	  UEdge ne=g.addEdge(n1,n3);
   1.105 -	  enext[p]=ne;
   1.106 -	  enext[ne]=ff;
   1.107 -	  ednum--;
   1.108 +	  if(n1!=n3)
   1.109 +	    {
   1.110 +	      Edge ne=g.direct(g.addEdge(n1,n3),n1);
   1.111 +	      enext[p]=ne;
   1.112 +	      enext[ne]=ff;
   1.113 +	      ednum--;
   1.114 +	    }
   1.115 +	  else {
   1.116 +	    enext[p]=ff;
   1.117 +	    ednum-=2;
   1.118 +	  }
   1.119  	}
   1.120      }
   1.121  
   1.122    std::cout << "Total edge length (tour) : " << totalLen() << std::endl;
   1.123  
   1.124 +  std::cout << "2-opt the tour..." << 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 @@ -761,11 +782,12 @@
   1.130    for(UEdgeIt e(g);e!=INVALID;++e)
   1.131      tlen+=sqrt((coords[g.source(e)]-coords[g.target(e)]).normSquare());
   1.132    std::cout << "Total edge length  : " << tlen << std::endl;
   1.133 +
   1.134    if(ap["eps"])
   1.135      graphToEps(g,prefix+".eps").
   1.136        scale(600).nodeScale(.2).edgeWidthScale(.001).preScale(false).
   1.137        coords(coords).run();
   1.138 -
   1.139 +  
   1.140    if(ap["dir"])
   1.141      GraphWriter<ListUGraph>(prefix+".lgf",g).
   1.142        writeNodeMap("coordinates_x",scaleMap(xMap(coords),600)).