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