|
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 |