]>
git.proxmox.com Git - ceph.git/blob - ceph/src/boost/libs/graph/test/metric_tsp_approx.cpp
57560bd4d1eb1ccebcafcaabe29f0f493a7a17a6
1 //=======================================================================
3 // Author: Matyas W Egyhazy
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 //=======================================================================
16 #include <boost/assert.hpp>
17 #include <boost/lexical_cast.hpp>
18 #include <boost/random.hpp>
19 #include <boost/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>
27 // TODO: Integrate this into the test system a little better. We need to run
28 // the test with some kind of input file.
30 template<typename PointType
>
33 bool operator()(const boost::simple_point
<PointType
>& l
,
34 const boost::simple_point
<PointType
>& r
) const
35 { return (l
.x
> r
.x
); }
38 //add edges to the graph (for each node connect it to all other nodes)
39 template<typename VertexListGraph
, typename PointContainer
,
40 typename WeightMap
, typename VertexIndexMap
>
41 void connectAllEuclidean(VertexListGraph
& g
,
42 const PointContainer
& points
,
43 WeightMap wmap
, // Property maps passed by value
44 VertexIndexMap vmap
, // Property maps passed by value
47 using namespace boost
;
49 typedef typename graph_traits
<VertexListGraph
>::edge_descriptor Edge
;
50 typedef typename graph_traits
<VertexListGraph
>::vertex_iterator VItr
;
55 pair
<VItr
, VItr
> verts(vertices(g
));
56 for (VItr
src(verts
.first
); src
!= verts
.second
; src
++)
58 for (VItr
dest(src
); dest
!= verts
.second
; dest
++)
62 double weight(sqrt(pow(
63 static_cast<double>(points
[vmap
[*src
]].x
-
64 points
[vmap
[*dest
]].x
), 2.0) +
65 pow(static_cast<double>(points
[vmap
[*dest
]].y
-
66 points
[vmap
[*src
]].y
), 2.0)));
68 boost::tie(e
, inserted
) = add_edge(*src
, *dest
, g
);
78 // Create a randomly generated point
79 // scatter time execution
80 void testScalability(unsigned numpts
)
82 using namespace boost
;
85 typedef adjacency_matrix
<undirectedS
, no_property
,
86 property
<edge_weight_t
, double,
87 property
<edge_index_t
, int> > > 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
;
93 boost::mt19937
rng(time(0));
94 uniform_real
<> range(0.01, (numpts
* 2));
95 variate_generator
<boost::mt19937
&, uniform_real
<> >
99 simple_point
<double> pnt
;
101 while (points
.size() < numpts
)
109 WeightMap
weight_map(get(edge_weight
, g
));
110 vector
<simple_point
<double> > point_vec(points
.begin(), points
.end());
112 connectAllEuclidean(g
, point_vec
, weight_map
, get(vertex_index
, g
), numpts
);
118 // Run the TSP approx, creating the visitor on the fly.
119 metric_tsp_approx(g
, make_tsp_tour_len_visitor(g
, back_inserter(c
), len
, weight_map
));
121 cout
<< "Number of points: " << num_vertices(g
) << endl
;
122 cout
<< "Number of edges: " << num_edges(g
) << endl
;
123 cout
<< "Length of tour: " << len
<< endl
;
124 cout
<< "Elapsed: " << t
.elapsed() << endl
;
127 template <typename PositionVec
>
128 void checkAdjList(PositionVec v
)
131 using namespace boost
;
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
;
145 VertexIndexMap v_map
;
146 VPropertyMap
v_pmap(v_map
);
147 EWeightPropertyMap
w_pmap(w_map
);
151 //create vertex index map
154 for (boost::tie(vi
, ve
) = vertices(g
); vi
!= ve
; ++vi
)
161 connectAllEuclidean(g
, v
, w_pmap
,
164 metric_tsp_approx_from_vertex(g
,
168 tsp_tour_visitor
<back_insert_iterator
<Container
> >
171 cout
<< "adj_list" << endl
;
172 for (Container::iterator itr
= c
.begin(); itr
!= c
.end(); ++itr
) {
173 cout
<< v_map
[*itr
] << " ";
175 cout
<< endl
<< endl
;
183 cerr
<< "To run this program properly please place a "
184 << "file called graph.txt"
185 << endl
<< "into the current working directory." << endl
186 << "Each line of this file should be a coordinate specifying the"
187 << endl
<< "location of a vertex" << endl
188 << "For example: " << endl
<< "1,2" << endl
<< "20,4" << endl
189 << "15,7" << endl
<< endl
;
192 int main(int argc
, char* argv
[])
194 using namespace boost
;
197 typedef vector
<simple_point
<double> > PositionVec
;
198 typedef adjacency_matrix
<undirectedS
, no_property
,
199 property
<edge_weight_t
, double> > Graph
;
200 typedef graph_traits
<Graph
>::vertex_descriptor Vertex
;
201 typedef vector
<Vertex
> Container
;
202 typedef property_map
<Graph
, edge_weight_t
>::type WeightMap
;
203 typedef property_map
<Graph
, vertex_index_t
>::type VertexMap
;
205 // Make sure that the the we can parse the given file.
212 // Open the graph file, failing if one isn't given on the command line.
213 ifstream
fin(argv
[1]);
222 PositionVec position_vec
;
225 while (getline(fin
, line
))
227 simple_point
<double> vertex
;
229 size_t idx(line
.find(","));
230 string
xStr(line
.substr(0, idx
));
231 string
yStr(line
.substr(idx
+ 1, line
.size() - idx
));
233 vertex
.x
= lexical_cast
<double>(xStr
);
234 vertex
.y
= lexical_cast
<double>(yStr
);
236 position_vec
.push_back(vertex
);
243 Graph
g(position_vec
.size());
244 WeightMap
weight_map(get(edge_weight
, g
));
245 VertexMap v_map
= get(vertex_index
, g
);
247 connectAllEuclidean(g
, position_vec
, weight_map
, v_map
, n
);
249 metric_tsp_approx_tour(g
, back_inserter(c
));
251 for (vector
<Vertex
>::iterator itr
= c
.begin(); itr
!= c
.end(); ++itr
)
255 cout
<< endl
<< endl
;
259 checkAdjList(position_vec
);
261 metric_tsp_approx_from_vertex(g
, *vertices(g
).first
,
262 get(edge_weight
, g
), get(vertex_index
, g
),
263 tsp_tour_visitor
<back_insert_iterator
<vector
<Vertex
> > >
266 for (vector
<Vertex
>::iterator itr
= c
.begin(); itr
!= c
.end(); ++itr
)
270 cout
<< endl
<< endl
;
276 metric_tsp_approx(g
, make_tsp_tour_len_visitor(g
, back_inserter(c
), len
, weight_map
));
278 catch (const bad_graph
& e
) {
279 cerr
<< "bad_graph: " << e
.what() << endl
;
283 cout
<< "Number of points: " << num_vertices(g
) << endl
;
284 cout
<< "Number of edges: " << num_edges(g
) << endl
;
285 cout
<< "Length of Tour: " << len
<< endl
;
288 pair
<Vertex
,Vertex
> triangleEdge
;
289 for (vector
<Vertex
>::iterator itr
= c
.begin(); itr
!= c
.end();
296 triangleEdge
.first
= *itr
;
300 triangleEdge
.second
= *itr
;
303 cout
<< endl
<< endl
;
306 testScalability(1000);
308 // if the graph is not fully connected then some of the
309 // assumed triangle-inequality edges may not exist
310 remove_edge(edge(triangleEdge
.first
, triangleEdge
.second
, g
).first
, g
);
312 // Make sure that we can actually trap incomplete graphs.
316 metric_tsp_approx(g
, make_tsp_tour_len_visitor(g
, back_inserter(c
), len
, weight_map
));
318 catch (const bad_graph
& e
) { caught
= true; }
319 BOOST_ASSERT(caught
);