[pgrouting-dev] cloning boost_drivedist.cpp to return predecessors
Stephen Woodbridge
woodbri at swoodbridge.com
Thu Jun 2 21:07:41 EDT 2011
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
>>
>
>
More information about the pgrouting-dev
mailing list