boost :: graph metric_tsp_approx со связанными свойствами завершается ошибкой во время выполнения - PullRequest
Новая
       22

boost :: graph metric_tsp_approx со связанными свойствами завершается ошибкой во время выполнения

0 голосов
/ 19 ноября 2018

Я пытаюсь запустить алгоритм metric_tsp_approx из boost BGL для решения простой задачи коммивояжера ( здесь документации и соответствующий пример ). Я использую связанные свойства, чтобы создать свой график. Код компилируется нормально, но во время выполнения при выполнении функции metric_tsp_approx(...) происходит сбой и выдается векторное значение утверждения вне диапазона . Я не могу понять, чего мне здесь не хватает, ниже я помещаю код, который вы можете запустить, чтобы воспроизвести ошибку: 

#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);
}
...