c – Dijkstra具有VertexList的最短路径=升压图中的ListS

前端之家收集整理的这篇文章主要介绍了c – Dijkstra具有VertexList的最短路径=升压图中的ListS前端之家小编觉得挺不错的,现在分享给大家,也给大家做个参考。
我对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*,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,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;
}

我收到以下错误

在/ index = = 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> :: with _Tp = void *,_Tp& = void *&)= c’

我确定我在创建自己的顶点索引时犯了一个错误.但究竟究竟是什么问题.有人对我做错了什么有一些建议吗

解决方法

BGL实际上有一个使用dijkstra_shortest_paths与listS / listS的例子,但它没有链接到HTML文档: http://www.boost.org/doc/libs/release/libs/graph/example/dijkstra-example-listS.cpp

这个错误信息正在尝试告诉你(错误:在’index.boost :: adj_list_vertex_property_map …中的’operator =’不匹配… ValueType = boost :: detail :: error_property_not_found …)是没有per- vertex_index_t属性的顶点存储,这是adj_list_vertex_property_map需要的.要解决这个问题,您可以更改Graph typedef以包含vertex_index_t属性的每顶点存储,也可以使用“external”属性映射(例如,associative_property_map).

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

typedef boost::adjacency_list <boost::listS,boost::property<boost::vertex_name_t,std::string,boost::property<boost::vertex_index_t,int> >,boost::property<boost::edge_weight_t,Weight> > Graph;
原文链接:https://www.f2er.com/c/111793.html

猜你在找的C&C++相关文章