[pgrouting-dev] Finally getting back to integrating your TRSP improvements

[Helder Alves]

Hi Steve and all!

Do you have any advance on this matter? :-)

Thanks!

--
Helder Alves
On Apr 14, 2014 4:05 PM, "Stephen Woodbridge" <woodbri at swoodbridge.com>
wrote:

> On 4/13/2014 3:08 PM, Ashraf Hossain wrote:
>
>> Dear Steve,
>> I am out of town in village, I will come back to you soon with my
>> thoughts.
>>
>
> Hi Roni,
>
> No problem, enjoy your time being mostly disconnected from the net :)
>
> 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:
>
> vector<int> GraphDefinition::makeVirtualNodes(vector<int> edge_ids,
> vector<double> edge_parts);
>
> 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.
>
> And it would be easy to change or clone multi_dijkstra to add options for
> one_to_many and many_to_many loops.
>
> 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.
>
> Any thoughts on this when you have a chance to look over the code.
>
> 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.
>
> 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
>
> pgr_dijkstra()            - pgr_trsp() point_to_point
> pgr_kdijkstra()           - pgr_trsp() one_to_many
> pgr_makeDistanceMatrix()  - pgr_trsp() many_to_many
>
> We would be able to support turn restrictions or not with all these
> functions.
>
> 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).
>
> Hope this all makes some sense.
>
> Thanks,
>   -Steve
>
>  Regards
>> Roni
>>
>>
>> On Sun, Apr 13, 2014 at 6:28 AM, Stephen Woodbridge
>> <woodbri at swoodbridge.com <mailto:woodbri at swoodbridge.com>> wrote:
>>
>>     Hi Roni,
>>
>>     I hope you and your family are doing well.
>>     I am well but have been very busy. I'm between some contracts at the
>>     moment and I am looking at the TRSP improvements you did quite a
>>     ways back to add the reverse cost and routing from nodes A-B-C-...
>>
>>     Looking at multi_dijkstra it seems that I should be able to mimic
>>     that code based on how you clean up after each route A-B to restart
>>     for B-C and create a similar function that computes one to many
>>     destinations, A-B, A-C, A-D, etc.
>>
>>     What do you think?
>>
>>     So for integrating this code, I probably need to implement a family
>>     of additional functions like:
>>
>>
>>     Existing functions:
>>
>>     pgr_trsp(text, integer, integer, boolean, boolean)
>>     -- node to node
>>
>>     pgr_trsp(text, integer, integer, boolean, boolean, text)
>>     -- node to node with restrictions
>>
>>     pgr_trsp(text, integer, double precision, integer, double precision,
>>     boolean, boolean)
>>     -- edge to edge
>>
>>     pgr_trsp(text, integer, double precision, integer, double precision,
>>     boolean, boolean, text)
>>     -- edge to edge with restrictions
>>
>>     pgr_trsp(text, integer[], boolean, boolean, text)
>>     -- array of nodes **this gets changed to use new code (1)**
>>
>>     pgr_trsp(text, integer[], float8[], boolean, boolean, text)
>>     -- array of edges **this gets changed to use new code (2)**
>>
>>     (1) should plug directly into your code. I currently do this in C by
>>     calling your old code multiple times, but it will be more efficient
>>     to change this to call multi_dijkstra because we only build the
>>     graph once.
>>
>>     (2) I currently do this in C by making multiple calls to your old
>>     code. The multi_dijkstra only accepts nodes, not edges, so I'll look
>>     at making a version that can be called by edges. Unless you want to
>>     do that :)
>>
>>     Then I think I would like to add a new argument to (1) and (2) above
>>     "boolean onetomany" and if it is true then we compute A-B, A-C, A-D,
>>     ... and if it is false it will compute A-B-C-...
>>
>>     I'll have to think about how to return the results, but that should
>>     not be too hard.
>>
>>     TODO:
>>
>>     1. create function to support multi_dijkstra with edges
>>     2. create new function onetomany_dijkstra for nodes
>>     3. create new function onetomany_dijkstra for edges
>>     4. update C code wrappers to support the above
>>     5. develop test cases
>>     6. write the documentation
>>     7. check it in
>>
>>     Ok that is a bunch of work! Maybe I'll start with just getting (1)
>>     done so it calls your new code, and write a test case for that. Then
>>     tackle the rest.
>>
>>     Thoughts?
>>
>>     -Steve
>>
>>
>>
> _______________________________________________
> pgrouting-dev mailing list
> pgrouting-dev at lists.osgeo.org
> http://lists.osgeo.org/mailman/listinfo/pgrouting-dev
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.osgeo.org/pipermail/pgrouting-dev/attachments/20140505/0e9cd0ae/attachment.html>