Utilizzo di proprietà raggruppate come mappa del peso in dijkstra_shortest_paths

Question

Forse questa è una domanda stupida, ma sto cercando di utilizzare BGL dijkstra_shortest_paths, e, in particolare, di utilizzare un campo della mia proprietà in bundle Edge come la mappa del peso. I miei tentativi hanno attualmente portato a decine di pagine di errori del compilatore, quindi spero che qualcuno sappia come aiutarmi. Questo è essenzialmente ciò che il mio codice è simile:

struct GraphEdge { 
    float length; 
    // other cruft 
}; 
struct GraphVertex { 
    ... 
}; 
typedef boost::adjacency_list 
<boost::vecS, boost::vecS, boost::directedS, 
GraphVertex, GraphEdge> GraphType; 

posso compilare il grafico senza problemi, ma quando si tratta di chiamare dijkstra_shortest_paths, ho nei guai. Mi piacerebbe utilizzare il campo length. In particolare, mi piacerebbe sapere qual è il pezzo di voodoo spinta necessaria per andare in forma in una chiamata in questo modo:

GraphType m_graph; 

vector<int> predecessor(num_vertices(m_graph)); 
vector<float> distances(num_vertices(m_graph), 0.0f); 
vector<int> vertex_index_map(num_vertices(m_graph)); 
for (size_t i=0; i<vertex_index_map.size(); ++i) { 
    vertex_index_map[i] = i; 
} 

dijkstra_shortest_paths(m_graph, vertex_from, predecessor, distances, 
         weightmap, vertex_index_map, 
         std::less<float>(), closed_plus<float>(), 
         (std::numeric_limits<float>::max)(), 0.0f, 
         default_dijkstra_visitor()); 
// How do I write the right version of weightmap here? 

tale che weightmap in qualche modo associare un particolare bordo del mio grafico con il corrispondente length campo nel proprietà. Sono sicuro che c'è un modo semplice per farlo, ma la documentazione per BGL è incredibilmente opaca per me. Se puoi dirmi dove nella documentazione è descritto l'esempio, sarei molto felice anch'io.

Grazie in anticipo!

Answer 1

Nel caso qualcuno si preoccupa di questo, utilizzando la versione parametro denominato della chiamata sembra aver funzionato, come segue:

dijkstra_shortest_paths(m_graph, vertex_from, 
         weight_map(get(&TrafficGraphEdge::length, m_graph)) 
         .distance_map(make_iterator_property_map(distances.begin(), 
                   get(vertex_index, m_graph)))); 

Questo è nella documentazione, here. Non so ancora come usare la versione "parametro non-chiamato" della chiamata, comunque.

Answer 2

Ok, ho solo perso troppo tempo su questo problema. Ecco la soluzione per i posteri:

/** 
* @brief Example concerning bundled properties. 
* @author Pierre-Andre Noel 
* @date September 10 2012 
*/ 

#include <iostream> 
#include <boost/graph/adjacency_list.hpp> 

/// The type of the field we are interested in. 
typedef int interesting_type; 

/// The struct whose elements will be bundled in each vertex. 
struct bundled_in_vertex_type 
{ 
    /// Something interesting. 
    interesting_type something; 
}; 

int main() 
{ 
    typedef boost::adjacency_list< boost::vecS, boost::vecS, boost::undirectedS, bundled_in_vertex_type > graph_type; 
    typedef graph_type::vertex_descriptor vertex_descriptor_type; 

    /// Create a graph of two vertices. 
    graph_type g(2); 

    /// Name the two nodes. 
    const vertex_descriptor_type v1(*boost::vertices(g).first), v2(*(++boost::vertices(g).first)); 

    // Store some stuff in the two nodes, the "easy" way. 
    g[v1].something = interesting_type(42); 
    g[v2].something = interesting_type(999); 

    // Now what you came here for. 
    /// An handle providing direct access to the field "something". 
    boost::property_map< graph_type, interesting_type bundled_in_vertex_type::* >::type handle_to_something(boost::get(&bundled_in_vertex_type::something, g)); 
    // You can now use "handle_to_something" for whatever deed you are interested in. 

    // Just checking that it works. 
    std::cout << "Vertex v1's ""something"" field is: " << handle_to_something[v1] << std::endl; 
    std::cout << "Vertex v2's ""something"" field is: " << handle_to_something[v2] << std::endl; 

    // Thank you and have a nice day. 
    return 0; 
} 

Scherzi a parte, questa biblioteca è grande, ma la documentation definitivamente carente. Questo dovrebbe essere un aspetto banale.

---

EDIT

Se si utilizza C++ 11, allora si può preferire la seguente alternativa.

auto handle_to_something(boost::get(&bundled_in_vertex_type::something, g)); 

Answer 3

Per quanto potente possa essere il BGL, sfortunatamente, non è molto facile da usare a mio parere onesto. Ottenere questo al lavoro ha preso un po 'di notevole tentativi ed errori, ma qui è una versione funzionante compilata con Boost 1.53.0 [vogliamo usare l'algoritmo di Dijkstra sulla variabile 'tasso' in __edge_data]:

struct __edge_data 
{ 
    double rate; 
    double edge_thickness; 
    size_t colour; 
}; 

struct __vertex_data 
{ 
    size_t colour; 
    size_t shape_code; 
    string name; 
}; 

typedef boost::adjacency_list<boost::vecS, boost::vecS, boost::directedS, __vertex_data, __edge_data> DIgraph; 
typedef boost::graph_traits<DIgraph>::vertex_descriptor vertexx; 
typedef boost::graph_traits<DIgraph>::vertex_iterator vertexx_iter; 
typedef boost::graph_traits<DIgraph>::edge_descriptor edgee; 

// functor 
template<typename T> 
struct combine_min : public std::binary_function<T, T, T> 
{ 
     T const operator()(const T& a, const T& b) const 
     { 
      return b < a ? (b) : (a); 
     } 
}; 

// functor 
template<typename T> 
struct compare_less_than : public std::binary_function<T, T, bool> 
{ 
     bool const operator()(const T& a, const T& b) const 
     { 
      return a < b; 
     } 
}; 

void graph_analysis() 
{ 
    ... 

     std::vector<vertexx> parents(num_vertices(G)); 
     std::vector<double> distances(num_vertices(G)); 

     auto p_map = boost::make_iterator_property_map(&parents[0], boost::get(boost::vertex_index, G)); 
     auto d_map = boost::make_iterator_property_map(&distances[0], boost::get(boost::vertex_index, G)); 
     auto w_map = boost::get(&__edge_data::rate_rate, G); // <=== THIS IS THE TRICK!!! 
     auto n_map = boost::get(&__vertex_data::name, G); 

     boost::dijkstra_shortest_paths(G, start_vertex_vector, 
     boost::weight_map(w_map). 
       predecessor_map(p_map). 
       distance_map(d_map). 
       distance_combine(combine_min<double>()). 
       distance_compare(compare_less_than<double>())); 

    ... 
} 

Spero sinceramente questo aiuta! Il mio tentativo qui era di mostrare come accedere a tutte le principali 'funzionalità' disponibili all'algoritmo.