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

[Mukul priya]

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
>>
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.osgeo.org/pipermail/pgrouting-dev/attachments/20151223/3ff77c26/attachment.html>