Floyd Warshall (все парные кратчайшие пути) на взвешенном неориентированном графике - Boost Graph

Question

У меня проблемы с Floyd Warshall (все пары кратчайших путей) в графе Boost. Есть ли способ напрямую предоставить ориентированный взвешенный график до floyd_warshall_all_pairs_shortest_paths? Кажется, что все его функции перегрузок требуют дополнительных параметров, которые я не совсем понимаю. Ниже приводится тестовый код, который я пишу (не компилируется, потому что мой призыв к floyd_warshall_all_pairs_shortest_paths неполно)

#include <iostream> 

#include <map> 
#include <boost/graph/adjacency_list.hpp> 
#include <boost/graph/floyd_warshall_shortest.hpp> 

typedef boost::property<boost::edge_weight_t, double> EdgeWeightProperty; 
typedef boost::adjacency_list<boost::vecS, boost::vecS, 
           boost::undirectedS, boost::no_property, 
           EdgeWeightProperty> Graph; 
typedef unsigned long t_indx; 

int main() 
{ 
    typedef boost::graph_traits<Graph>::vertex_descriptor vertex_des; 
    std::map<vertex_des, std::map<vertex_des, int> > matrix; 
    Graph sp_graph; 

    int edgelet_sp[] = { 1,  2, 
         1,  3, 
         1,  4, 
         2,  5, 
         3,  4, 
         3,  6, 
         4,  5, 
         4,  6, 
         4,  7, 
         5,  7, 
         6,  7 }; 
    double edgelet_vals[] = { 4, 
          10, 
          3, 
          1, 
          12, 
          20, 
          6, 
          3, 
          0, 
          3, 
          9}; 
    int num_edges = 11; 

    /* make the superpixel graph */ 
    for (t_indx i = 0; i < num_edges; ++i) { 
    add_edge(edgelet_sp[i]-1, edgelet_sp[i+num_edges]-1, edgelet_vals[i], sp_graph); 
    } 

    std::cout << num_vertices(sp_graph) << std::endl; 

    bool floyd2 = 
     boost::floyd_warshall_all_pairs_shortest_paths 
      (sp_graph, matrix); 
    return 0; 
} 

Я новичок в BGL, так что любая помощь будет оценена. Например, есть ли более элегантные способы написания этого кода (без объявления edgelet_sps и edgelet_vals, оба из которых будут заменены)? Благодарю.

Answer 1

Я понял (с помощью межсетевых экранов), что мне нужно использовать boost::get(boost::edge_weight, g), чтобы напрямую отправлять неориентированный взвешенный график в floyd warshall. Следующий код компилируется и работает (здесь приведен пример graph для примера ниже)

#include <iostream> 
#include <boost/graph/undirected_graph.hpp> 
#include <boost/graph/exterior_property.hpp> 
#include <boost/graph/floyd_warshall_shortest.hpp> 

// type for weight/distance on each edge 
typedef double t_weight; 

// define the graph type 
typedef boost::property<boost::edge_weight_t, t_weight> EdgeWeightProperty; 
typedef boost::adjacency_list<boost::vecS, boost::vecS, boost::undirectedS, 
           boost::no_property, EdgeWeightProperty> Graph; 

typedef boost::property_map<Graph, boost::edge_weight_t>::type WeightMap; 

// Declare a matrix type and its corresponding property map that 
// will contain the distances between each pair of vertices. 
typedef boost::exterior_vertex_property<Graph, t_weight> DistanceProperty; 
typedef DistanceProperty::matrix_type DistanceMatrix; 
typedef DistanceProperty::matrix_map_type DistanceMatrixMap; 


int main() 
{ 
    Graph g; 

    const int num_edges = 11; 

    // define edges 
    int edges[] = { 1,  2, 
        1,  3, 
        1,  4, 
        2,  5, 
        3,  4, 
        3,  6, 
        4,  5, 
        4,  6, 
        4,  7, 
        5,  7, 
        6,  7 }; 

    // define the weight on edges 
    t_weight weight[] = { 4, 
         10, 
         3, 
         1, 
         12, 
         20, 
         6, 
         3, 
         0, 
         3, 
         9 }; 

    // iterate over all edges and insert them in the graph 
    for (std::size_t k = 0; k < num_edges; ++k) 
    boost::add_edge(edges[k*2]-1, edges[k*2+1]-1, weight[k], g); 

    WeightMap weight_pmap = boost::get(boost::edge_weight, g); 

    // set the distance matrix to receive the floyd warshall output 
    DistanceMatrix distances(num_vertices(g)); 
    DistanceMatrixMap dm(distances, g); 

    // find all pairs shortest paths 
    bool valid = floyd_warshall_all_pairs_shortest_paths(g, dm, 
              boost::weight_map(weight_pmap)); 

    // check if there no negative cycles 
    if (!valid) { 
    std::cerr << "Error - Negative cycle in matrix" << std::endl; 
    return -1; 
    } 

    // print upper triangular part of the distance matrix 
    std::cout << "Distance matrix: " << std::endl; 
    for (std::size_t i = 0; i < num_vertices(g); ++i) { 
    for (std::size_t j = i; j < num_vertices(g); ++j) { 
     std::cout << "From vertex " << i+1 << " to " << j+1 << " : "; 
     if(distances[i][j] == std::numeric_limits<t_weight>::max()) 
     std::cout << "inf" << std::endl; 
     else 
     std::cout << distances[i][j] << std::endl; 
    } 
    std::cout << std::endl; 
    } 

    return 0; 
}