[pgrouting-users] TRSP - Bug with rules referring to the starting edge.

[Stephen Woodbridge]

Hi Fabien,

I have some other changes and fixes from Ashraf for TRSP in a zip file. 
But I do not think they cover all the issues you mention below. I have 
been buried in work lately. If you would like to work on this I can 
forward the zipfile to you if you want to merge it and fix some of these 
other issues.

Ideally you would make a branch off of develop and integrate it into 
that then make a pull request.

Let me know and I will forward the zip file.

Thanks you for the offer to help,
    -Steve

 From Ashraf's email on his fixes:

> I have made some improvement over the trsp source code.
>
> 1) The first thing is now it should response properly for different values of directed and has_reverse_cost parameters. Please note that if directed is true and has_reverse_cost is false then it will only use the given cost in single direction. On the other hand if directed is false and has_reverse_cost is false then it is assumed that the same weight applies in the opposite direction.
>
> 2) A new method is added to route over multiple via point named multi_dijkstra(). Here is the signature:
>
> int multi_dijkstra(edge_t *edges, unsigned int edge_count, vector<int> vertices, bool directed, bool has_reverse_cost,
>             path_element_t **path, int *path_count, char **err_msg, std::vector<PDVI> &ruleList);
>
> The vector<int> contains the via points. This calculates routes from vertices[0] to vertices[1], then vertices[1] to vertices[2] then vertices[2] to vertices[3] and so on.
> The result is accumulated in path which is like for a sample case of vertices = {5700, 6733, 6585, 8247}
>
> 5700    |20787    |0.006774
> 10932  |20756    |0.040876
> .....
> 9313    |15058    |0.044674
> 6733    |-1          |0.000000
> 6733    |15058    |0.044674
> 9313    |15059    |0.047811
> .....
> 6584    |8029      |0.119086
> 6585    |-1          |0.000000
> 6585    |17975    |0.200230
> .....
> 10705  |20185    |0.055053
> 8247    |-1          |0.000000
>
> Please note the -1 in the middle. I intentionally kept it to indicate that it is a via point. It can be removed if required. One can pass empty vector if there is no restriction.
> Please let me know if there is an query.
>
> The affected files are GraphDefinition.cpp, GraphDEfinition.h and trsp_core.cpp. I have attached the files. I have checked with windows but could not check it with linux.
> Please have a look.


On 2/26/2014 10:42 AM, Fabien Ancelin wrote:
> Hello all,
>
> There is I suspect another bug in TRSP algorithm that occurs in the file
> GraphDefinition.cpp, at line 299.
>
> The issue appears when the start location for routing passed from
> PostgreSQL is a position on a segment, and this position is different
> from 0 or 1 (For example Edge 200, Position 0.5). In that case, the
> starting edge gets split. Because of that all the elements in the rule
> table referencing to the starting segment need to be updated.
>
> There are several things that caught my attention :
>
>   * The code in order to update the rule and replace the reference to
>     the starting segment is activated only if there 1 one segment in the
>     precedence list (line 299). The rule could very well have a
>     reference to the starting segment and a precedence list with more
>     than 1 element.
>   * The logic to update the rule assumes that the starting segment will
>     always be the last element in the precedence list. That is not a
>     right assumption.
>   * Even when we do attempt to update the rule, the code logic seems
>     puzzling (line 301). The reference to the starting segment is
>     removed, and we insert the edges created from the split into the
>     precedence list, without checking the connection with the previous
>     segment in the precedent list.
>
> Is that issues that you are aware of or planning to fix? Would you need
> help to fix those bugs?
>
> Regards,
>
>
> _______________________________________________
> Pgrouting-users mailing list
> Pgrouting-users at lists.osgeo.org
> http://lists.osgeo.org/mailman/listinfo/pgrouting-users
>