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

Fri Dec 25 18:07:07 PST 2015

Hi Mukul, Stephen,

Okay, thanks for details.
(Sorry for late reply.)

I will check a bit about contracted graph in this winter holidays.

Regards,

Ko

2015-12-24 2:37 GMT+09:00 Mukul priya <mukul2047 at gmail.com>:
> Steve is right here  about  the trade off with dynamic nature of the graph .
> It is kind of difficult to update the edge weights in contracted graph. One
> has to do the pre computation once again and generate the contracted
> graph.This technique will be helpful to people who want to run querries on
> the same static network.
>
> -mukul
>
> On Wed, Dec 23, 2015 at 10:43 PM, Mukul priya <mukul2047 at gmail.com> wrote:
>>
>> Hi ,
>> Yes we are basically introducing shortcuts what contraction hierarchy does
>> right now.This pre-computation will be done by a database procedure which
>> will be a user defined function. The amount of shortcuts introduced
>> determines the level of contraction. However there is a trade off between
>> the amount of contraction and the time taken to unpack the path computed on
>> the contracted network.
>> So there will be a precomputaion involved in which we will populate a
>> table containing the contracted network, this table with the contracted
>> graph will be fetched for path computation .
>> The difference between Contraction hierarchy and our approach is that in
>> CH , there is a hierarchy of nodes maintained and there path computation
>> algorithm has an upward Graph and a downward graph and they process the
>> nodes from the both the directions using the hierarchy of the nodes .
>>
>> Thanks
>> Mukul
>>
>> On Wed, Dec 23, 2015 at 9:29 PM, Ko Nagase <nagase at georepublic.co.jp>
>> 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
>>>
>>>
>>>
>>> --
>>> Ko Nagase (長瀬　興)
>>> Georepublic Japan
>>> mail: nagase at georepublic.co.jp
>>> web: http://georepublic.co.jp
>>> _______________________________________________
>>> 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

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