带VertexList的Dijkstra最短路径=升压图列表

本文介绍了带VertexList的Dijkstra最短路径=升压图列表的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！ 问题描述

我很新的提升图形。我试图适应查找其使用VertexList时，血管内皮细胞=迪杰斯特拉最短路径算法的例子。我改变了顶点容器列表。我了解到，我们必须为我们自己的vertex_index因为如果我们用列表的算法来工作。

I am quite new to Boost graph. I am trying to adapt an example for finding Dijkstra Shortest Path algorithm which used VertexList = vecS. I changed the vertex container to ListS. I learned that we have to provide our own vertex_index for the algorithm to work if we use 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; }

我收到以下错误：

I get the following error:

/spvec.cpp:62:20：错误：index.boost :: adj_list_vertex_property_map ::运算符[]敌不过'运算符='[图表与升压= ::的adjacency_list>，提振::财产>值类型=的boost ::详细:: error_property_not_found，参考=的boost ::详细:: error_property_not_found和放大器;，标签=的boost :: vertex_index_t，提​​振:: adj_list_vertex_property_map :: key_type的=无效*]（i.std :: _ List_iterator＆LT; _TP>： ：运算符*与_TP =无效*，_TP＆安培; =无效*安培）= C

/spvec.cpp:62:20: error: no match for ‘operator=’ in ‘index.boost::adj_list_vertex_property_map::operator[] [with Graph = boost::adjacency_list >, boost::property >, 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<_Tp>::operator* with _Tp = void*, _Tp& = void*&) = c’

我相信，我在创造我自己的顶点索引犯了一个错误。但couldn't找出到底what's的问题。有没有人有什么我做错了一些建议。

I am sure I made a mistake in creating my own vertex index. But couldn´t find out exactly what´s the issue. Does anyone have some suggestions on what I am doing wrong..

推荐答案

BGL实际上有使用的例子 dijkstra_shortest_paths 使用列表/列表，但它不是从挂HTML文档：www.boost/doc/libs/release/libs/graph/example/dijkstra-example-listS.cpp

BGL actually has an example of using dijkstra_shortest_paths with listS/listS, but it's not linked to from the HTML documentation: www.boost/doc/libs/release/libs/graph/example/dijkstra-example-listS.cpp

什么错误消息想告诉你（错误：没有对应于index.boost运算符=':: adj_list_vertex_property_map ...的ValueType =提升： ：细节:: error_property_not_found ... ）是没有每个顶点存储为 vertex_index_t 属性，这就是 adj_list_vertex_property_map 的需求。要解决你可以改变问题的图 的typedef 来包括每个顶点存储为 vertex_index_t 属性或使用外部属性映射，如 associative_property_map 。

What the error message is trying to tell you (error: no match for ‘operator=’ in ‘index.boost::adj_list_vertex_property_map...ValueType = boost::detail::error_property_not_found...) is that there is no per-vertex storage for the vertex_index_t property, which is what adj_list_vertex_property_map needs. To fix the problem you can either change your Graph typedef to include per-vertex storage for the vertex_index_t property or use an "external" property map such as associative_property_map.

的 Dijkstra算法，例如-listS.cpp 示例使用改变图形的方法的typedef 。要在code使用这种方法，你可以定义：

The dijkstra-example-listS.cpp example uses the approach of changing the graph typedef. To use this approach in your code, you could define:

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;