<p dir="ltr">Hi Steve and all! </p>
<p dir="ltr">Do you have any advance on this matter? :-) </p>
<p dir="ltr">Thanks! </p>
<p dir="ltr">--<br>
Helder Alves</p>
<div class="gmail_quote">On Apr 14, 2014 4:05 PM, "Stephen Woodbridge" <<a href="mailto:woodbri@swoodbridge.com">woodbri@swoodbridge.com</a>> wrote:<br type="attribution"><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
On 4/13/2014 3:08 PM, Ashraf Hossain wrote:<br>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
Dear Steve,<br>
I am out of town in village, I will come back to you soon with my thoughts.<br>
</blockquote>
<br>
Hi Roni,<br>
<br>
No problem, enjoy your time being mostly disconnected from the net :)<br>
<br>
Looking at GraphDefinition.cpp, I'm thinking that a small refactoring might make it easier to deal with multi_dijkstra using edges versus nodes. Something along the lines of:<br>
<br>
vector<int> GraphDefinition::<u></u>makeVirtualNodes(vector<int> edge_ids, vector<double> edge_parts);<br>
<br>
This could take a list of edges and position on the edges and create a vector of virtual nodes and add then to the graph and return vector of the new virtual node ids. Then in multi_dijkstra you can loop through these as the start and end nodes. If we only have one start and end then the existing code could be change to work with this vector.<br>
<br>
And it would be easy to change or clone multi_dijkstra to add options for one_to_many and many_to_many loops.<br>
<br>
We could also eliminate the existing edge to edge version of my_dijkstra or trivialize it to call multi_dijkstra where we pass it just a vector of the start and end points. This would remove redundant code and simplify testing and verification of the existing code.<br>
<br>
Any thoughts on this when you have a chance to look over the code.<br>
<br>
I'm not sure what the best way to do this in GraphDefinition. It looks like we have a few places where we check if(is<Start|End>Virtual) when evaluating restrictions because this gets a little trickier. If the node is a via point in the middle of a restriction, then we will continue on that edge as if there is no virtual node there, but if it is the first or last point in overall route we will treat it like the start or end case as we do now. In the case of one_to_many and many_to_many, the start and end points would get treated as they are now also.<br>
<br>
I'm thinking that with these changes, we could potentially also replace pgr_dijkstra and pgr_kdijkstra with the trsp code so we have one common code base for<br>
<br>
pgr_dijkstra() - pgr_trsp() point_to_point<br>
pgr_kdijkstra() - pgr_trsp() one_to_many<br>
pgr_makeDistanceMatrix() - pgr_trsp() many_to_many<br>
<br>
We would be able to support turn restrictions or not with all these functions.<br>
<br>
One question I have about trsp is when I do a dijkstra solution in Boost, I solve the whole graph so in the kdijkstra case (one_to_many) I make one solution of the graph and I can extract paths to the "many" end nodes in the graph rather than doing multiple solves like A-B, A-C, A-D, ...? Can we do the same (extract multiple end points) in trsp? If so then many_to_many becomes (N * one_to_many).<br>
<br>
Hope this all makes some sense.<br>
<br>
Thanks,<br>
-Steve<br>
<br>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
Regards<br>
Roni<br>
<br>
<br>
On Sun, Apr 13, 2014 at 6:28 AM, Stephen Woodbridge<br>
<<a href="mailto:woodbri@swoodbridge.com" target="_blank">woodbri@swoodbridge.com</a> <mailto:<a href="mailto:woodbri@swoodbridge.com" target="_blank">woodbri@swoodbridge.<u></u>com</a>>> wrote:<br>
<br>
Hi Roni,<br>
<br>
I hope you and your family are doing well.<br>
I am well but have been very busy. I'm between some contracts at the<br>
moment and I am looking at the TRSP improvements you did quite a<br>
ways back to add the reverse cost and routing from nodes A-B-C-...<br>
<br>
Looking at multi_dijkstra it seems that I should be able to mimic<br>
that code based on how you clean up after each route A-B to restart<br>
for B-C and create a similar function that computes one to many<br>
destinations, A-B, A-C, A-D, etc.<br>
<br>
What do you think?<br>
<br>
So for integrating this code, I probably need to implement a family<br>
of additional functions like:<br>
<br>
<br>
Existing functions:<br>
<br>
pgr_trsp(text, integer, integer, boolean, boolean)<br>
-- node to node<br>
<br>
pgr_trsp(text, integer, integer, boolean, boolean, text)<br>
-- node to node with restrictions<br>
<br>
pgr_trsp(text, integer, double precision, integer, double precision,<br>
boolean, boolean)<br>
-- edge to edge<br>
<br>
pgr_trsp(text, integer, double precision, integer, double precision,<br>
boolean, boolean, text)<br>
-- edge to edge with restrictions<br>
<br>
pgr_trsp(text, integer[], boolean, boolean, text)<br>
-- array of nodes **this gets changed to use new code (1)**<br>
<br>
pgr_trsp(text, integer[], float8[], boolean, boolean, text)<br>
-- array of edges **this gets changed to use new code (2)**<br>
<br>
(1) should plug directly into your code. I currently do this in C by<br>
calling your old code multiple times, but it will be more efficient<br>
to change this to call multi_dijkstra because we only build the<br>
graph once.<br>
<br>
(2) I currently do this in C by making multiple calls to your old<br>
code. The multi_dijkstra only accepts nodes, not edges, so I'll look<br>
at making a version that can be called by edges. Unless you want to<br>
do that :)<br>
<br>
Then I think I would like to add a new argument to (1) and (2) above<br>
"boolean onetomany" and if it is true then we compute A-B, A-C, A-D,<br>
... and if it is false it will compute A-B-C-...<br>
<br>
I'll have to think about how to return the results, but that should<br>
not be too hard.<br>
<br>
TODO:<br>
<br>
1. create function to support multi_dijkstra with edges<br>
2. create new function onetomany_dijkstra for nodes<br>
3. create new function onetomany_dijkstra for edges<br>
4. update C code wrappers to support the above<br>
5. develop test cases<br>
6. write the documentation<br>
7. check it in<br>
<br>
Ok that is a bunch of work! Maybe I'll start with just getting (1)<br>
done so it calls your new code, and write a test case for that. Then<br>
tackle the rest.<br>
<br>
Thoughts?<br>
<br>
-Steve<br>
<br>
<br>
</blockquote>
<br>
______________________________<u></u>_________________<br>
pgrouting-dev mailing list<br>
<a href="mailto:pgrouting-dev@lists.osgeo.org" target="_blank">pgrouting-dev@lists.osgeo.org</a><br>
<a href="http://lists.osgeo.org/mailman/listinfo/pgrouting-dev" target="_blank">http://lists.osgeo.org/<u></u>mailman/listinfo/pgrouting-dev</a><br>
</blockquote></div>