[pgrouting-dev] Non-scheduled Routing algorithm

[Stephen Woodbridge]

On 6/13/2011 1:28 PM, Kishore Kumar wrote:
> Hi,
>
> I am facing the following issues in the prototype code[1]:
>
> 1. As I am internally calling Dijkstra function and the Dijkstra
> implementation assumes that vertex id and edge id are integers but
> according to GTFS, stop id and route id can be text also. This can be
> solved by:
>   a. Generating a new table that maps Auto-generated integers to Stop
> Ids(Map<Integer,Text>)
>   b. Modifying Dijkstra implementation to accept vertex id of type text

I think I would do a. above. The reason is text id's are really for 
people and and integer id's computers like. And it is likely that doing 
b., you would need to remap the text labels to integer anyway for 
performance reasons.

> 2. Since the non-scheduling algorithm is not directly doing any lower
> level calculations, I implemented the prototype using PL/pgSQL
> language. Is rewriting the same logic in c is required and does it
> provide any significant performance boost? According to a post in
> pgsql-performance list[2], "I wouldn't expect the queries called by
> the pl/pgsql function to be much faster if called through SPI from C
> instead.". Hence, my current thought is to give real-life data as
> input and check for performance problems and if performance is bad,
> write the code in c.

I do not have direct test experience to back this up, but assuming pgsql 
as a language is implemented similar to Perl or python the standard is 
to compile the source to bytecode and then run a bytecode interpreter. 
This gives very good perfomance when 90% of the time is spend in library 
functions that really are compiled C/C++ and called from the 
interpreter. Where you start to run into performance problems is when 
you have a lot of code or a lot of looping and evaluating expressions. 
That said, the rule for optimizing code is to measure first and then 
remove the worse bottle neck, and then repeat until you are happy with 
the results. So I see no problem with a prototype in pgsql, and later it 
or part of it can be rewritten to C if there are performance issues.

Hope this helps,
   -Steve

> Thanks&  Regards,
> J Kishore kumar.
>
> [1] - https://github.com/pgRouting/pgrouting/blob/gsoc-multimodal/extra/transit/sql/nonscheduled.sql
> [2] - http://archives.postgresql.org/pgsql-performance/2010-05/msg00199.php
>
> On Sun, Jun 12, 2011 at 1:30 PM, Anton Patrushev
> <anton.patrushev at georepublic.de>  wrote:
>> Hi Kishore,
>>
>> Ah, now I got it. Well, here in Russia some bus routes also don't have
>> fixed schedule and are regulated by number of buses/trips. Thus I
>> think the idea makes sense.
>>
>> Anton.
>> _______________________________________________
>> 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