[pgrouting-dev] cloning boost_drivedist.cpp to return predecessors

[Stephen Woodbridge]

Hi Anton,

I'm looking at boost_drivedist.cpp with the idea of clone it to also 
return the predecessor with each record output, but I have not worked in 
C++ before. So I think I have the idea but want to bounce it off you first.

...
   vertex_descriptor source_vertex = vertex( source_vertex_id, graph );

   std::vector<vertex_descriptor> predecessors(num_vertices(graph));
   std::vector<float8> distances(num_vertices(graph));

   dijkstra_shortest_paths(graph, source_vertex,
                           predecessor_map(&predecessors[0])
                           .weight_map(get(&Edge::cost, graph))
                           .distance_map(&distances[0]));


   graph_traits < graph_t >::vertex_iterator vi, vend;
   vector<path_element> path_vector;                // <<<< ????????
   int j=0;

   for(tie(vi, vend) = vertices(graph); vi != vend; vi++) {

     if( (double)distances[*vi] <= rdistance ) {

       path_element pe;

       graph_traits<graph_t>::vertex_descriptor s;
       graph_traits<graph_t>::vertex_descriptor p;   // <<<< add this

       s = vertex(*vi, graph);
       p = vertex(predecessor[*vi], graph);          // <<<< add this

       pe.vertex_id = graph[s].id;
       pe.parent_id = graph[p].id;                   // <<<< add this
       pe.edge_id   = graph[s].edge_id;
       pe.cost      = distances[*vi];

       path_vector.push_back( pe );
     }
   }

   if( path_vector.size() == 0 ) {
     *err_msg = (char *)"No path found";
     return 0;
   }

   vector<path_element>::iterator itr;
   *path = (path_element_t *) malloc( sizeof(path_element_t) *
                                      (path_vector.size() + 1) );
   *path_count = path_vector.size();

   for(j=0,itr=path_vector.begin();itr != path_vector.end();itr++,j++) {
     path_element pe = *itr;
     (*path)[j].vertex_id = pe.vertex_id;
     (*path)[j].parent_id = pe.parent_id;           // <<<< add this
     (*path)[j].edge_id   = pe.edge_id;
     (*path)[j].cost      = pe.cost;
   }

   return EXIT_SUCCESS;
}

So in addition to the above 3 lines, I would need to modify 
core/src/dijkstra.h

typedef struct path_element
{
     int vertex_id;
     int parent_id;   // <<< add this
     int edge_id;
     float8 cost;
} path_element_t;

What I'm not sure on is how (or if it is possible) to modify 
path_element pe to include parent_id item.

And finally in the C wrapper to this function I would need to update 
parent_id along with vertex_id to uncompress the range shift that was done.

Does this look like it will work? Did I forget anything?

Thoughts?

-Steve