|
1 #ifndef LEMON_NEAREST_NEIGHBOUR_TSP_H |
|
2 #define LEMON_NEAREST_NEIGHBOUR_TSP_H |
|
3 |
|
4 #include <deque> |
|
5 #include <lemon/full_graph.h> |
|
6 #include <lemon/path.h> |
|
7 #include <lemon/maps.h> |
|
8 |
|
9 namespace lemon { |
|
10 |
|
11 namespace nn_helper { |
|
12 template <class L> |
|
13 L dequeConvert(const std::deque<FullGraph::Node> &_path) { |
|
14 return L(_path.begin(), _path.end()); |
|
15 } |
|
16 |
|
17 template <> |
|
18 std::deque<FullGraph::Node> dequeConvert(const std::deque<FullGraph::Node> &_path) { |
|
19 return _path; |
|
20 } |
|
21 } |
|
22 |
|
23 template <typename CM> |
|
24 class NearestNeighborTsp { |
|
25 private: |
|
26 GRAPH_TYPEDEFS(FullGraph); |
|
27 |
|
28 public: |
|
29 typedef CM CostMap; |
|
30 typedef typename CM::Value Cost; |
|
31 |
|
32 NearestNeighborTsp(const FullGraph &gr, const CostMap &cost) : _gr(gr), _cost(cost) {} |
|
33 |
|
34 Cost run() { |
|
35 _path.clear(); |
|
36 |
|
37 Edge min_edge1 = INVALID, |
|
38 min_edge2 = INVALID; |
|
39 |
|
40 min_edge1 = mapMin(_gr, _cost); |
|
41 |
|
42 FullGraph::NodeMap<bool> used(_gr, false); |
|
43 |
|
44 Node n1 = _gr.u(min_edge1), |
|
45 n2 = _gr.v(min_edge1); |
|
46 |
|
47 _path.push_back(n1); |
|
48 _path.push_back(n2); |
|
49 |
|
50 used[n1] = true; |
|
51 used[n2] = true; |
|
52 |
|
53 min_edge1 = INVALID; |
|
54 |
|
55 while (int(_path.size()) != _gr.nodeNum()) { |
|
56 if (min_edge1 == INVALID) { |
|
57 for (IncEdgeIt e(_gr, n1); e!=INVALID; ++e) { |
|
58 if (!used[_gr.runningNode(e)]) { |
|
59 if (min_edge1==INVALID || _cost[min_edge1] > _cost[e]) |
|
60 min_edge1 = e; |
|
61 } |
|
62 } |
|
63 } |
|
64 |
|
65 if (min_edge2 == INVALID) { |
|
66 for (IncEdgeIt e(_gr, n2); e!=INVALID; ++e) { |
|
67 if (!used[_gr.runningNode(e)]) { |
|
68 if (min_edge2==INVALID || _cost[min_edge2] > _cost[e]) |
|
69 min_edge2 = e; |
|
70 } |
|
71 } |
|
72 } |
|
73 |
|
74 if ( _cost[min_edge1] < _cost[min_edge2] ) { |
|
75 n1 = (_gr.u(min_edge1) == n1) ? _gr.v(min_edge1) : _gr.u(min_edge1); |
|
76 _path.push_front(n1); |
|
77 |
|
78 used[n1] = true; |
|
79 min_edge1 = INVALID; |
|
80 |
|
81 if (_gr.u(min_edge2)==n1 || _gr.v(min_edge2)==n1) |
|
82 min_edge2 = INVALID; |
|
83 } else { |
|
84 n2 = (_gr.u(min_edge2) == n2) ? _gr.v(min_edge2) : _gr.u(min_edge2); |
|
85 _path.push_back(n2); |
|
86 |
|
87 used[n2] = true; |
|
88 min_edge2 = INVALID; |
|
89 |
|
90 if (_gr.u(min_edge1)==n2 || _gr.v(min_edge1)==n2) |
|
91 min_edge1 = INVALID; |
|
92 } |
|
93 } |
|
94 |
|
95 _sum = _cost[ _gr.edge(_path.back(), _path.front()) ]; |
|
96 for (unsigned int i=0; i<_path.size()-1; ++i) |
|
97 _sum += _cost[ _gr.edge(_path[i], _path[i+1]) ]; |
|
98 |
|
99 return _sum; |
|
100 } |
|
101 |
|
102 |
|
103 template <typename L> |
|
104 void tourNodes(L &container) { |
|
105 container(nn_helper::dequeConvert<L>(_path)); |
|
106 } |
|
107 |
|
108 template <template <typename> class L> |
|
109 L<Node> tourNodes() { |
|
110 return nn_helper::dequeConvert<L<Node> >(_path); |
|
111 } |
|
112 |
|
113 const std::deque<Node>& tourNodes() { |
|
114 return _path; |
|
115 } |
|
116 |
|
117 Path<FullGraph> tour() { |
|
118 Path<FullGraph> p; |
|
119 if (_path.size()<2) |
|
120 return p; |
|
121 |
|
122 for (unsigned int i=0; i<_path.size()-1; ++i) { |
|
123 p.addBack(_gr.arc(_path[i], _path[i+1])); |
|
124 } |
|
125 p.addBack(_gr.arc(_path.back(), _path.front())); |
|
126 |
|
127 return p; |
|
128 } |
|
129 |
|
130 Cost tourCost() { |
|
131 return _sum; |
|
132 } |
|
133 |
|
134 |
|
135 private: |
|
136 const FullGraph &_gr; |
|
137 const CostMap &_cost; |
|
138 Cost _sum; |
|
139 std::deque<Node> _path; |
|
140 }; |
|
141 |
|
142 |
|
143 }; // namespace lemon |
|
144 |
|
145 #endif |