使用VertexList = ListS的boost图中的Dijkstra最短路径

Question

我对Boost图形库非常陌生。我试图调整一个使用VertexList = vecS的查找Dijkstra最短路径算法示例。我将顶点容器更改为ListS。我了解到，如果我们使用listS，则必须为算法提供自己的vertex_index才能使其正常工作。

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;
}

我遇到了以下错误：

/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’

我确定在创建自己的顶点索引时犯了一个错误，但是无法确定问题所在。是否有人能提出一些建议，告诉我我做错了什么？

- srkrish

---

不知道错误在哪里，就像是大海捞针一样，而且这根针可能甚至不在那段代码片段中。 - Anne Quinn

Answer 1

BGL实际上提供了使用listS/listS和dijkstra_shortest_paths的示例，但其未在HTML文档中链接：http://www.boost.org/doc/libs/release/libs/graph/example/dijkstra-example-listS.cpp

错误信息试图告诉您(error: no match for ‘operator=’ in ‘index.boost::adj_list_vertex_property_map...ValueType = boost::detail::error_property_not_found...)，即没有vertex_index_t属性的每个顶点的存储空间，这是adj_list_vertex_property_map所需的。要解决此问题，您可以更改Graph typedef，以包括vertex_index_t属性的每个顶点的存储空间，或者使用“外部”属性映射，例如associative_property_map。

dijkstra-example-listS.cpp示例使用更改图形typedef的方法。要在代码中使用此方法，您可以定义：

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;

- Daniel Trebbien

---

我不想像示例中那样在图形顶点属性中添加vertex_index_t属性。这样我就无法使用捆绑属性方法。虽然上面的代码没有使用捆绑属性，但最终我会使用它们。但正如你建议的那样，关联属性映射应该可以解决问题。我会尝试一下。 - srkrish

Answer 2

如果有人对解决方案感兴趣，可以按照之前的建议创建一个 associative_property_map 来解决问题:

   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++);
     }

然后将该顶点索引图作为命名参数传递给dijkstra_shortest_paths()调用。 PS：BGL_FORALL_VERTICES()在中定义。

- srkrish

---

能否提供完整的代码？前驱和距离映射的索引映射呢？您还需要传递它们的propmapIndex吗？vdesc是什么？它是向量属性吗？ - blakeO

感谢这个代码片段。我用它创建了一个vertex_index_map并将其传递给breadth_first_search函数。我已经发布了一个工作示例：https://dev59.com/723Xa4cB1Zd3GeqPf4oO#43780529 - opetroch