Boost logo

Boost :

From: Matyas W Egyhazy (megyha80_at_[hidden])
Date: 2006-08-04 23:33:12


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:

I have attached a newer version and test driver. Comments are welcome.




//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" <<

        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);



    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

//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.


#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


    //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);
            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
        std::vector<Node> path_;
        typedef typename std::vector<Node>::const_iterator const_iterator;

        void preorder(Node n, const Tree& t)

        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


Boost list run by bdawes at, gregod at, cpdaniel at, john at