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

[Stephen Woodbridge]

Hi Ko,

We will have to see the details in a few weeks as I have no more 
information that what Mukul chatted and the rest is speculation on my 
part. If the contracted graph is stored in a table or even a named file, 
then it should be possible to store multiple profiles and then select 
which profile to use in a specific query.

I would think that even if it is not implemented like that on the 
initial preview that we should be able to grow it to support something 
like that.

-Steve

On 12/23/2015 10:59 AM, Ko Nagase wrote:
> Hi Stephen,
>
> Thanks for details.
>
> About a huge network, I think that the performance is the highest priority
> and dynamic graph (CRUD and dynamic condition) is not so important.
>
> But, if possible, supporting multiple weights (like bicycle and car
> .etc) may be good.
>
> (In FOSS4G 2015 Seoul, I heard that OSRM requires multiple instances (daemons)
> for multiple profiles and it is a bit complex.)
>
> Anyway, I'm looking forward to it. :-)
>
> Regards,
>
> Ko
>
>
> 2015-12-23 23:20 GMT+09:00 Stephen Woodbridge <woodbri at swoodbridge.com>:
>> 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
>>
>> _______________________________________________
>> 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