f4c3@1031: #ifndef LEMON_CHRISTOFIDES_TSP_H
f4c3@1031: #define LEMON_CHRISTOFIDES_TSP_H
f4c3@1031: 
f4c3@1031: #include <lemon/full_graph.h>
f4c3@1031: #include <lemon/smart_graph.h>
f4c3@1031: #include <lemon/path.h>
f4c3@1031: #include <lemon/kruskal.h>
f4c3@1031: #include <lemon/matching.h>
f4c3@1031: #include <lemon/adaptors.h>
f4c3@1031: #include <lemon/maps.h>
f4c3@1031: #include <lemon/euler.h>
f4c3@1031: 
f4c3@1031: namespace lemon {
f4c3@1031:   
f4c3@1031:   namespace christofides_helper {
f4c3@1031:     template <class L>
f4c3@1031:     L vectorConvert(const std::vector<FullGraph::Node> &_path) {
f4c3@1031:       return L(_path.begin(), _path.end());
f4c3@1031:     }
f4c3@1031:   
f4c3@1031:     template <>
f4c3@1031:     std::vector<FullGraph::Node> vectorConvert(const std::vector<FullGraph::Node> &_path) {
f4c3@1031:       return _path;
f4c3@1031:     }
f4c3@1031:   }
f4c3@1031:   
f4c3@1031:   template <typename CM>
f4c3@1031:   class ChristofidesTsp {
f4c3@1031:     private:
f4c3@1031:       GRAPH_TYPEDEFS(SmartGraph);
f4c3@1031: 
f4c3@1031:     public:
f4c3@1031:       typedef typename CM::Value Cost;
f4c3@1031:       typedef SmartGraph::EdgeMap<Cost> CostMap;
f4c3@1031:     
f4c3@1031:       ChristofidesTsp(const FullGraph &gr, const CM &cost) : _cost(_gr), fullg(gr), fullcost(cost), nr(_gr) {
f4c3@1031:         graphCopy(gr, _gr).nodeCrossRef(nr).edgeMap(cost, _cost).run();
f4c3@1031:       }
f4c3@1031: 
f4c3@1031:       Cost run() {
f4c3@1031:         _path.clear();
f4c3@1031:         
f4c3@1031:         SmartGraph::EdgeMap<bool> tree(_gr);
f4c3@1031:         kruskal(_gr, _cost, tree);
f4c3@1031:         
f4c3@1031:         FilterEdges<SmartGraph> treefiltered(_gr, tree);
f4c3@1031:         InDegMap<FilterEdges<SmartGraph> > deg(treefiltered);
f4c3@1031:         
f4c3@1031:         SmartGraph::NodeMap<bool> oddfilter(_gr, false);
f4c3@1031:         FilterNodes<SmartGraph> oddNodes(_gr, oddfilter);
f4c3@1031:         
f4c3@1031:         for (NodeIt n(_gr); n!=INVALID; ++n) {
f4c3@1031:           if (deg[n]%2 == 1) {
f4c3@1031:             oddNodes.enable(n);
f4c3@1031:           }
f4c3@1031:         }
f4c3@1031:         
f4c3@1031:         NegMap<CostMap> negmap(_cost);
f4c3@1031:         MaxWeightedPerfectMatching<FilterNodes<SmartGraph>,
f4c3@1031:                   NegMap<CostMap> > perfmatch(oddNodes, negmap);
f4c3@1031:         perfmatch.run();
f4c3@1031:         
f4c3@1031:         for (FilterNodes<SmartGraph>::EdgeIt e(oddNodes); e!=INVALID; ++e) {
f4c3@1031:           if (perfmatch.matching(e)) {
f4c3@1031:             treefiltered.enable(_gr.addEdge(_gr.u(e), _gr.v(e)));
f4c3@1031:           }
f4c3@1031:         }
f4c3@1031:         
f4c3@1031:         FilterEdges<SmartGraph>::NodeMap<bool> seen(treefiltered, false);
f4c3@1031:         for (EulerIt<FilterEdges<SmartGraph> > e(treefiltered); e!=INVALID; ++e) {
f4c3@1031:           if (seen[treefiltered.target(e)]==false) {
f4c3@1031:             _path.push_back(nr[treefiltered.target(e)]);
f4c3@1031:             seen[treefiltered.target(e)] = true;
f4c3@1031:           }
f4c3@1031:         }
f4c3@1031: 
f4c3@1031:         _sum = fullcost[ fullg.edge(_path.back(), _path.front()) ];
f4c3@1031:         for (unsigned int i=0; i<_path.size()-1; ++i)
f4c3@1031:           _sum += fullcost[ fullg.edge(_path[i], _path[i+1]) ];
f4c3@1031: 
f4c3@1031:         return _sum;
f4c3@1031:       }
f4c3@1031: 
f4c3@1031:       template <typename L>
f4c3@1031:       void tourNodes(L &container) {
f4c3@1031:         container(christofides_helper::vectorConvert<L>(_path));
f4c3@1031:       }
f4c3@1031:       
f4c3@1031:       template <template <typename> class L>
f4c3@1031:       L<FullGraph::Node> tourNodes() {
f4c3@1031:         return christofides_helper::vectorConvert<L<FullGraph::Node> >(_path);
f4c3@1031:       }
f4c3@1031: 
f4c3@1031:       const std::vector<Node>& tourNodes() {
f4c3@1031:         return _path;
f4c3@1031:       }
f4c3@1031:       
f4c3@1031:       Path<FullGraph> tour() {
f4c3@1031:         Path<FullGraph> p;
f4c3@1031:         if (_path.size()<2)
f4c3@1031:           return p;
f4c3@1031: 
f4c3@1031:         for (unsigned int i=0; i<_path.size()-1; ++i) {
f4c3@1031:           p.addBack(fullg.arc(_path[i], _path[i+1]));
f4c3@1031:         }
f4c3@1031:         p.addBack(fullg.arc(_path.back(), _path.front()));
f4c3@1031:         
f4c3@1031:         return p;
f4c3@1031:       }
f4c3@1031:       
f4c3@1031:       Cost tourCost() {
f4c3@1031:         return _sum;
f4c3@1031:       }
f4c3@1031:       
f4c3@1031: 
f4c3@1031:   private:
f4c3@1031:     SmartGraph _gr;
f4c3@1031:     CostMap _cost;
f4c3@1031:     Cost _sum;
f4c3@1031:     const FullGraph &fullg;
f4c3@1031:     const CM &fullcost;
f4c3@1031:     std::vector<FullGraph::Node> _path;
f4c3@1031:     SmartGraph::NodeMap<FullGraph::Node> nr;
f4c3@1031:   };
f4c3@1031: 
f4c3@1031: 
f4c3@1031: }; // namespace lemon
f4c3@1031: 
f4c3@1031: #endif