[1031] | 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 |
---|