Nsryjdtyk

I am trying to run the metric_tsp_approx algorithm from boost BGL to solve a simple Traveling Salesman Problem (here the documentation and the related example). I use bundled properties to create my graph. The code compiles fine, but at runtime, when executing the function metric_tsp_approx(...), it crashes and gives the assertion vector subscript out of range. I cannot understand what I am missing here, below I put some code that you can run to reproduce the error:

#include <string>

#include <vector>

#include <string>

#include <iostream>



#include <boost/graph/adjacency_matrix.hpp>

#include <boost/graph/metric_tsp_approx.hpp>



using std::cout;

using std::endl;

using std::string;

using std::vector;



using namespace boost;



struct Trip

{

    double km;

    int travel_minutes;

};



struct Location

{

    string name;

    std::pair<double, double> coordinates;

    //the following function returns the euclidian distance between locations

    static double distance(const Location & l1, const Location & l2);

};



typedef boost::adjacency_matrix<boost::undirectedS, Location, Trip> Graph;

typedef typename Graph::vertex_descriptor Node;

typedef typename Graph::edge_descriptor Arc;



int main()

{

    //num of nodes in graph

    int N = 4;



    Graph g = Graph(N);



    //building a complete graph of 4 nodes on a 2x2 grid: coordinates of such nodes are (0,0), (0,1), (1,0), (1,1)

    //the member variable *km* of each arc is computed as the 

    //Euclidian distance between the source and target node



    Graph::vertex_iterator v, v_end;

    for (tie(v, v_end) = vertices(g); v != v_end; ++v)

    {

        Location loc;

        int idx_vertex = N - (int)std::distance(v, v_end);

        loc.name = "loc_" + std::to_string(idx_vertex);

        loc.coordinates.first = idx_vertex < 2 ? 0 : 1;

        loc.coordinates.second = idx_vertex % 2 == 0 ? 0 : 1;

        g[*v] = loc;

    }



    Graph::vertex_iterator i, i_end, j, j_end;

    for (tie(i, i_end) = vertices(g); i != i_end; ++i)

    {

        for (tie(j, j_end) = vertices(g); j != j_end; ++j)

        {

            Trip trip;

            trip.km = Location::distance(g[*i], g[*j]);

            trip.travel_minutes = (int)floor(trip.km);

            Arc a;

            bool inserted;

            tie(a,inserted) = add_edge(*i, *j, g);

            g[a] = trip;

        }

    }



    /*TSP*/



    vector<Node> tour;//solution of TSP

    double len = 0;//length of the tour



    auto vertex_indices = get(vertex_index, g);

    auto w_map = get(&Trip::km, g);//property map of Trip::km that I want to pass to metric_tsp_approx

    auto tour_visitor = make_tsp_tour_len_visitor(g, std::back_inserter(tour), len, w_map);



    //run

    metric_tsp_approx(g, w_map, vertex_indices, tour_visitor);//ERR: vector subscript out of range



    for (vector<Node>::iterator itr = tour.begin(); itr != tour.end(); ++itr)

        cout << g[*itr].name << " ";



    return 0;

}



double Location::distance(const Location & l1, const Location & l2)

{

    double lat_delta = l1.coordinates.first - l2.coordinates.first;

    double lng_delta = l1.coordinates.second - l2.coordinates.second;

    return sqrt(lat_delta*lat_delta + lng_delta*lng_delta);

}