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

[Stephen Woodbridge]

Hi Anton,

Welcome back and hope you are feeling better. I hate being sick, and I 
think a bad case of the flu is about the worse.

So I did play around with this a little but in the end ripped it out of 
the postgresql server environment and test things out in a plan command 
tool. I just using the libpq-fe.h to the database from C. You should see 
more on this in my follow up posts. In my code, with the predecessor 
changes I get all the result records that I would expect. So there is 
some bug in the pgRouting driving distance code that where the symptom 
is that some result records are not in the records set. With the node 
and edge of a result tuple you can reconstruct the tree, but some of the 
tuples are missing in the driving distance results, result in the fact 
that you reconstruct multiple disconnected trees that COULD be connected 
correctly if the missing tuples were in the result set.

That is as far as I have been able to get. Things to do:

1. add the predecessor changes below to the pg_routing code and see if 
the trigger returning the missing tuples (I suspect it will not).
2. I can modify my test code to look more like the pgrouting code and 
see if I can reproduce the missing tuples (I suspect it will not).

My intuitive GUESS, is that we are loosing the tuples somehow when we 
move them from the C/C++ structures into the set returning mechanism of 
postgresql. I looked at this code but not knowing the nuances of 
programming in the postgresql server environment, I did not see anything 
obvious to me.

So maybe you could look that over when you have a chance.

-Steve

On 6/2/2011 8:43 PM, Anton Patrushev wrote:
> Hi Steve,
>
> Looks OK to me.
> There's nothing wrong with one more int field in path_element structure.
> I don't remember what path_vector is for, most likely it is bad
> copy/paste from somewhere else and not used at all.
>
> Anton.
>
> On 5/17/11, Stephen Woodbridge<woodbri at swoodbridge.com>  wrote:
>> 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
>> _______________________________________________
>> pgrouting-dev mailing list
>> pgrouting-dev at lists.osgeo.org
>> http://lists.osgeo.org/mailman/listinfo/pgrouting-dev
>>
>
>