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

[Helder Alves]

Hi Steve,

Please consider this opportunity to consolidate current Dijkstra functions.

As you know, there are side situations where Dijkstra and KDijkstra are
producing different results when that shouldn't happen.

Maybe it's time to merge everything into the same code base to be make it
easier to tackle bugs and future improvements. :-)

I can help with testing, if you want!

Thanks to all community!

--
Helder Alves
On Apr 13, 2014 2:41 PM, "Stephen Woodbridge" <woodbri at swoodbridge.com>
wrote:

> So a couple of more thoughts on refactoring TRSP. I think we can get away
> with having just two C wrapper functions:
>
> 1) to handle node input
> 2) to handle edge input
>
> I think everything else can be handled as options in the plpgsql wrappers
> like:
>
> a) input is always an array of nodes or edges
>    we can take two node arguments and create an array in psql wrapper
>    likewise for the start and end edge function
>
> b) we can add an argument mode=n, where
>    0 - point to point
>    1 - one to many
>    2 - many to many
>
> c) it might be useful to have an option costonly if you only want the cost
> and not all the edge info
>
> d) restrictions are optional and can be passed as null if none
>
> The only issue with this is that we currently return different result
> types if we are returning a single route versus returning multiple routes
> in the result. I think we can deal with this by always returning the
> multiple results structure from the C code and filtering the column out in
> the plpgsql wrapper function to support the existing functions
>
> My goal is to minimize code duplication and to simplify the lower level
> code for consistency, supportability, and testing. Long term we might
> deprecate some of the plpgsql wrapper functions to simplify the
> documentation and to make it easier to work with.
>
> Thoughts and input are welcome. I'm still in the planning stage for this
> but will short start coding something ;)
>
> Thanks,
>   -Steve
>
> On 4/12/2014 8:28 PM, Stephen Woodbridge 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
>>
>
> _______________________________________________
> 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/20140413/47ac787b/attachment.html>