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

[Stephen Woodbridge]

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
>
>