550 |
544 |
551 { |
545 { |
552 std::vector<Node> leafs; |
546 std::vector<Node> leafs; |
553 for(NodeIt n(g);n!=INVALID;++n) |
547 for(NodeIt n(g);n!=INVALID;++n) |
554 if(countIncEdges(g,n)%2==1) leafs.push_back(n); |
548 if(countIncEdges(g,n)%2==1) leafs.push_back(n); |
555 for(unsigned int i=0;i<leafs.size();i+=2) |
549 |
556 g.addEdge(leafs[i],leafs[i+1]); |
550 // for(unsigned int i=0;i<leafs.size();i+=2) |
|
551 // g.addEdge(leafs[i],leafs[i+1]); |
|
552 |
|
553 std::vector<Pedge> pedges; |
|
554 for(unsigned int i=0;i<leafs.size()-1;i++) |
|
555 for(unsigned int j=i+1;j<leafs.size();j++) |
|
556 { |
|
557 Node n=leafs[i]; |
|
558 Node m=leafs[j]; |
|
559 Pedge p; |
|
560 p.a=n; |
|
561 p.b=m; |
|
562 p.len=(coords[m]-coords[n]).normSquare(); |
|
563 pedges.push_back(p); |
|
564 } |
|
565 std::sort(pedges.begin(),pedges.end(),pedgeLess); |
|
566 for(unsigned int i=0;i<pedges.size();i++) |
|
567 if(countIncEdges(g,pedges[i].a)%2 && |
|
568 countIncEdges(g,pedges[i].b)%2) |
|
569 g.addEdge(pedges[i].a,pedges[i].b); |
557 } |
570 } |
558 |
571 |
559 for(NodeIt n(g);n!=INVALID;++n) |
572 for(NodeIt n(g);n!=INVALID;++n) |
560 if(countIncEdges(g,n)%2) |
573 if(countIncEdges(g,n)%2 || countIncEdges(g,n)==0 ) |
561 std::cout << "GEBASZ!!!" << std::endl; |
574 std::cout << "GEBASZ!!!" << std::endl; |
562 |
575 |
|
576 for(UEdgeIt e(g);e!=INVALID;++e) |
|
577 if(g.source(e)==g.target(e)) |
|
578 std::cout << "LOOP GEBASZ!!!" << std::endl; |
|
579 |
563 std::cout << "Number of edges : " << countUEdges(g) << std::endl; |
580 std::cout << "Number of edges : " << countUEdges(g) << std::endl; |
564 |
|
565 // for(NodeIt n(g);n!=INVALID;++n) |
|
566 // if(countIncEdges(g,n)>2) |
|
567 // std::cout << "+"; |
|
568 // std::cout << std::endl; |
|
569 |
581 |
570 std::cout << "Total edge length (euler) : " << totalLen() << std::endl; |
582 std::cout << "Total edge length (euler) : " << totalLen() << std::endl; |
571 |
583 |
572 ListUGraph::UEdgeMap<UEdge> enext(g); |
584 ListUGraph::UEdgeMap<Edge> enext(g); |
573 { |
585 { |
574 UEulerIt<ListUGraph> e(g); |
586 UEulerIt<ListUGraph> e(g); |
575 UEdge eo=e; |
587 Edge eo=e; |
576 UEdge ef=e; |
588 Edge ef=e; |
577 // std::cout << "Tour edge: " << g.id(UEdge(e)) << std::endl; |
589 // std::cout << "Tour edge: " << g.id(UEdge(e)) << std::endl; |
578 for(++e;e!=INVALID;++e) |
590 for(++e;e!=INVALID;++e) |
579 { |
591 { |
580 // std::cout << "Tour edge: " << g.id(UEdge(e)) << std::endl; |
592 // std::cout << "Tour edge: " << g.id(UEdge(e)) << std::endl; |
581 enext[eo]=e; |
593 enext[eo]=e; |
582 eo=e; |
594 eo=e; |
583 } |
595 } |
584 enext[eo]=ef; |
596 enext[eo]=ef; |
585 } |
597 } |
586 |
598 |
587 std::cout << "Creating a tour from that..." << std::endl; |
599 std::cout << "Creating a tour from that..." << std::endl; |
588 |
600 |
589 int nnum = countNodes(g); |
601 int nnum = countNodes(g); |
590 int ednum = countUEdges(g); |
602 int ednum = countUEdges(g); |
591 |
603 |
592 for(UEdge p=UEdgeIt(g);ednum>nnum;p=enext[p]) |
604 for(Edge p=enext[UEdgeIt(g)];ednum>nnum;p=enext[p]) |
593 { |
605 { |
594 // std::cout << "Checking edge " << g.id(p) << std::endl; |
606 // std::cout << "Checking edge " << g.id(p) << std::endl; |
595 UEdge e=enext[p]; |
607 Edge e=enext[p]; |
596 UEdge f=enext[e]; |
608 Edge f=enext[e]; |
597 Node n2=common(e,f); |
609 Node n2=g.source(f); |
598 Node n1=g.oppositeNode(n2,e); |
610 Node n1=g.oppositeNode(n2,e); |
599 Node n3=g.oppositeNode(n2,f); |
611 Node n3=g.oppositeNode(n2,f); |
600 if(countIncEdges(g,n2)>2) |
612 if(countIncEdges(g,n2)>2) |
601 { |
613 { |
602 // std::cout << "Remove an Edge" << std::endl; |
614 // std::cout << "Remove an Edge" << std::endl; |
603 UEdge ff=enext[f]; |
615 Edge ff=enext[f]; |
604 g.erase(e); |
616 g.erase(e); |
605 g.erase(f); |
617 g.erase(f); |
606 UEdge ne=g.addEdge(n1,n3); |
618 if(n1!=n3) |
607 enext[p]=ne; |
619 { |
608 enext[ne]=ff; |
620 Edge ne=g.direct(g.addEdge(n1,n3),n1); |
609 ednum--; |
621 enext[p]=ne; |
|
622 enext[ne]=ff; |
|
623 ednum--; |
|
624 } |
|
625 else { |
|
626 enext[p]=ff; |
|
627 ednum-=2; |
|
628 } |
610 } |
629 } |
611 } |
630 } |
612 |
631 |
613 std::cout << "Total edge length (tour) : " << totalLen() << std::endl; |
632 std::cout << "Total edge length (tour) : " << totalLen() << std::endl; |
614 |
633 |
|
634 std::cout << "2-opt the tour..." << std::endl; |
|
635 |
615 tsp_improve(); |
636 tsp_improve(); |
616 |
637 |
617 std::cout << "Total edge length (2-opt tour) : " << totalLen() << std::endl; |
638 std::cout << "Total edge length (2-opt tour) : " << totalLen() << std::endl; |
618 } |
639 } |
619 |
640 |
759 std::cout << "Number of edges : " << countUEdges(g) << std::endl; |
780 std::cout << "Number of edges : " << countUEdges(g) << std::endl; |
760 double tlen=0; |
781 double tlen=0; |
761 for(UEdgeIt e(g);e!=INVALID;++e) |
782 for(UEdgeIt e(g);e!=INVALID;++e) |
762 tlen+=sqrt((coords[g.source(e)]-coords[g.target(e)]).normSquare()); |
783 tlen+=sqrt((coords[g.source(e)]-coords[g.target(e)]).normSquare()); |
763 std::cout << "Total edge length : " << tlen << std::endl; |
784 std::cout << "Total edge length : " << tlen << std::endl; |
|
785 |
764 if(ap["eps"]) |
786 if(ap["eps"]) |
765 graphToEps(g,prefix+".eps"). |
787 graphToEps(g,prefix+".eps"). |
766 scale(600).nodeScale(.2).edgeWidthScale(.001).preScale(false). |
788 scale(600).nodeScale(.2).edgeWidthScale(.001).preScale(false). |
767 coords(coords).run(); |
789 coords(coords).run(); |
768 |
790 |
769 if(ap["dir"]) |
791 if(ap["dir"]) |
770 GraphWriter<ListUGraph>(prefix+".lgf",g). |
792 GraphWriter<ListUGraph>(prefix+".lgf",g). |
771 writeNodeMap("coordinates_x",scaleMap(xMap(coords),600)). |
793 writeNodeMap("coordinates_x",scaleMap(xMap(coords),600)). |
772 writeNodeMap("coordinates_y",scaleMap(yMap(coords),600)). |
794 writeNodeMap("coordinates_y",scaleMap(yMap(coords),600)). |
773 run(); |
795 run(); |