diff options
Diffstat (limited to 'src/boost/libs/graph/test/metric_tsp_approx.cpp')
-rw-r--r-- | src/boost/libs/graph/test/metric_tsp_approx.cpp | 333 |
1 files changed, 333 insertions, 0 deletions
diff --git a/src/boost/libs/graph/test/metric_tsp_approx.cpp b/src/boost/libs/graph/test/metric_tsp_approx.cpp new file mode 100644 index 000000000..031c8eed1 --- /dev/null +++ b/src/boost/libs/graph/test/metric_tsp_approx.cpp @@ -0,0 +1,333 @@ +//======================================================================= +// Copyright 2008 +// Author: Matyas W Egyhazy +// +// Distributed under the Boost Software License, Version 1.0. (See +// accompanying file LICENSE_1_0.txt or copy at +// http://www.boost.org/LICENSE_1_0.txt) +//======================================================================= + +#include <iostream> +#include <vector> +#include <fstream> +#include <set> +#include <ctime> + +#include <boost/assert.hpp> +#include <boost/lexical_cast.hpp> +#include <boost/random.hpp> +#include <boost/timer/timer.hpp> +#include <boost/integer_traits.hpp> +#include <boost/graph/adjacency_matrix.hpp> +#include <boost/graph/adjacency_list.hpp> +#include <boost/graph/simple_point.hpp> +#include <boost/graph/metric_tsp_approx.hpp> +#include <boost/graph/graphviz.hpp> + +// TODO: Integrate this into the test system a little better. We need to run +// the test with some kind of input file. + +template < typename PointType > struct cmpPnt +{ + bool operator()(const boost::simple_point< PointType >& l, + const boost::simple_point< PointType >& r) const + { + return (l.x > r.x); + } +}; + +// add edges to the graph (for each node connect it to all other nodes) +template < typename VertexListGraph, typename PointContainer, + typename WeightMap, typename VertexIndexMap > +void connectAllEuclidean(VertexListGraph& g, const PointContainer& points, + WeightMap wmap, // Property maps passed by value + VertexIndexMap vmap, // Property maps passed by value + int /*sz*/) +{ + using namespace boost; + using namespace std; + typedef typename graph_traits< VertexListGraph >::edge_descriptor Edge; + typedef typename graph_traits< VertexListGraph >::vertex_iterator VItr; + + Edge e; + bool inserted; + + pair< VItr, VItr > verts(vertices(g)); + for (VItr src(verts.first); src != verts.second; src++) + { + for (VItr dest(src); dest != verts.second; dest++) + { + if (dest != src) + { + double weight( + sqrt(pow(static_cast< double >( + points[vmap[*src]].x - points[vmap[*dest]].x), + 2.0) + + pow(static_cast< double >( + points[vmap[*dest]].y - points[vmap[*src]].y), + 2.0))); + + boost::tie(e, inserted) = add_edge(*src, *dest, g); + + wmap[e] = weight; + } + } + } +} + +// Create a randomly generated point +// scatter time execution +void testScalability(unsigned numpts) +{ + using namespace boost; + using namespace std; + + typedef adjacency_matrix< undirectedS, no_property, + property< edge_weight_t, double, property< edge_index_t, int > > > + Graph; + typedef graph_traits< Graph >::vertex_descriptor Vertex; + typedef property_map< Graph, edge_weight_t >::type WeightMap; + typedef set< simple_point< double >, cmpPnt< double > > PointSet; + typedef vector< Vertex > Container; + + boost::mt19937 rng(time(0)); + uniform_real<> range(0.01, (numpts * 2)); + variate_generator< boost::mt19937&, uniform_real<> > pnt_gen(rng, range); + + PointSet points; + simple_point< double > pnt; + + while (points.size() < numpts) + { + pnt.x = pnt_gen(); + pnt.y = pnt_gen(); + points.insert(pnt); + } + + Graph g(numpts); + WeightMap weight_map(get(edge_weight, g)); + vector< simple_point< double > > point_vec(points.begin(), points.end()); + + connectAllEuclidean(g, point_vec, weight_map, get(vertex_index, g), numpts); + + Container c; + boost::timer::cpu_timer t; + t.start(); + double len = 0.0; + + // Run the TSP approx, creating the visitor on the fly. + metric_tsp_approx( + g, make_tsp_tour_len_visitor(g, back_inserter(c), len, weight_map)); + + cout << "Number of points: " << num_vertices(g) << endl; + cout << "Number of edges: " << num_edges(g) << endl; + cout << "Length of tour: " << len << endl; + cout << "Elapsed: " << boost::timer::format(t.elapsed()) << endl; +} + +template < typename PositionVec > void checkAdjList(PositionVec v) +{ + using namespace std; + using namespace boost; + + typedef adjacency_list< listS, listS, undirectedS > Graph; + typedef graph_traits< Graph >::vertex_descriptor Vertex; + typedef graph_traits< Graph >::edge_descriptor Edge; + typedef vector< Vertex > Container; + typedef map< Vertex, std::size_t > VertexIndexMap; + typedef map< Edge, double > EdgeWeightMap; + typedef associative_property_map< VertexIndexMap > VPropertyMap; + typedef associative_property_map< EdgeWeightMap > EWeightPropertyMap; + typedef graph_traits< Graph >::vertex_iterator VItr; + + Container c; + EdgeWeightMap w_map; + VertexIndexMap v_map; + VPropertyMap v_pmap(v_map); + EWeightPropertyMap w_pmap(w_map); + + Graph g(v.size()); + + // create vertex index map + VItr vi, ve; + int idx(0); + for (boost::tie(vi, ve) = vertices(g); vi != ve; ++vi) + { + Vertex v(*vi); + v_pmap[v] = idx; + idx++; + } + + connectAllEuclidean(g, v, w_pmap, v_pmap, v.size()); + + metric_tsp_approx_from_vertex(g, *vertices(g).first, w_pmap, v_pmap, + tsp_tour_visitor< back_insert_iterator< Container > >( + back_inserter(c))); + + cout << "adj_list" << endl; + for (Container::iterator itr = c.begin(); itr != c.end(); ++itr) + { + cout << v_map[*itr] << " "; + } + cout << endl << endl; + + c.clear(); +} + +static void usage() +{ + using namespace std; + cerr << "To run this program properly please place a " + << "file called graph.txt" << endl + << "into the current working directory." << endl + << "Each line of this file should be a coordinate specifying the" + << endl + << "location of a vertex" << endl + << "For example: " << endl + << "1,2" << endl + << "20,4" << endl + << "15,7" << endl + << endl; +} + +int main(int argc, char* argv[]) +{ + using namespace boost; + using namespace std; + + typedef vector< simple_point< double > > PositionVec; + typedef adjacency_matrix< undirectedS, no_property, + property< edge_weight_t, double > > + Graph; + typedef graph_traits< Graph >::vertex_descriptor Vertex; + typedef vector< Vertex > Container; + typedef property_map< Graph, edge_weight_t >::type WeightMap; + typedef property_map< Graph, vertex_index_t >::type VertexMap; + + // Make sure that the the we can parse the given file. + if (argc < 2) + { + usage(); + // return -1; + return 0; + } + + // Open the graph file, failing if one isn't given on the command line. + ifstream fin(argv[1]); + if (!fin) + { + usage(); + // return -1; + return 0; + } + + string line; + PositionVec position_vec; + + int n(0); + while (getline(fin, line)) + { + simple_point< double > vertex; + + size_t idx(line.find(",")); + string xStr(line.substr(0, idx)); + string yStr(line.substr(idx + 1, line.size() - idx)); + + vertex.x = lexical_cast< double >(xStr); + vertex.y = lexical_cast< double >(yStr); + + position_vec.push_back(vertex); + n++; + } + + fin.close(); + + Container c; + Graph g(position_vec.size()); + WeightMap weight_map(get(edge_weight, g)); + VertexMap v_map = get(vertex_index, g); + + connectAllEuclidean(g, position_vec, weight_map, v_map, n); + + metric_tsp_approx_tour(g, back_inserter(c)); + + for (vector< Vertex >::iterator itr = c.begin(); itr != c.end(); ++itr) + { + cout << *itr << " "; + } + cout << endl << endl; + + c.clear(); + + checkAdjList(position_vec); + + metric_tsp_approx_from_vertex(g, *vertices(g).first, get(edge_weight, g), + get(vertex_index, g), + tsp_tour_visitor< back_insert_iterator< vector< Vertex > > >( + back_inserter(c))); + + for (vector< Vertex >::iterator itr = c.begin(); itr != c.end(); ++itr) + { + cout << *itr << " "; + } + cout << endl << endl; + + c.clear(); + + double len(0.0); + try + { + metric_tsp_approx( + g, make_tsp_tour_len_visitor(g, back_inserter(c), len, weight_map)); + } + catch (const bad_graph& e) + { + cerr << "bad_graph: " << e.what() << endl; + return -1; + } + + cout << "Number of points: " << num_vertices(g) << endl; + cout << "Number of edges: " << num_edges(g) << endl; + cout << "Length of Tour: " << len << endl; + + int cnt(0); + pair< Vertex, Vertex > triangleEdge; + for (vector< Vertex >::iterator itr = c.begin(); itr != c.end(); + ++itr, ++cnt) + { + cout << *itr << " "; + + if (cnt == 2) + { + triangleEdge.first = *itr; + } + if (cnt == 3) + { + triangleEdge.second = *itr; + } + } + cout << endl << endl; + c.clear(); + + testScalability(1000); + + // if the graph is not fully connected then some of the + // assumed triangle-inequality edges may not exist + remove_edge(edge(triangleEdge.first, triangleEdge.second, g).first, g); + + // Make sure that we can actually trap incomplete graphs. + bool caught = false; + try + { + double len = 0.0; + metric_tsp_approx( + g, make_tsp_tour_len_visitor(g, back_inserter(c), len, weight_map)); + } + catch (const bad_graph& e) + { + caught = true; + } + BOOST_ASSERT(caught); + + return 0; +} |