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@lists.osgeo.org
http://lists.osgeo.org/mailman/listinfo/pgrouting-users