boost graph metric_tsp_approx solution not following graph edges

Question

I am trying to solve the traveling salesmen problem on a graph created using boost::adjacency_list. I am using the metric_tsp_approx to solve the tsp. The problem I am facing is that the solution does not follow the graph edges. The solution connects vertices in the graph which are not directly connected. I wanted to know if this is how the library works or if I am doing something wrong. The solution does not look correct either. I had 4 vertices forming a square, the solution should have been going along the perimeter, but it was going along the diagonal instead. There was no edge along the diagonal.

This is my adjacency_list:

boost::adjacency_list<boost::setS, boost::listS, boost::undirectedS,
                                boost::property<boost::vertex_index_t, int>,
                                boost::property<boost::edge_weight_t, double>,
                                boost::no_property>

Add vertex and add edge functions:

boost::add_vertex(id, graph);
boost::add_edge(id1, id2, weight, graph);  // weight is euclidean distance

TSP solver:

std::vector<VertexDescriptor> tsp_path;  //VertexDescriptor is adjacency_list::vertex_descriptor
metric_tsp_approx_tour(graph, back_inserter(tsp_path));

I also tried passing the weightmap to the metric_tsp_approx_tour but the same problem persists.

Can someone help me solve this? If the boost metric_tsp_approx_tour does not consider the edges of the graph, is there a way to make it consider them?

sehe sehe · Accepted Answer · 2020-09-18T20:38:03

The docs: https://www.boost.org/doc/libs/1_74_0/libs/graph/doc/metric_tsp_approx.html

This is a traveling salesperson heuristic for generating a tour of vertices for a fully connected undirected graph with weighted edges that obey the triangle inequality.

(emphasis mine)

The "fully connected graph" clause does state that all vertices are assumed to be connected.

Note as well, the vertex index is assumed to map to [0,num_vertices(graph)).

BONUS

As a bonus I tried to work out a minimal working example for the algorithm. It does seem to work as advertised:

Live On Coliru

#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/graph_utility.hpp>
#include <boost/graph/metric_tsp_approx.hpp>

using Graph = 
    boost::adjacency_list<boost::setS, boost::listS, boost::undirectedS,
        boost::property<boost::vertex_index_t, int>,
        boost::property<boost::edge_weight_t, double>,
        boost::no_property>;

using VertexDescriptor = Graph::vertex_descriptor;

int main() {
    std::vector const points { std::pair
        { 4., 9. }, // these can be randomized
        { 2., 6. },
        { 4., 1. },
        { 1., 1. },
    };

    Graph graph;
    for (auto i = 0u; i < points.size(); ++i) {
        add_vertex(i, graph);
    }

    for (auto i = 0u; i < points.size(); ++i) {
        auto va = vertex(i, graph);

        // undirected, so only need traverse higher vertices for connections
        for (auto j = i+1; j < points.size(); ++j) {
            auto vb = vertex(j, graph);

            auto const [ax, ay] = points.at(i);
            auto const [bx, by] = points.at(j);
            auto const dx = bx - ax;
            auto const dy = by - ay;

            add_edge(va, vb, sqrt(dx*dx + dy*dy), graph); // weight is euclidean distance
        }
    }

    print_graph(graph);

    std::vector<VertexDescriptor> tsp_path(num_vertices(graph));  //VertexDescriptor is adjacency_list::vertex_descriptor
    metric_tsp_approx_tour(graph, back_inserter(tsp_path));

    auto idmap = get(boost::vertex_index, graph);
    for (auto vd : tsp_path) {
        if (vd != graph.null_vertex()) {
            auto [x,y] = points.at(idmap[vd]); 
            std::cout << " {" << x << "," << y << "}";
        }
    }
}

Prints

0 <--> 1 2 3 
1 <--> 0 2 3 
2 <--> 0 1 3 
3 <--> 0 1 2 
 {4,9} {2,6} {1,1} {4,1} {4,9}

boost graph metric_tsp_approx solution not following graph edges

1 Answers

BONUS