Hello, I posted earlier on the boost-users list regarding an implementation of the tsp 2-approximation that I have implemented using the BGL. I have fixed it up a bit since my initial post simplifying both the interface and the implementation. The approximation algorithm runs in polynomial time and solves the TSP problem with the worst possible solution producing a path twice as long as the optimal solution. More information can be found regarding the algorithm/heuristic on page 1028 in "Introduction to Algorithms" by Cormen, Leiserson, Rivest, and Stein. A slightly different description can be found on Wikipedia: http://en.wikipedia.org/wiki/Traveling_salesperson_problem#Triangle_inequali... I have attached a newer version and test driver. Comments are welcome. Thanks, Matt 1,2 2,4 10,20 45,20 15,1 17,20 20,25 30,20 //Main test harness for the tsp_2_approximation solution generator #include <iostream> #include <vector> #include <fstream> #include <boost/lexical_cast.hpp> #include <boost/graph/simple_point.hpp> #include <boost/graph/tsp_2_approx.hpp> int main(int argc, char** argv) { using namespace boost; using namespace std; typedef vector<simple_point<double> > PositionVec; ifstream fin("graph.txt"); if (!fin) { 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 << "The output of the program will be a TSP tour of the graph" << endl; return -1; } 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(); vector<int> tour(n + 1); tsp_2_approximation(position_vec, &tour.front()); for (vector<int>::const_iterator itr = tour.begin(); itr != tour.end(); ++itr) { cout << *itr << " "; } return 0; } //======================================================================= // Copyright 2006 Virginia Tech // 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) //======================================================================= // //tsp_2_approximation //Takes a sequence of simple_points and performs 2-approximation //triangle inequality to generate an approximate tour solution for //the traveling salesperson problem in polynomial time. #ifndef BOOST_GRAPH_TSP_2APPROX_HPP #define BOOST_GRAPH_TSP_2APPROX_HPP #include <vector> #include <complex> #include <boost/graph/graph_as_tree.hpp> #include <boost/graph/adjacency_list.hpp> #include <boost/graph/prim_minimum_spanning_tree.hpp> namespace boost { //tour is the TSP approximation tour //pos is a coordinate map of the vertices represented as simple_points template<typename PositionMap, typename Tour> void tsp_2_approximation(const PositionMap& pos, Tour tour) { using namespace boost; using namespace std; typedef adjacency_list <vecS, vecS, directedS, property<vertex_distance_t, int>, property <edge_weight_t, double> >Graph; typedef graph_traits<Graph>::vertex_descriptor Vertex; typedef graph_traits <Graph>::edge_descriptor Edge; typedef iterator_property_map<vector<Vertex>::iterator, property_map<Graph, vertex_index_t>::type> ParentMap; typedef graph_as_tree<Graph, ParentMap> Tree; typedef tree_traits<Tree>::node_descriptor Node; int n(pos.size()); bool inserted; Edge e; Graph g(n); property_map<Graph, edge_weight_t>::type weight_map(get(edge_weight, g)); //add edges to the graph (for each node connect it to all other nodes) for (int q(0); q < n; ++q) { for (int i(q); i < n; ++i) { if (q != i) { //triangle distance double weight(sqrt(pow(static_cast<double>(pos[q].x - pos[i].x), 2.0) + pow(static_cast<double>(pos[i].y - pos[q].y), 2.0))); tie(e, inserted) = add_edge(q, i, g); weight_map[e] = weight; } } } //extract the mst using prim's minimum spanning tree algorithm vector<Vertex> mst_preds(num_vertices(g)); prim_minimum_spanning_tree(g, &mst_preds.front()); Graph mst(n); //build mst graph using the predecessor map from prim's mst algorithm int cnt(0); for (vector<Vertex>::const_iterator vi(mst_preds.begin()); vi != mst_preds.end(); ++vi, ++cnt) { if (*vi != cnt) { add_edge(*vi, cnt, mst); } } vector<Vertex> parent(num_vertices(mst)); Tree t(mst, 0, make_iterator_property_map(parent.begin(), get(vertex_index, mst))); //create tour using a preorder traversal of the mst PreorderTraverser<Node, Tree> vis; traverse_tree_ref(0, t, vis); cnt = 0; for (PreorderTraverser<Node, Tree>::const_iterator curr(vis.begin()); curr != vis.end(); ++curr, ++cnt) { tour[cnt] = *curr; } tour[cnt] = tour[0]; } } //boost namespace { //Recursive function that traverses a tree with a custom visttor template <class Tree, class TreeVisitor> void traverse_tree_ref(typename boost::tree_traits<Tree>::node_descriptor v, const Tree& t, TreeVisitor& visitor) { visitor.preorder(v, t); typename boost::tree_traits<Tree>::children_iterator i, end; tie(i, end) = children(v, t); if (i != end) { traverse_tree_ref(*i++, t, visitor); visitor.inorder(v, t); while (i != end) { traverse_tree_ref(*i++, t, visitor); } } else { visitor.inorder(v, t); } visitor.postorder(v, t); } //Tree visitor that keeps track of a preorder traversal of a tree template<typename Node, typename Tree> class PreorderTraverser { private: std::vector<Node> path_; public: typedef typename std::vector<Node>::const_iterator const_iterator; void preorder(Node n, const Tree& t) { path_.push_back(n); } void inorder(Node n, const Tree& t) const {} void postorder(Node, const Tree& t) const {} typename PreorderTraverser<typename Node, typename Tree>::const_iterator begin() const { return path_.begin(); } typename PreorderTraverser<typename Node, typename Tree>::const_iterator end() const { return path_.end(); } }; } // anonymous #endif //BOOST_GRAPH_TSP_2APPROX_HPP