1 | //======================================================================= |
2 | // Copyright 2008 |
3 | // Author: Matyas W Egyhazy |
4 | // |
5 | // Distributed under the Boost Software License, Version 1.0. (See |
6 | // accompanying file LICENSE_1_0.txt or copy at |
7 | // http://www.boost.org/LICENSE_1_0.txt) |
8 | //======================================================================= |
9 | |
10 | #include <iostream> |
11 | #include <vector> |
12 | #include <fstream> |
13 | #include <set> |
14 | #include <ctime> |
15 | |
16 | #include <boost/assert.hpp> |
17 | #include <boost/lexical_cast.hpp> |
18 | #include <boost/random.hpp> |
19 | #include <boost/timer/timer.hpp> |
20 | #include <boost/integer_traits.hpp> |
21 | #include <boost/graph/adjacency_matrix.hpp> |
22 | #include <boost/graph/adjacency_list.hpp> |
23 | #include <boost/graph/simple_point.hpp> |
24 | #include <boost/graph/metric_tsp_approx.hpp> |
25 | #include <boost/graph/graphviz.hpp> |
26 | |
27 | // TODO: Integrate this into the test system a little better. We need to run |
28 | // the test with some kind of input file. |
29 | |
30 | template < typename PointType > struct cmpPnt |
31 | { |
32 | bool operator()(const boost::simple_point< PointType >& l, |
33 | const boost::simple_point< PointType >& r) const |
34 | { |
35 | return (l.x > r.x); |
36 | } |
37 | }; |
38 | |
39 | // add edges to the graph (for each node connect it to all other nodes) |
40 | template < typename VertexListGraph, typename PointContainer, |
41 | typename WeightMap, typename VertexIndexMap > |
42 | void connectAllEuclidean(VertexListGraph& g, const PointContainer& points, |
43 | WeightMap wmap, // Property maps passed by value |
44 | VertexIndexMap vmap, // Property maps passed by value |
45 | int /*sz*/) |
46 | { |
47 | using namespace boost; |
48 | using namespace std; |
49 | typedef typename graph_traits< VertexListGraph >::edge_descriptor Edge; |
50 | typedef typename graph_traits< VertexListGraph >::vertex_iterator VItr; |
51 | |
52 | Edge e; |
53 | bool inserted; |
54 | |
55 | pair< VItr, VItr > verts(vertices(g)); |
56 | for (VItr src(verts.first); src != verts.second; src++) |
57 | { |
58 | for (VItr dest(src); dest != verts.second; dest++) |
59 | { |
60 | if (dest != src) |
61 | { |
62 | double weight( |
63 | sqrt(x: pow(x: static_cast< double >( |
64 | points[vmap[*src]].x - points[vmap[*dest]].x), |
65 | y: 2.0) |
66 | + pow(x: static_cast< double >( |
67 | points[vmap[*dest]].y - points[vmap[*src]].y), |
68 | y: 2.0))); |
69 | |
70 | boost::tie(e, inserted) = add_edge(*src, *dest, g); |
71 | |
72 | wmap[e] = weight; |
73 | } |
74 | } |
75 | } |
76 | } |
77 | |
78 | // Create a randomly generated point |
79 | // scatter time execution |
80 | void testScalability(unsigned numpts) |
81 | { |
82 | using namespace boost; |
83 | using namespace std; |
84 | |
85 | typedef adjacency_matrix< undirectedS, no_property, |
86 | property< edge_weight_t, double, property< edge_index_t, int > > > |
87 | Graph; |
88 | typedef graph_traits< Graph >::vertex_descriptor Vertex; |
89 | typedef property_map< Graph, edge_weight_t >::type WeightMap; |
90 | typedef set< simple_point< double >, cmpPnt< double > > PointSet; |
91 | typedef vector< Vertex > Container; |
92 | |
93 | boost::mt19937 rng(std::time(timer: 0)); |
94 | uniform_real<> range(0.01, (numpts * 2)); |
95 | variate_generator< boost::mt19937&, uniform_real<> > pnt_gen(rng, range); |
96 | |
97 | PointSet points; |
98 | simple_point< double > pnt; |
99 | |
100 | while (points.size() < numpts) |
101 | { |
102 | pnt.x = pnt_gen(); |
103 | pnt.y = pnt_gen(); |
104 | points.insert(x: pnt); |
105 | } |
106 | |
107 | Graph g(numpts); |
108 | WeightMap weight_map(get(tag: edge_weight, g)); |
109 | vector< simple_point< double > > point_vec(points.begin(), points.end()); |
110 | |
111 | connectAllEuclidean(g, points: point_vec, wmap: weight_map, vmap: get(vertex_index, g), numpts); |
112 | |
113 | Container c; |
114 | boost::timer::cpu_timer t; |
115 | t.start(); |
116 | double len = 0.0; |
117 | |
118 | // Run the TSP approx, creating the visitor on the fly. |
119 | metric_tsp_approx( |
120 | g, vis: make_tsp_tour_len_visitor(g, iter: back_inserter(x&: c), l&: len, map: weight_map)); |
121 | |
122 | cout << "Number of points: " << num_vertices(g) << endl; |
123 | cout << "Number of edges: " << num_edges(g) << endl; |
124 | cout << "Length of tour: " << len << endl; |
125 | cout << "Elapsed: " << boost::timer::format(times: t.elapsed()) << endl; |
126 | } |
127 | |
128 | template < typename PositionVec > void checkAdjList(PositionVec v) |
129 | { |
130 | using namespace std; |
131 | using namespace boost; |
132 | |
133 | typedef adjacency_list< listS, listS, undirectedS > Graph; |
134 | typedef graph_traits< Graph >::vertex_descriptor Vertex; |
135 | typedef graph_traits< Graph >::edge_descriptor Edge; |
136 | typedef vector< Vertex > Container; |
137 | typedef map< Vertex, std::size_t > VertexIndexMap; |
138 | typedef map< Edge, double > EdgeWeightMap; |
139 | typedef associative_property_map< VertexIndexMap > VPropertyMap; |
140 | typedef associative_property_map< EdgeWeightMap > EWeightPropertyMap; |
141 | typedef graph_traits< Graph >::vertex_iterator VItr; |
142 | |
143 | Container c; |
144 | EdgeWeightMap w_map; |
145 | VertexIndexMap v_map; |
146 | VPropertyMap v_pmap(v_map); |
147 | EWeightPropertyMap w_pmap(w_map); |
148 | |
149 | Graph g(v.size()); |
150 | |
151 | // create vertex index map |
152 | VItr vi, ve; |
153 | int idx(0); |
154 | for (boost::tie(t0&: vi, t1&: ve) = vertices(g_: g); vi != ve; ++vi) |
155 | { |
156 | Vertex v(*vi); |
157 | v_pmap[v] = idx; |
158 | idx++; |
159 | } |
160 | |
161 | connectAllEuclidean(g, v, w_pmap, v_pmap, v.size()); |
162 | |
163 | metric_tsp_approx_from_vertex(g, start: *vertices(g_: g).first, weightmap: w_pmap, indexmap: v_pmap, |
164 | vis: tsp_tour_visitor< back_insert_iterator< Container > >( |
165 | back_inserter(x&: c))); |
166 | |
167 | cout << "adj_list" << endl; |
168 | for (Container::iterator itr = c.begin(); itr != c.end(); ++itr) |
169 | { |
170 | cout << v_map[*itr] << " " ; |
171 | } |
172 | cout << endl << endl; |
173 | |
174 | c.clear(); |
175 | } |
176 | |
177 | static void usage() |
178 | { |
179 | using namespace std; |
180 | cerr << "To run this program properly please place a " |
181 | << "file called graph.txt" << endl |
182 | << "into the current working directory." << endl |
183 | << "Each line of this file should be a coordinate specifying the" |
184 | << endl |
185 | << "location of a vertex" << endl |
186 | << "For example: " << endl |
187 | << "1,2" << endl |
188 | << "20,4" << endl |
189 | << "15,7" << endl |
190 | << endl; |
191 | } |
192 | |
193 | int main(int argc, char* argv[]) |
194 | { |
195 | using namespace boost; |
196 | using namespace std; |
197 | |
198 | typedef vector< simple_point< double > > PositionVec; |
199 | typedef adjacency_matrix< undirectedS, no_property, |
200 | property< edge_weight_t, double > > |
201 | Graph; |
202 | typedef graph_traits< Graph >::vertex_descriptor Vertex; |
203 | typedef vector< Vertex > Container; |
204 | typedef property_map< Graph, edge_weight_t >::type WeightMap; |
205 | typedef property_map< Graph, vertex_index_t >::type VertexMap; |
206 | |
207 | // Make sure that the the we can parse the given file. |
208 | if (argc < 2) |
209 | { |
210 | usage(); |
211 | // return -1; |
212 | return 0; |
213 | } |
214 | |
215 | // Open the graph file, failing if one isn't given on the command line. |
216 | ifstream fin(argv[1]); |
217 | if (!fin) |
218 | { |
219 | usage(); |
220 | // return -1; |
221 | return 0; |
222 | } |
223 | |
224 | string line; |
225 | PositionVec position_vec; |
226 | |
227 | int n(0); |
228 | while (getline(is&: fin, str&: line)) |
229 | { |
230 | simple_point< double > vertex; |
231 | |
232 | size_t idx(line.find(s: "," )); |
233 | string xStr(line.substr(pos: 0, n: idx)); |
234 | string yStr(line.substr(pos: idx + 1, n: line.size() - idx)); |
235 | |
236 | vertex.x = lexical_cast< double >(arg: xStr); |
237 | vertex.y = lexical_cast< double >(arg: yStr); |
238 | |
239 | position_vec.push_back(x: vertex); |
240 | n++; |
241 | } |
242 | |
243 | fin.close(); |
244 | |
245 | Container c; |
246 | Graph g(position_vec.size()); |
247 | WeightMap weight_map(get(tag: edge_weight, g)); |
248 | VertexMap v_map = get(vertex_index, g); |
249 | |
250 | connectAllEuclidean(g, points: position_vec, wmap: weight_map, vmap: v_map, n); |
251 | |
252 | metric_tsp_approx_tour(g, o: back_inserter(x&: c)); |
253 | |
254 | for (vector< Vertex >::iterator itr = c.begin(); itr != c.end(); ++itr) |
255 | { |
256 | cout << *itr << " " ; |
257 | } |
258 | cout << endl << endl; |
259 | |
260 | c.clear(); |
261 | |
262 | checkAdjList(v: position_vec); |
263 | |
264 | metric_tsp_approx_from_vertex(g, start: *vertices(g_: g).first, weightmap: get(tag: edge_weight, g), |
265 | indexmap: get(vertex_index, g), |
266 | vis: tsp_tour_visitor< back_insert_iterator< vector< Vertex > > >( |
267 | back_inserter(x&: c))); |
268 | |
269 | for (vector< Vertex >::iterator itr = c.begin(); itr != c.end(); ++itr) |
270 | { |
271 | cout << *itr << " " ; |
272 | } |
273 | cout << endl << endl; |
274 | |
275 | c.clear(); |
276 | |
277 | double len(0.0); |
278 | try |
279 | { |
280 | metric_tsp_approx( |
281 | g, vis: make_tsp_tour_len_visitor(g, iter: back_inserter(x&: c), l&: len, map: weight_map)); |
282 | } |
283 | catch (const bad_graph& e) |
284 | { |
285 | cerr << "bad_graph: " << e.what() << endl; |
286 | return -1; |
287 | } |
288 | |
289 | cout << "Number of points: " << num_vertices(g) << endl; |
290 | cout << "Number of edges: " << num_edges(g) << endl; |
291 | cout << "Length of Tour: " << len << endl; |
292 | |
293 | int cnt(0); |
294 | pair< Vertex, Vertex > triangleEdge; |
295 | for (vector< Vertex >::iterator itr = c.begin(); itr != c.end(); |
296 | ++itr, ++cnt) |
297 | { |
298 | cout << *itr << " " ; |
299 | |
300 | if (cnt == 2) |
301 | { |
302 | triangleEdge.first = *itr; |
303 | } |
304 | if (cnt == 3) |
305 | { |
306 | triangleEdge.second = *itr; |
307 | } |
308 | } |
309 | cout << endl << endl; |
310 | c.clear(); |
311 | |
312 | testScalability(numpts: 1000); |
313 | |
314 | // if the graph is not fully connected then some of the |
315 | // assumed triangle-inequality edges may not exist |
316 | remove_edge(e: edge(u: triangleEdge.first, v: triangleEdge.second, g).first, g); |
317 | |
318 | // Make sure that we can actually trap incomplete graphs. |
319 | bool caught = false; |
320 | try |
321 | { |
322 | double len = 0.0; |
323 | metric_tsp_approx( |
324 | g, vis: make_tsp_tour_len_visitor(g, iter: back_inserter(x&: c), l&: len, map: weight_map)); |
325 | } |
326 | catch (const bad_graph& e) |
327 | { |
328 | caught = true; |
329 | } |
330 | BOOST_ASSERT(caught); |
331 | |
332 | return 0; |
333 | } |
334 | |