Dijkstra Shortest Path with VertexList = ListS nel grafico boost

Sono abbastanza nuovo per il grafico Boost. Sto cercando di adattare un esempio per trovare l’algoritmo Dijkstra Shortest Path che utilizzava VertexList = vecS. Ho cambiato il contenitore del vertice in ListS. Ho imparato che dobbiamo fornire il nostro vertex_index affinché l’algoritmo funzioni se usiamo listS.

int main(int, char *[]) { typedef float Weight; typedef boost::property WeightProperty; typedef boost::property NameProperty; typedef boost::property IndexProperty; typedef boost::adjacency_list  Graph; typedef boost::graph_traits ::vertex_descriptor Vertex; typedef boost::graph_traits ::vertex_iterator Viter; typedef boost::property_map ::type IndexMap; typedef boost::property_map ::type NameMap; typedef boost::iterator_property_map  PredecessorMap; typedef boost::iterator_property_map  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 predecessors(boost::num_vertices(g)); // To store parents std::vector 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 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 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; } 

Ottengo il seguente errore:

/spvec.cpp:62:20: errore: nessuna corrispondenza per ‘operator =’ in ‘index.boost :: adj_list_vertex_property_map :: operator [] [con Graph = boost :: adjacency_list>, boost :: proprietà>, ValueType = boost :: detail :: error_property_not_found, Reference = boost :: detail :: error_property_not_found &, Tag = boost :: vertex_index_t, boost :: adj_list_vertex_property_map :: key_type = void *] (i.std :: _ List_iterator :: operator * con _Tp = void *, _Tp & = void * &) = c ‘

Sono sicuro di aver fatto un errore nel creare il mio indice dei vertici. Ma non è riuscito a scoprire esattamente qual è il problema. Qualcuno ha qualche suggerimento su cosa sto facendo male …

In realtà, BGL ha un esempio di utilizzo dijkstra_shortest_paths con listS / listS, ma non è collegato alla documentazione HTML: http://www.boost.org/doc/libs/release/libs/graph/example/dijkstra-example-listS cpp

Cosa sta cercando di dirti il ​​messaggio di error: no match for 'operator=' in 'index.boost:: adj_list_vertex_property_map ...ValueType = boost::detail:: error_property_not_found ... ( error: no match for 'operator=' in 'index.boost:: adj_list_vertex_property_map ...ValueType = boost::detail:: error_property_not_found ... ) è che non esiste archiviazione vertice per la proprietà vertex_index_t , che è ciò che adj_list_vertex_property_map bisogno di adj_list_vertex_property_map . Per risolvere il problema, puoi modificare il tuo typedef Graph per includere l’archiviazione per-vertice per la proprietà vertex_index_t o utilizzare una mappa di proprietà “esterna” come associative_property_map .

L’ dijkstra-example-listS.cpp usa l’approccio di cambiare il typedef del grafico. Per utilizzare questo approccio nel codice, è ansible definire:

 typedef boost::adjacency_list  >, boost::property > Graph; 

Se qualcuno è interessato alla soluzione, la creazione di una carta_ativa_propriazione come suggerito nella risposta precedente ha risolto il problema:

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

Quindi passare questa mappa dell’indice di vertice alla chiamata dijkstra_shortest_paths () come parametro denominato. PS: BGL_FORALL_VERTICES () è definito in