B
B
becks2015-05-26 11:16:24
C++ / C#
becks, 2015-05-26 11:16:24

What is the error of plotting the shortest path with BGL (boost graph library)?

I'm trying to use BGL to find the shortest path from one vertex to all the others in the graph. Wrote this code:

#include <iostream>
#include <boost/graph/graph_traits.hpp>
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/dijkstra_shortest_paths.hpp>
#include <boost/property_map/property_map.hpp>
 
#include"cdu/CduNetworkModeExtractor.h"
 
usingnamespace std;
usingnamespace boost;
 
typedefadjacency_list <listS, vecS, directedS, no_property, property<edge_weight_t, int>> Graph;
typedefgraph_traits<Graph>::vertex_descriptor VertexDescriptor;
typedefstd::pair<int,int> Edge;
 
int main()
{
  ...	
  //----Graph----
  QVector<ElectricityEdge> q_edges = mode.edges;
  vector<Edge> edges;
  
  foreach(ElectricityEdgee, q_edges)
    edges.push_back(Edge(e.sourceNode, e.destNode));

  std::vector<int> weights(edges.size(), 1);
  
  Graph graph(edges.begin(), edges.end(), weights.begin(), mode.nodes.size());
  
  vector<VertexDescriptor> p( num_vertices(graph) );
  vector<int> distance( num_vertices(graph) );
  VertexDescriptor s = vertex(1,graph);
  
  dijkstra_shortest_paths(graph, s, predecessor_map(&(*p.begin())).distance_map(&(*distance.begin())));
  
  graph_traits<Graph>::vertex_iterator vi,vend;
  boost::tie(vp,vend)=vertices(graph);
  
  std::for_each(vp, vend, [&distance](int value)
        { std::cout << "distanceto" << value << "equalto" << distance[value] << "\n"; }
  );
  ---------
  return 0;
}

The code doesn't work correctly. The reason, as far as I understand, is the lack of sequential numbering of nodes in the graph. Those. the graph can have nodes with numbers 15, 17, 23, but no nodes 16, 18-22. On the test example, the maximum node number is 900451, and the actual number of nodes is 4511. However, num_vertices(graph) returns 900452 (or 900451, I don't remember). From here I concluded that he counts by the maximum node number.
Please tell me how to correct the example. The only way out now I see is to make a correspondence map with a serial number - the real number of the node.

Answer the question

In order to leave comments, you need to log in

Didn't find what you were looking for?

Ask your question

Ask a Question

731 491 924 answers to any question