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

[Ko Nagase]

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



-- 
Ko Nagase (長瀬　興)
Georepublic Japan
mail: nagase at georepublic.co.jp
web: http://georepublic.co.jp