|
1 #ifndef LEMON_GREEDY_TSP_H |
|
2 #define LEMON_GREEDY_TSP_H |
|
3 |
|
4 #include <lemon/path.h> |
|
5 #include <lemon/full_graph.h> |
|
6 #include <lemon/unionfind.h> |
|
7 #include <algorithm> |
|
8 |
|
9 namespace lemon { |
|
10 |
|
11 namespace greedy_tsp_helper { |
|
12 |
|
13 template <typename CostMap> |
|
14 class KeyComp { |
|
15 typedef typename CostMap::Key Key; |
|
16 const CostMap &cost; |
|
17 |
|
18 public: |
|
19 KeyComp(const CostMap &_cost) : cost(_cost) {} |
|
20 |
|
21 bool operator() (const Key &a, const Key &b) const { |
|
22 return cost[a] < cost[b]; |
|
23 } |
|
24 }; |
|
25 |
|
26 |
|
27 template <class L> |
|
28 L vectorConvert(const std::vector<FullGraph::Node> &_path) { |
|
29 return L(_path.begin(), _path.end()); |
|
30 } |
|
31 |
|
32 template <> |
|
33 std::vector<FullGraph::Node> vectorConvert(const std::vector<FullGraph::Node> &_path) { |
|
34 return _path; |
|
35 } |
|
36 |
|
37 } |
|
38 |
|
39 |
|
40 template <typename CM> |
|
41 class GreedyTsp { |
|
42 private: |
|
43 GRAPH_TYPEDEFS(FullGraph); |
|
44 |
|
45 public: |
|
46 typedef CM CostMap; |
|
47 typedef typename CM::Value Cost; |
|
48 |
|
49 GreedyTsp(const FullGraph &gr, const CostMap &cost) : _gr(gr), _cost(cost) {} |
|
50 |
|
51 Cost run() { |
|
52 typedef UnionFind<FullGraph::NodeMap<int> > Union; |
|
53 _nodes.clear(); |
|
54 |
|
55 std::vector<int> path; |
|
56 path.resize(_gr.nodeNum()*2, -1); |
|
57 |
|
58 std::vector<typename CostMap::Key> sorted_edges; |
|
59 sorted_edges.reserve(_gr.edgeNum()); |
|
60 for (EdgeIt n(_gr); n != INVALID; ++n) |
|
61 sorted_edges.push_back(n); |
|
62 |
|
63 std::sort(sorted_edges.begin(), sorted_edges.end(), greedy_tsp_helper::KeyComp<CostMap>(_cost)); |
|
64 |
|
65 FullGraph::NodeMap<int> nodemap(_gr); |
|
66 Union unionfind(nodemap); |
|
67 |
|
68 for (NodeIt n(_gr); n != INVALID; ++n) |
|
69 unionfind.insert(n); |
|
70 |
|
71 FullGraph::NodeMap<int> degree(_gr, 0); |
|
72 |
|
73 int nodesNum = 0, i = 0; |
|
74 |
|
75 while ( nodesNum != _gr.nodeNum()-1 ) { |
|
76 const Edge &e = sorted_edges[i]; |
|
77 |
|
78 const Node u = _gr.u(e), |
|
79 v = _gr.v(e); |
|
80 |
|
81 if (degree[u]<=1 && degree[v]<=1) { |
|
82 if (unionfind.join(u, v)) { |
|
83 ++degree[u]; |
|
84 ++degree[v]; |
|
85 ++nodesNum; |
|
86 |
|
87 const int uid = _gr.id(u), |
|
88 vid = _gr.id(v); |
|
89 |
|
90 |
|
91 path[uid*2 + (path[uid*2]==-1 ? 0 : 1)] = vid; |
|
92 path[vid*2 + (path[vid*2]==-1 ? 0 : 1)] = uid; |
|
93 } |
|
94 } |
|
95 |
|
96 ++i; |
|
97 } |
|
98 |
|
99 |
|
100 for (int i=0, n=-1; i<_gr.nodeNum()*2; ++i) { |
|
101 if (path[i] == -1) { |
|
102 if (n==-1) { |
|
103 n = i; |
|
104 } else { |
|
105 path[n] = i/2; |
|
106 path[i] = n/2; |
|
107 break; |
|
108 } |
|
109 } |
|
110 } |
|
111 |
|
112 |
|
113 for (int i=0, j=0, last=-1; i!=_gr.nodeNum(); ++i) { |
|
114 _nodes.push_back(_gr.nodeFromId(j)); |
|
115 |
|
116 if (path[2*j] != last) { |
|
117 last = j; |
|
118 j = path[2*j]; |
|
119 } else { |
|
120 last = j; |
|
121 j = path[2*j+1]; |
|
122 } |
|
123 } |
|
124 |
|
125 _sum = _cost[_gr.edge(_nodes.back(), _nodes.front())]; |
|
126 for (unsigned int i=0; i<_nodes.size()-1; ++i) |
|
127 _sum += _cost[_gr.edge(_nodes[i], _nodes[i+1])]; |
|
128 |
|
129 return _sum; |
|
130 } |
|
131 |
|
132 |
|
133 |
|
134 template <typename L> |
|
135 void tourNodes(L &container) { |
|
136 container(greedy_tsp_helper::vectorConvert<L>(_nodes)); |
|
137 } |
|
138 |
|
139 template <template <typename> class L> |
|
140 L<Node> tourNodes() { |
|
141 return greedy_tsp_helper::vectorConvert<L<Node> >(_nodes); |
|
142 } |
|
143 |
|
144 const std::vector<Node>& tourNodes() { |
|
145 return _nodes; |
|
146 } |
|
147 |
|
148 Path<FullGraph> tour() { |
|
149 Path<FullGraph> p; |
|
150 if (_nodes.size()<2) |
|
151 return p; |
|
152 |
|
153 for (unsigned int i=0; i<_nodes.size()-1; ++i) { |
|
154 p.addBack(_gr.arc(_nodes[i], _nodes[i+1])); |
|
155 } |
|
156 |
|
157 p.addBack(_gr.arc(_nodes.back(), _nodes.front())); |
|
158 |
|
159 return p; |
|
160 } |
|
161 |
|
162 Cost tourCost() { |
|
163 return _sum; |
|
164 } |
|
165 |
|
166 |
|
167 private: |
|
168 const FullGraph &_gr; |
|
169 const CostMap &_cost; |
|
170 Cost _sum; |
|
171 std::vector<Node> _nodes; |
|
172 }; |
|
173 |
|
174 }; // namespace lemon |
|
175 |
|
176 #endif |