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 {
operator ()cmpPnt32 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 >
connectAllEuclidean(VertexListGraph & g,const PointContainer & points,WeightMap wmap,VertexIndexMap vmap,int)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(pow(static_cast< double >(
64 points[vmap[*src]].x - points[vmap[*dest]].x),
65 2.0)
66 + pow(static_cast< double >(
67 points[vmap[*dest]].y - points[vmap[*src]].y),
68 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
testScalability(unsigned numpts)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(time(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(pnt);
105 }
106
107 Graph g(numpts);
108 WeightMap weight_map(get(edge_weight, g));
109 vector< simple_point< double > > point_vec(points.begin(), points.end());
110
111 connectAllEuclidean(g, point_vec, weight_map, 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, make_tsp_tour_len_visitor(g, back_inserter(c), len, 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(t.elapsed()) << endl;
126 }
127
checkAdjList(PositionVec v)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(vi, ve) = vertices(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, *vertices(g).first, w_pmap, v_pmap,
164 tsp_tour_visitor< back_insert_iterator< Container > >(
165 back_inserter(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
usage()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
main(int argc,char * argv[])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(fin, line))
229 {
230 simple_point< double > vertex;
231
232 size_t idx(line.find(","));
233 string xStr(line.substr(0, idx));
234 string yStr(line.substr(idx + 1, line.size() - idx));
235
236 vertex.x = lexical_cast< double >(xStr);
237 vertex.y = lexical_cast< double >(yStr);
238
239 position_vec.push_back(vertex);
240 n++;
241 }
242
243 fin.close();
244
245 Container c;
246 Graph g(position_vec.size());
247 WeightMap weight_map(get(edge_weight, g));
248 VertexMap v_map = get(vertex_index, g);
249
250 connectAllEuclidean(g, position_vec, weight_map, v_map, n);
251
252 metric_tsp_approx_tour(g, back_inserter(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(position_vec);
263
264 metric_tsp_approx_from_vertex(g, *vertices(g).first, get(edge_weight, g),
265 get(vertex_index, g),
266 tsp_tour_visitor< back_insert_iterator< vector< Vertex > > >(
267 back_inserter(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, make_tsp_tour_len_visitor(g, back_inserter(c), len, 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(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(edge(triangleEdge.first, 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, make_tsp_tour_len_visitor(g, back_inserter(c), len, weight_map));
325 }
326 catch (const bad_graph& e)
327 {
328 caught = true;
329 }
330 BOOST_ASSERT(caught);
331
332 return 0;
333 }
334