Hi Jay,<br><br><div class="gmail_quote"><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex;"><b>Source Code </b>(Quote from their web-page)<br><i>The source code of our implementation of contraction hierarchies (CHs)
is now available under the terms of the AGPL. If you are interested in
getting the source code write an email to <a href="http://algo2.iti.kit.edu/english/geisberger.php" target="_blank">Robert Geisberger</a>.<br></i></blockquote><div><br></div><div>I think I saw it already once somewhere, but couldn't find it now anymore.</div>
<div>Instead I found these two pages:</div><div><ul><li><meta http-equiv="content-type" content="text/html; charset=utf-8"><a href="http://en.wikipedia.org/wiki/Contraction_hierarchies">http://en.wikipedia.org/wiki/Contraction_hierarchies</a> ... so it seems OpenTripPlanner uses CH:<br>
<meta http-equiv="content-type" content="text/html; charset=utf-8"><a href="http://opentripplanner.org/browser/trunk/opentripplanner-routing/src/main/java/org/opentripplanner/routing/contraction">http://opentripplanner.org/browser/trunk/opentripplanner-routing/src/main/java/org/opentripplanner/routing/contraction</a></li>
<li><meta http-equiv="content-type" content="text/html; charset=utf-8"><a href="http://cloudmade.com/about/open-source">http://cloudmade.com/about/open-source</a> ... Cloudmade uses CH</li></ul><div>But I think it would fine to just ask Robert Geisberger for the source code.</div>
</div><div> </div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex;"><i></i><br>They have also come up with another paper in 2010: "<a href="http://algo2.iti.kit.edu/english/1695.php" target="_blank">A comparison for high-level approaches for speed-up in path finding algorithms</a>" but the full-text does not seem to be available. (I think this might be useful too)<br>
<br>The GSoc page lists Network Layering (Contraction Hierarchies) and Highway Hierarchies as two separate problems. But Contraction Hierarchies technique seems to outperform HH in almost all categories, and comparatively its less complex.<br>
</blockquote><div><br></div><div>Needs to be updated for 2011. It was just a collection of ideas, but not a requirement for students to follow.</div><div><br></div><div>Daniel</div><div><br></div><div><br></div><div> </div>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex;">
<br>I think it will require a lot of brain-storming before we can narrow down any particular technique to implement, and also analyse the feasibility / difficulty of implementation of the same. Hoping to hear all your opinions on this.<br>
<b><br>PS:</b><br>I have started work on my Masters thesis, and I plan to explore this area further and maybe extend the work. (I need to do 8+16+16 thesis credits over the course of this semester and next 2 semesters, 4 credits is eq to 1 subject). A GSoc project in summer would be an added incentive! <br>
<div><div></div><div class="h5">
<br><br><div class="gmail_quote">On Fri, Jan 28, 2011 at 11:45 PM, Stephen Woodbridge <span dir="ltr"><<a href="mailto:woodbri@swoodbridge.com" target="_blank">woodbri@swoodbridge.com</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0pt 0pt 0pt 0.8ex;border-left:1px solid rgb(204, 204, 204);padding-left:1ex">
Hi Jay,<br>
<br>
If you are up for tackling another algorithm, I think this is the one that has really high value for pgRouting:<br>
<br>
<a href="http://algo2.iti.kit.edu/english/routeplanning.php" target="_blank">http://algo2.iti.kit.edu/english/routeplanning.php</a><br>
<br>
The contraction highways routing is awesome stuff. There is a lot of pre-analysis of the network which takes a lot of compute time, but once that is done and stored, the resulting structures let you compute routes of continental distances in milliseconds.<br>
<br>
This should be a very high priority for us as it is already in at least two separate tools that work with OSM data. The value add for pgRouting is that we could then use this algorithm for any datasets that meet the minimum requirements for contraction highways.<br>
<br>
Daniel, Anton, do you agree that this is a priority?<br>
<br>
I hope you will give this one serious consideration.<br>
<br>
Best regards,<br>
-Steve<div><br>
<br>
On 1/28/2011 8:22 AM, Jay Mahadeokar wrote:<br>
</div><blockquote class="gmail_quote" style="margin:0pt 0pt 0pt 0.8ex;border-left:1px solid rgb(204, 204, 204);padding-left:1ex"><div>
Hi all,<br>
<br>
Excuse me for bringing up an old topic again! Quoting the idea posted in<br>
GSoc 2010 ideas page:<br>
<br>
/Network Layering Support:<br>
This idea is a quite a challenging task. Network layering would allow<br>
the routing algorithm to change from more to less dense networks to<br>
enable long-distance routing.<br>
/<br>
Has this idea still got priority? If yes, I would like to have more info<br>
on the same.<br>
<br>
<br>
On Sat, Oct 16, 2010 at 10:48 AM, Jay Mahadeokar<br></div><div><div></div><div>
<<a href="mailto:jai.mahadeokar@gmail.com" target="_blank">jai.mahadeokar@gmail.com</a> <mailto:<a href="mailto:jai.mahadeokar@gmail.com" target="_blank">jai.mahadeokar@gmail.com</a>>> wrote:<br>
<br>
Hi.<br>
<br>
I am currently doing MTech in Computer Science and Engineering from<br>
Indian Institute of Technology Kanpur, India. I have used pgRouting<br>
while working with postGreSQL in past. I have special interest in<br>
routing algorithms and would like to contribute in some way.<br>
<br>
I was looking at the ideas posted here:<br>
<a href="http://wiki.osgeo.org/wiki/OpenRouter_2010_SOC_Ideas" target="_blank">http://wiki.osgeo.org/wiki/OpenRouter_2010_SOC_Ideas</a> which mentions<br>
that a network layering support is desirable which would allow the<br>
routing algorithm to change from more to less dense networks to<br>
enable long-distance routing. I have worked with sparse spanner<br>
algorithms, and was wondering if it can be applied here. A 3 spanner<br>
algorithm can allow you to get a sparse graph containing O(n^3/2)<br>
edges from dense graph containing O(n^2) edges, using linear time -<br>
O(m) - m s the number of edges.<br>
<br>
It would be great if I could know more details about the<br>
requirement. Example - while constructing spanner for road network,<br>
do we want to consider the type of roads and give them priorities<br>
accordingly?<br>
<br>
PS - I am complete newbie when it comes to contribution to<br>
opensource projects of such scale. Please excuse me for asking wrong<br>
questions. I would also like to work on other ideas which may be in<br>
your TODO list. I would be great if you can direct me to some links<br>
which may help to get started properly.<br>
<br>
<br>
--<br>
Regards,<br>
-Jay Mahadeokar<br>
<br>
<br>
<br>
<br>
--<br>
Regards,<br>
-Jay Mahadeokar<br>
<br>
<br>
<br></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" target="_blank">http://lists.osgeo.org/mailman/listinfo/pgrouting-dev</a><br>
</blockquote>
<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" target="_blank">http://lists.osgeo.org/mailman/listinfo/pgrouting-dev</a><br>
</blockquote></div><br><br clear="all"><br></div></div>-- <br>Regards,<br><font color="#888888">-Jay Mahadeokar<br><br>
</font><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" target="_blank">http://lists.osgeo.org/mailman/listinfo/pgrouting-dev</a><br>
<br></blockquote></div><br><br clear="all"><br>-- <br><span style="font-family:arial, sans-serif;font-size:13px;border-collapse:collapse">Georepublic UG & Georepublic Japan<br>eMail: <a href="mailto:daniel.kastl@georepublic.de" style="color:rgb(66, 99, 171)" target="_blank">daniel.kastl@georepublic.de</a><br>
Web: <a href="http://georepublic.de/" style="color:rgb(66, 99, 171)" target="_blank">http://georepublic.de</a></span><br>