<div dir="ltr"><div><div>Hi , <br></div>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.<br></div><div>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 . <br></div><div>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 . <br><br></div><div>Thanks<br></div><div>Mukul<br></div></div><div class="gmail_extra"><br><div class="gmail_quote">On Wed, Dec 23, 2015 at 9:29 PM, Ko Nagase <span dir="ltr"><<a href="mailto:nagase@georepublic.co.jp" target="_blank">nagase@georepublic.co.jp</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">Hi Stephen,<br>
<br>
Thanks for details.<br>
<br>
About a huge network, I think that the performance is the highest priority<br>
and dynamic graph (CRUD and dynamic condition) is not so important.<br>
<br>
But, if possible, supporting multiple weights (like bicycle and car<br>
.etc) may be good.<br>
<br>
(In FOSS4G 2015 Seoul, I heard that OSRM requires multiple instances (daemons)<br>
for multiple profiles and it is a bit complex.)<br>
<br>
Anyway, I'm looking forward to it. :-)<br>
<br>
Regards,<br>
<br>
Ko<br>
<div class="HOEnZb"><div class="h5"><br>
<br>
2015-12-23 23:20 GMT+09:00 Stephen Woodbridge <<a href="mailto:woodbri@swoodbridge.com">woodbri@swoodbridge.com</a>>:<br>
> I believe that is correct, but I have not seem the actual code Mukul and<br>
> Rohit are developing. I'm also not sure how the precomputed graph is getting<br>
> stored/retrieved which will directly impact the compute time.<br>
><br>
> In pgRouting today, I think we spend our compute time roughly like:<br>
><br>
> 1/3 - fetching edges<br>
> 1/3 - building the graph<br>
> 1/3 - computing results<br>
><br>
> Depending on the exact implementation this should eliminate much building<br>
> the graph and computing results. And instead of fetching edges we would be<br>
> fetching the contracted graph.<br>
><br>
> Also, this technique trades off dynamic graph definition for performance<br>
> because you have to precompute the contracted graph which is time consuming<br>
> and only has value if you want to build once and solve many times. If you<br>
> want to change the weights or add or remove edges, then you have to<br>
> precompute the contracted graph again.<br>
><br>
> Regardless of the details, this will be a very nice addition to pgRouting.<br>
><br>
> -Steve<br>
><br>
><br>
> On 12/23/2015 8:36 AM, Ko Nagase wrote:<br>
>><br>
>> Hi Stephen, Mukul,<br>
>><br>
>> Thanks for good news!<br>
>><br>
>> Does "contraction hierarchies" mean the following technique ?<br>
>> ===<br>
>> [Contraction hierarchies - Wikipedia, the free encyclopedia]<br>
>> <a href="https://en.wikipedia.org/wiki/Contraction_hierarchies" rel="noreferrer" target="_blank">https://en.wikipedia.org/wiki/Contraction_hierarchies</a><br>
>> ===<br>
>><br>
>> It seems to be used in OSRM/OpenTripPlanner/GraphHopper from the<br>
>> site's  "References" section,<br>
>> so I think that it will be a quite nice improvement for pgRouting.<br>
>><br>
>> Regards,<br>
>><br>
>> Ko<br>
>><br>
>> 2015-12-23 0:00 GMT+09:00 Stephen Woodbridge <<a href="mailto:woodbri@swoodbridge.com">woodbri@swoodbridge.com</a>>:<br>
>>><br>
>>> Hi All,<br>
>>><br>
>>> I got a chat from Mukul who was a past GSoC student and he says:<br>
>>><br>
>>> "I have been working on a contraction based approach for path computation<br>
>>> where we are trying to observe the trade off between different level of<br>
>>> network contraction and final unpacking of the path computed on these<br>
>>> contracted networks. I have been doing this in my free time for now with<br>
>>> one<br>
>>> of my junior, Rohit Reddy. The contraction does make the path computation<br>
>>> faster and we have implemented all these functionality (precomputation<br>
>>> and<br>
>>> routing) as database procedure which can be integrated very easily in<br>
>>> pgrouting . As soon as we are ready with  a tried and tested procedure ,<br>
>>> i<br>
>>> will let you know . You can review it then."<br>
>>><br>
>>> They think they might have something to review in a few weeks that we can<br>
>>> take a look at.<br>
>>><br>
>>> This is a very exciting and surprising development!<br>
>>><br>
>>> -Steve<br>
>>><br>
>>> ---<br>
>>> This email has been checked for viruses by Avast antivirus software.<br>
>>> <a href="https://www.avast.com/antivirus" rel="noreferrer" target="_blank">https://www.avast.com/antivirus</a><br>
>>><br>
>>> _______________________________________________<br>
>>> pgrouting-dev mailing list<br>
>>> <a href="mailto:pgrouting-dev@lists.osgeo.org">pgrouting-dev@lists.osgeo.org</a><br>
>>> <a href="http://lists.osgeo.org/mailman/listinfo/pgrouting-dev" rel="noreferrer" target="_blank">http://lists.osgeo.org/mailman/listinfo/pgrouting-dev</a><br>
>><br>
>><br>
>><br>
>><br>
><br>
><br>
> ---<br>
> This email has been checked for viruses by Avast antivirus software.<br>
> <a href="https://www.avast.com/antivirus" rel="noreferrer" target="_blank">https://www.avast.com/antivirus</a><br>
><br>
> _______________________________________________<br>
> pgrouting-dev mailing list<br>
> <a href="mailto:pgrouting-dev@lists.osgeo.org">pgrouting-dev@lists.osgeo.org</a><br>
> <a href="http://lists.osgeo.org/mailman/listinfo/pgrouting-dev" rel="noreferrer" target="_blank">http://lists.osgeo.org/mailman/listinfo/pgrouting-dev</a><br>
<br>
<br>
<br>
</div></div><span class="im HOEnZb">--<br>
Ko Nagase (長瀬　興)<br>
Georepublic Japan<br>
mail: <a href="mailto:nagase@georepublic.co.jp">nagase@georepublic.co.jp</a><br>
web: <a href="http://georepublic.co.jp" rel="noreferrer" target="_blank">http://georepublic.co.jp</a><br>
</span><div class="HOEnZb"><div class="h5">_______________________________________________<br>
pgrouting-dev mailing list<br>
<a href="mailto:pgrouting-dev@lists.osgeo.org">pgrouting-dev@lists.osgeo.org</a><br>
<a href="http://lists.osgeo.org/mailman/listinfo/pgrouting-dev" rel="noreferrer" target="_blank">http://lists.osgeo.org/mailman/listinfo/pgrouting-dev</a></div></div></blockquote></div><br></div>