COIN-OR::LEMON - Graph Library

Changeset 2446:dd20d76eed13 in lemon-0.x


Ignore:
Timestamp:
06/05/07 12:59:16 (13 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:
1 edited

Legend:

Unmodified
Added
Removed
  • tools/lgf-gen.cc

    r2410 r2446  
    2727#include <lemon/graph_writer.h>
    2828#include <lemon/arg_parser.h>
     29#include <lemon/euler.h>
    2930#include <cmath>
    3031#include <algorithm>
     
    4748std::vector<Node> nodes;
    4849ListUGraph::NodeMap<Point> coords(g);
     50
     51
     52double totalLen(){
     53  double tlen=0;
     54  for(UEdgeIt e(g);e!=INVALID;++e)
     55    tlen+=sqrt((coords[g.source(e)]-coords[g.target(e)]).normSquare());
     56  return tlen;
     57}
    4958
    5059int tsp_impr_num=0;
     
    253262          pedges.push_back(p);
    254263        }
    255       en++;
    256264      if(progress && en>=pr*double(N)/100)
    257265        {
     
    271279      if ( uf.join(pi->a,pi->b) ) {
    272280        g.addEdge(pi->a,pi->b);
     281        en++;
    273282        if(en>=N-1)
    274283          break;
     
    278287}
    279288
     289Node common(UEdge e, UEdge f)
     290{
     291  return (g.source(e)==g.source(f)||g.source(e)==g.target(f))?
     292        g.source(e):g.target(e);
     293}
     294
     295void tsp2()
     296{
     297  std::cout << "Find a tree..." << std::endl;
     298
     299  minTree();
     300
     301  std::cout << "Total edge length (tree) : " << totalLen() << std::endl;
     302
     303  std::cout << "Make it Euler..." << std::endl;
     304
     305  {
     306    std::vector<Node> leafs;
     307    for(NodeIt n(g);n!=INVALID;++n)
     308      if(countIncEdges(g,n)%2==1) leafs.push_back(n);
     309    for(unsigned int i=0;i<leafs.size();i+=2)
     310      g.addEdge(leafs[i],leafs[i+1]);
     311  }
     312
     313  for(NodeIt n(g);n!=INVALID;++n)
     314    if(countIncEdges(g,n)%2)
     315      std::cout << "GEBASZ!!!" << std::endl;
     316 
     317  std::cout << "Number of edges : " << countUEdges(g) << std::endl;
     318
     319//   for(NodeIt n(g);n!=INVALID;++n)
     320//     if(countIncEdges(g,n)>2)
     321//       std::cout << "+";
     322//   std::cout << std::endl;
     323 
     324  std::cout << "Total edge length (euler) : " << totalLen() << std::endl;
     325
     326  ListUGraph::UEdgeMap<UEdge> enext(g);
     327  {
     328    UEulerIt<ListUGraph> e(g);
     329    UEdge eo=e;
     330    UEdge ef=e;
     331//     std::cout << "Tour edge: " << g.id(UEdge(e)) << std::endl;     
     332    for(++e;e!=INVALID;++e)
     333      {
     334//      std::cout << "Tour edge: " << g.id(UEdge(e)) << std::endl;     
     335        enext[eo]=e;
     336        eo=e;
     337      }
     338    enext[eo]=ef;
     339  }
     340 
     341  std::cout << "Creating a tour from that..." << std::endl;
     342 
     343  int nnum = countNodes(g);
     344  int ednum = countUEdges(g);
     345 
     346  for(UEdge p=UEdgeIt(g);ednum>nnum;p=enext[p])
     347    {
     348//       std::cout << "Checking edge " << g.id(p) << std::endl;     
     349      UEdge e=enext[p];
     350      UEdge f=enext[e];
     351      Node n2=common(e,f);
     352      Node n1=g.oppositeNode(n2,e);
     353      Node n3=g.oppositeNode(n2,f);
     354      if(countIncEdges(g,n2)>2)
     355        {
     356//        std::cout << "Remove an Edge" << std::endl;
     357          UEdge ff=enext[f];
     358          g.erase(e);
     359          g.erase(f);
     360          UEdge ne=g.addEdge(n1,n3);
     361          enext[p]=ne;
     362          enext[ne]=ff;
     363          ednum--;
     364        }
     365    }
     366
     367  std::cout << "Total edge length (tour) : " << totalLen() << std::endl;
     368
     369  tsp_improve();
     370 
     371  std::cout << "Total edge length (2-opt tour) : " << totalLen() << std::endl;
     372}
    280373
    281374
     
    307400    .onlyOneGroup("dist")
    308401    .boolOption("eps", "Also generate .eps output (prefix.eps)")
     402    .boolOption("dir", "Directed graph is generated (each edges are replaced by two directed ones)")
    309403    .boolOption("2con", "Create a two connected planar graph")
    310404    .optionGroup("alg","2con")
     
    313407    .boolOption("tsp", "Create a TSP tour")
    314408    .optionGroup("alg","tsp")
     409    .boolOption("tsp2", "Create a TSP tour (tree based)")
     410    .optionGroup("alg","tsp2")
    315411    .onlyOneGroup("alg")
    316412    .other("[prefix]","Prefix of the output files. Default is 'lgf-gen-out'")
     
    373469    std::cout << "#2-opt improvements: " << tsp_impr_num << std::endl;
    374470  }
     471  if(ap["tsp2"]) {
     472    tsp2();
     473    std::cout << "#2-opt improvements: " << tsp_impr_num << std::endl;
     474  }
    375475  else if(ap["2con"]) {
    376476    std::cout << "Make triangles\n";
     
    396496      coords(coords).run();
    397497
    398   UGraphWriter<ListUGraph>(prefix+".lgf",g).
    399     writeNodeMap("coordinates_x",scaleMap(xMap(coords),600)).
    400     writeNodeMap("coordinates_y",scaleMap(yMap(coords),600)).
    401     run();
    402 }
    403 
     498  if(ap["dir"])
     499    GraphWriter<ListUGraph>(prefix+".lgf",g).
     500      writeNodeMap("coordinates_x",scaleMap(xMap(coords),600)).
     501      writeNodeMap("coordinates_y",scaleMap(yMap(coords),600)).
     502      run();
     503  else UGraphWriter<ListUGraph>(prefix+".lgf",g).
     504         writeNodeMap("coordinates_x",scaleMap(xMap(coords),600)).
     505         writeNodeMap("coordinates_y",scaleMap(yMap(coords),600)).
     506         run();
     507}
     508
Note: See TracChangeset for help on using the changeset viewer.