lemon/christofides_tsp.h
author Peter Kovacs <kpeter@inf.elte.hu>
Sat, 08 Jan 2011 22:49:09 +0100
changeset 1032 62ba43576f85
child 1033 9a51db038228
permissions -rw-r--r--
Doc group for TSP algorithms (#386)
     1 #ifndef LEMON_CHRISTOFIDES_TSP_H
     2 #define LEMON_CHRISTOFIDES_TSP_H
     3 
     4 #include <lemon/full_graph.h>
     5 #include <lemon/smart_graph.h>
     6 #include <lemon/path.h>
     7 #include <lemon/kruskal.h>
     8 #include <lemon/matching.h>
     9 #include <lemon/adaptors.h>
    10 #include <lemon/maps.h>
    11 #include <lemon/euler.h>
    12 
    13 namespace lemon {
    14   
    15   namespace christofides_helper {
    16     template <class L>
    17     L vectorConvert(const std::vector<FullGraph::Node> &_path) {
    18       return L(_path.begin(), _path.end());
    19     }
    20   
    21     template <>
    22     std::vector<FullGraph::Node> vectorConvert(const std::vector<FullGraph::Node> &_path) {
    23       return _path;
    24     }
    25   }
    26   
    27   template <typename CM>
    28   class ChristofidesTsp {
    29     private:
    30       GRAPH_TYPEDEFS(SmartGraph);
    31 
    32     public:
    33       typedef typename CM::Value Cost;
    34       typedef SmartGraph::EdgeMap<Cost> CostMap;
    35     
    36       ChristofidesTsp(const FullGraph &gr, const CM &cost) : _cost(_gr), fullg(gr), fullcost(cost), nr(_gr) {
    37         graphCopy(gr, _gr).nodeCrossRef(nr).edgeMap(cost, _cost).run();
    38       }
    39 
    40       Cost run() {
    41         _path.clear();
    42         
    43         SmartGraph::EdgeMap<bool> tree(_gr);
    44         kruskal(_gr, _cost, tree);
    45         
    46         FilterEdges<SmartGraph> treefiltered(_gr, tree);
    47         InDegMap<FilterEdges<SmartGraph> > deg(treefiltered);
    48         
    49         SmartGraph::NodeMap<bool> oddfilter(_gr, false);
    50         FilterNodes<SmartGraph> oddNodes(_gr, oddfilter);
    51         
    52         for (NodeIt n(_gr); n!=INVALID; ++n) {
    53           if (deg[n]%2 == 1) {
    54             oddNodes.enable(n);
    55           }
    56         }
    57         
    58         NegMap<CostMap> negmap(_cost);
    59         MaxWeightedPerfectMatching<FilterNodes<SmartGraph>,
    60                   NegMap<CostMap> > perfmatch(oddNodes, negmap);
    61         perfmatch.run();
    62         
    63         for (FilterNodes<SmartGraph>::EdgeIt e(oddNodes); e!=INVALID; ++e) {
    64           if (perfmatch.matching(e)) {
    65             treefiltered.enable(_gr.addEdge(_gr.u(e), _gr.v(e)));
    66           }
    67         }
    68         
    69         FilterEdges<SmartGraph>::NodeMap<bool> seen(treefiltered, false);
    70         for (EulerIt<FilterEdges<SmartGraph> > e(treefiltered); e!=INVALID; ++e) {
    71           if (seen[treefiltered.target(e)]==false) {
    72             _path.push_back(nr[treefiltered.target(e)]);
    73             seen[treefiltered.target(e)] = true;
    74           }
    75         }
    76 
    77         _sum = fullcost[ fullg.edge(_path.back(), _path.front()) ];
    78         for (unsigned int i=0; i<_path.size()-1; ++i)
    79           _sum += fullcost[ fullg.edge(_path[i], _path[i+1]) ];
    80 
    81         return _sum;
    82       }
    83 
    84       template <typename L>
    85       void tourNodes(L &container) {
    86         container(christofides_helper::vectorConvert<L>(_path));
    87       }
    88       
    89       template <template <typename> class L>
    90       L<FullGraph::Node> tourNodes() {
    91         return christofides_helper::vectorConvert<L<FullGraph::Node> >(_path);
    92       }
    93 
    94       const std::vector<Node>& tourNodes() {
    95         return _path;
    96       }
    97       
    98       Path<FullGraph> tour() {
    99         Path<FullGraph> p;
   100         if (_path.size()<2)
   101           return p;
   102 
   103         for (unsigned int i=0; i<_path.size()-1; ++i) {
   104           p.addBack(fullg.arc(_path[i], _path[i+1]));
   105         }
   106         p.addBack(fullg.arc(_path.back(), _path.front()));
   107         
   108         return p;
   109       }
   110       
   111       Cost tourCost() {
   112         return _sum;
   113       }
   114       
   115 
   116   private:
   117     SmartGraph _gr;
   118     CostMap _cost;
   119     Cost _sum;
   120     const FullGraph &fullg;
   121     const CM &fullcost;
   122     std::vector<FullGraph::Node> _path;
   123     SmartGraph::NodeMap<FullGraph::Node> nr;
   124   };
   125 
   126 
   127 }; // namespace lemon
   128 
   129 #endif