[boost] [bgl] tsp 2-approximation

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

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_inequality_and_the_Christofides_algorithm 

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