Changeset 2446:dd20d76eed13 in lemon-0.x for tools
- Timestamp:
- 06/05/07 12:59:16 (17 years ago)
- Branch:
- default
- Phase:
- public
- Convert:
- svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@3283
- File:
-
- 1 edited
Legend:
- Unmodified
- Added
- Removed
-
tools/lgf-gen.cc
r2410 r2446 27 27 #include <lemon/graph_writer.h> 28 28 #include <lemon/arg_parser.h> 29 #include <lemon/euler.h> 29 30 #include <cmath> 30 31 #include <algorithm> … … 47 48 std::vector<Node> nodes; 48 49 ListUGraph::NodeMap<Point> coords(g); 50 51 52 double 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 } 49 58 50 59 int tsp_impr_num=0; … … 253 262 pedges.push_back(p); 254 263 } 255 en++;256 264 if(progress && en>=pr*double(N)/100) 257 265 { … … 271 279 if ( uf.join(pi->a,pi->b) ) { 272 280 g.addEdge(pi->a,pi->b); 281 en++; 273 282 if(en>=N-1) 274 283 break; … … 278 287 } 279 288 289 Node 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 295 void 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 } 280 373 281 374 … … 307 400 .onlyOneGroup("dist") 308 401 .boolOption("eps", "Also generate .eps output (prefix.eps)") 402 .boolOption("dir", "Directed graph is generated (each edges are replaced by two directed ones)") 309 403 .boolOption("2con", "Create a two connected planar graph") 310 404 .optionGroup("alg","2con") … … 313 407 .boolOption("tsp", "Create a TSP tour") 314 408 .optionGroup("alg","tsp") 409 .boolOption("tsp2", "Create a TSP tour (tree based)") 410 .optionGroup("alg","tsp2") 315 411 .onlyOneGroup("alg") 316 412 .other("[prefix]","Prefix of the output files. Default is 'lgf-gen-out'") … … 373 469 std::cout << "#2-opt improvements: " << tsp_impr_num << std::endl; 374 470 } 471 if(ap["tsp2"]) { 472 tsp2(); 473 std::cout << "#2-opt improvements: " << tsp_impr_num << std::endl; 474 } 375 475 else if(ap["2con"]) { 376 476 std::cout << "Make triangles\n"; … … 396 496 coords(coords).run(); 397 497 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.