[pgrouting-dev] Contraction hierarchies might be coming to a pgrouting near you

[Stephen Woodbridge]

I believe that is correct, but I have not seem the actual code Mukul and 
Rohit are developing. I'm also not sure how the precomputed graph is 
getting stored/retrieved which will directly impact the compute time.

In pgRouting today, I think we spend our compute time roughly like:

1/3 - fetching edges
1/3 - building the graph
1/3 - computing results

Depending on the exact implementation this should eliminate much 
building the graph and computing results. And instead of fetching edges 
we would be fetching the contracted graph.

Also, this technique trades off dynamic graph definition for performance 
because you have to precompute the contracted graph which is time 
consuming and only has value if you want to build once and solve many 
times. If you want to change the weights or add or remove edges, then 
you have to precompute the contracted graph again.

Regardless of the details, this will be a very nice addition to pgRouting.

-Steve

On 12/23/2015 8:36 AM, Ko Nagase wrote:
> Hi Stephen, Mukul,
>
> Thanks for good news!
>
> Does "contraction hierarchies" mean the following technique ?
> ===
> [Contraction hierarchies - Wikipedia, the free encyclopedia]
> https://en.wikipedia.org/wiki/Contraction_hierarchies
> ===
>
> It seems to be used in OSRM/OpenTripPlanner/GraphHopper from the
> site's  "References" section,
> so I think that it will be a quite nice improvement for pgRouting.
>
> Regards,
>
> Ko
>
> 2015-12-23 0:00 GMT+09:00 Stephen Woodbridge <woodbri at swoodbridge.com>:
>> Hi All,
>>
>> I got a chat from Mukul who was a past GSoC student and he says:
>>
>> "I have been working on a contraction based approach for path computation
>> where we are trying to observe the trade off between different level of
>> network contraction and final unpacking of the path computed on these
>> contracted networks. I have been doing this in my free time for now with one
>> of my junior, Rohit Reddy. The contraction does make the path computation
>> faster and we have implemented all these functionality (precomputation and
>> routing) as database procedure which can be integrated very easily in
>> pgrouting . As soon as we are ready with  a tried and tested procedure , i
>> will let you know . You can review it then."
>>
>> They think they might have something to review in a few weeks that we can
>> take a look at.
>>
>> This is a very exciting and surprising development!
>>
>> -Steve
>>
>> ---
>> This email has been checked for viruses by Avast antivirus software.
>> https://www.avast.com/antivirus
>>
>> _______________________________________________
>> pgrouting-dev mailing list
>> pgrouting-dev at lists.osgeo.org
>> http://lists.osgeo.org/mailman/listinfo/pgrouting-dev
>
>
>


---
This email has been checked for viruses by Avast antivirus software.
https://www.avast.com/antivirus