c++ - priority - dijkstra shortest path algorithm

Dijkstra Shortest Path con VertexList=ListS en el gráfico de impulso

Question

Soy bastante nuevo en Boost graph. 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;
}

Obtuve el siguiente error:

/spvec.cpp:62:20: error: no coincide con ''operator ='' en ''index.boost :: adj_list_vertex_property_map :: operator [] [con 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 ''

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 en realidad tiene un ejemplo de uso de dijkstra_shortest_paths con listS / listS, pero no está vinculado desde la documentación HTML: http://www.boost.org/doc/libs/release/libs/graph/example/dijkstra-example-listS .cpp

Lo que el mensaje de error intenta 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 de vértice para la propiedad vertex_index_t , que es lo que necesita adj_list_vertex_property_map . Para solucionar el problema, puede cambiar su tipo de Graph para incluir el almacenamiento por vértice para la propiedad vertex_index_t o usar un mapa de propiedades "externo" como associative_property_map .

El dijkstra-example-listS.cpp utiliza el enfoque de cambiar el gráfico typedef . Para utilizar este enfoque en su código, puede 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, la creación de un mapa_propiedad_sociativa como se sugirió 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, pase este mapa de índice Vertex a la llamada dijkstra_shortest_paths () como parámetro con nombre. PD: BGL_FORALL_VERTICES () se define en <boost / graph / iteration / iteration_macros.hpp>