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

[Mukul priya]

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/a78b450f/attachment-0001.html>