<div dir="ltr"><div>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. <br><br></div>-mukul<br></div><div class="gmail_extra"><br><div class="gmail_quote">On Wed, Dec 23, 2015 at 10:43 PM, Mukul priya <span dir="ltr"><<a href="mailto:mukul2047@gmail.com" target="_blank">mukul2047@gmail.com</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><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<span class="HOEnZb"><font color="#888888"><br></font></span></div><span class="HOEnZb"><font color="#888888"><div>Mukul<br></div></font></span></div><div class="HOEnZb"><div class="h5"><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><div><br>
<br>
2015-12-23 23:20 GMT+09:00 Stephen Woodbridge <<a href="mailto:woodbri@swoodbridge.com" target="_blank">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" target="_blank">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" target="_blank">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" target="_blank">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>--<br>
Ko Nagase (長瀬　興)<br>
Georepublic Japan<br>
mail: <a href="mailto:nagase@georepublic.co.jp" target="_blank">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><div>_______________________________________________<br>
pgrouting-dev mailing list<br>
<a href="mailto:pgrouting-dev@lists.osgeo.org" target="_blank">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>
</div></div></blockquote></div><br></div>