trayectoria más corta de Dijkstra con VertexList = listas en el gráfico impulso

Question

soy bastante nuevo para impulsar el gráfico. Estoy tratando de adaptar un ejemplo para encontrar el algoritmo Dijkstra Shortest Path que usó VertexList = vecS. Cambié el contenedor de vértices a ListS. Aprendí que tenemos que proporcionar nuestro propio vertex_index para que el algoritmo funcione si usamos listS.

int main(int, char *[]) 
{ 
    typedef float Weight; 
    typedef boost::property<boost::edge_weight_t, Weight> WeightProperty; 
    typedef boost::property<boost::vertex_name_t, std::string> NameProperty; 
    typedef boost::property<boost::vertex_index_t, int> IndexProperty; 

    typedef boost::adjacency_list < boost::listS, boost::listS, boost::directedS, 
    NameProperty, WeightProperty > Graph; 

    typedef boost::graph_traits <Graph>::vertex_descriptor Vertex; 
    typedef boost::graph_traits <Graph>::vertex_iterator Viter; 

    typedef boost::property_map < Graph, boost::vertex_index_t >::type IndexMap; 
    typedef boost::property_map < Graph, boost::vertex_name_t >::type NameMap; 

    typedef boost::iterator_property_map < Vertex*, IndexMap, Vertex, Vertex& > PredecessorMap; 
    typedef boost::iterator_property_map < Weight*, IndexMap, Weight, Weight& > DistanceMap; 

    Graph g; 


    Vertex v0 = boost::add_vertex(std::string("v0"), g); 
    Vertex v1 = boost::add_vertex(std::string("v1"), g); 
    Vertex v2 = boost::add_vertex(std::string("v2"), g); 
    Vertex v3 = boost::add_vertex(std::string("v3"), g); 

    Weight weight0 = 5; 
    Weight weight1 = 3; 
    Weight weight2 = 2; 
    Weight weight3 = 4; 

    boost::add_edge(v0, v1, weight0, g); 
    boost::add_edge(v1, v3, weight1, g); 
    boost::add_edge(v0, v2, weight2, g); 
    boost::add_edge(v2, v3, weight3, g); 


    std::vector<Vertex> predecessors(boost::num_vertices(g)); // To store parents 
    std::vector<Weight> distances(boost::num_vertices(g)); // To store distances 

    IndexMap indexMap; // = boost::get(boost::vertex_index, g); 
    NameMap name; 
    Viter i, iend; 
//Create our own vertex index. This is what I changed in the original code 
    int c = 0; 
    for (boost::tie(i, iend) = vertices(g); i != iend; ++i, ++c) { 
     indexMap[*i] = c; // **Error points to this line** 
     name[*i] = 'A' + c; 
    } 
PredecessorMap predecessorMap(&predecessors[0], indexMap); 
DistanceMap distanceMap(&distances[0], indexMap); 
boost::dijkstra_shortest_paths(g, v0, boost::distance_map(distanceMap).predecessor_map(predecessorMap)); 


    // Extract a shortest path 
    std::cout << std::endl; 
    typedef std::vector<Graph::edge_descriptor> PathType; 
    PathType path; 
    Vertex v = v3; 
    for(Vertex u = predecessorMap[v]; 
    u != v; // Keep tracking the path until we get to the source 
    v = u, u = predecessorMap[v]) // Set the current vertex to the current predecessor,  and the predecessor to one level up 
    { 
    std::pair<Graph::edge_descriptor, bool> edgePair = boost::edge(u, v, g); 
    Graph::edge_descriptor edge = edgePair.first; 
    path.push_back(edge); 
    } 

    // Write shortest path 
    std::cout << "Shortest path from v0 to v3:" << std::endl; 
    float totalDistance = 0; 
    for(PathType::reverse_iterator pathIterator = path.rbegin(); pathIterator !=  path.rend(); ++pathIterator) 
    { 
    std::cout << name[boost::source(*pathIterator, g)] << " -> " <<  name[boost::target(*pathIterator, g)] 
       << " = " << boost::get(boost::edge_weight, g, *pathIterator) <<  std::endl; 

    } 

    std::cout << std::endl; 

    std::cout << "Distance: " << distanceMap[v3] << std::endl; 

    return EXIT_SUCCESS; 
} 

me sale el siguiente error:

/spvec.cpp:62:20: error: no puede competir con 'operador =' en 'index.boost :: :: adj_list_vertex_property_map operador [] [con Graph = impulso :: adjacency_list>, impulsar :: propiedad>, ValueType = impulso :: :: error_property_not_found detalle, referencia = impulso :: :: detalle error_property_not_found &, Tag = impulso :: vertex_index_t, impulsar :: :: adj_list_vertex_property_map key_type = void *] (i.std :: _ List_iterator < _Tp> :: operator * with _Tp = void *, _Tp & = void * &) = c '

Estoy seguro de que cometí un error al crear mi propio índice de vértices. Pero no pude averiguar exactamente cuál es el problema. ¿Alguien tiene algunas sugerencias sobre lo que estoy haciendo mal ..

Answer 1

BGL tiene en realidad un ejemplo del uso dijkstra_shortest_paths con listas/listas, pero no está vinculado a partir de la documentación HTML: http://www.boost.org/doc/libs/release/libs/graph/example/dijkstra-example-listS.cpp

¿Cuál es el mensaje de error tratando de decirle (error: no match for ‘operator=’ in ‘index.boost::adj_list_vertex_property_map...ValueType = boost::detail::error_property_not_found...) es que no hay almacenamiento por vértice de la propiedad vertex_index_t, que es lo adj_list_vertex_property_map necesidades. Para solucionar el problema, puede cambiar su Graphtypedef que incluyen almacenamiento por vértice de la propiedad vertex_index_t o utilizar un mapa de la propiedad "externa" como associative_property_map.

El ejemplo dijkstra-example-listS.cpp utiliza el enfoque de cambiar el gráfico typedef. Para utilizar este enfoque en su código, se podría definir:

typedef boost::adjacency_list <boost::listS, boost::listS, boost::directedS, 
    boost::property<boost::vertex_name_t, std::string, boost::property<boost::vertex_index_t, int> >, 
    boost::property<boost::edge_weight_t, Weight> > Graph; 

Answer 2

Si alguien está interesado en la solución, creando un associative_property_map como se sugiere en la respuesta anterior resolvió el problema:

typedef std::map<vertex_desc, size_t>IndexMap; 
    IndexMap mapIndex; 
    boost::associative_property_map<IndexMap> propmapIndex(mapIndex); 
    //indexing the vertices 
    int i=0; 
    BGL_FORALL_VERTICES(v, g, pGraph) 
    { 
     boost::put(propmapIndex, v, i++); 
    } 

A continuación, pasar este Mapa de índice vértice a la llamada dijkstra_shortest_paths() como un parámetro nombrado. PD: BGL_FORALL_VERTICES() se define en < boost/graph/iteration/iteration_macros.hpp>