If you guys arrange something to meet up on Skype or a Google hangout to show the ins and outs of the development environment, I would love to attend. I'm still struggling with getting a proper environment set up for development of pgRouting.<div>
<br></div><div>Perhaps others would be interested in this as well?<br><br><div class="gmail_quote">On Mon, Mar 26, 2012 at 9:34 AM, Stephen Woodbridge <span dir="ltr"><<a href="mailto:woodbri@swoodbridge.com">woodbri@swoodbridge.com</a>></span> wrote:<br>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">Hi Jinfu,<br>
<br>
I think the Contraction hierarchies algorithm would be great to have in pgrouting. As Daniel notes one of the advantages of pgrouting is the dynamic nature of configuring the graph before computation, but given the performance boost of this algorithm, there would also be great value in having a solution that is less flexible but 2-3 orders of magnitude faster!<br>
<br>
Learning the postgresql api, development restrictions, and debugging can add significant time to your effort. It would give you a big head start if you were to dive into that before GSoC started to learn a little bit about it. A few suggestions, might be to take an algorithm that you have already written and just try to integrate it into pgrouting. Another would be to take a bug and try to fix it. Either of these efforts would require you to learn the basics about how to setup a development environment, compile pgrouting, debug code in the server and generally familiarize you with the environment that you would be constrained to work in. I would be happy to mentor an effort like this if you have the time and want to learn about pgrouting.<br>
<br>
Regarding contraction hierarchies, the AGPL license is so invasive that probably only Universities and Colleges can use the published code. While it would allow us to figure out the integration issues it is not a practical license for inclusion in pgrouting. This would mean that we would need a new implementation of the algorithm to make it useful to the project.<br>
<br>
Every project has problems and limitations, but I like to think of the possibilities and focus on how to move forward. It is good to be aware of the problems and issues from the outset, because then you have time to work around them or avoid them.<br>
<br>
So if you break this down into tangible tasks that represent potential stopping points you might have something like:<br>
<br>
1. write code to extract data from postgresql, preprocess it, write results back to postgresql<br>
2. write code to process a route request, ie: get data, solve request, return results.<br>
3. rewrite algorithm to be AGPL clean<br>
<br>
Any one of these might be a valid GSoC project, although 2 is rather small following to 1. Item 3 by itself could be a good GSoC project assuming it meets the requirements and this would give you a better understanding of the code and how it works so future integration of it into pgrouting would be easier and might be more dynamic if we understood how to propagate changes through the preprocessed data if that is possible.<br>
<br>
I'm willing to co-mentor any pgrouting GSoC projects.<br>
<br>
Best regards,<br>
-Steve<div class="im"><br>
<br>
On 3/26/2012 2:59 AM, Daniel Kastl wrote:<br>
</div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div class="im">
Hi Jinfu,<br>
<br>
Thank you for posting to the list!<br>
And thank you for your comment, Jay!<br>
<br>
There are already implementations of the contraction hierarchies<br>
algorithm available.<br>
I know about this one for example: <a href="http://project-osrm.org/" target="_blank">http://project-osrm.org/</a><br>
OpenTripPlanner is using it as well:<br>
<a href="https://github.com/openplans/OpenTripPlanner/wiki/" target="_blank">https://github.com/openplans/<u></u>OpenTripPlanner/wiki/</a><br>
<br>
There are two problems I see with this algorithm:<br>
<br></div>
* Can we use an algorithm published under AGPL? Or are only the<div class="im"><br>
existing applications AGPL but not the algorithm.<br></div>
* Contraction Hierarchies does a lot of pre-processing.<div class="im"><br>
pgRouting's strength is, that the network data can be changed easily.<br>
Jinfu, did you already think about details?<br>
<br>
I think an implementation of this algorithm in pgRouting is a very<br>
ambitious GSoC project and should be planned well.<br>
But it would be a great contribution for sure.<br>
<br>
Jinfu, maybe you can look a bit more into details, search for existing<br>
implementations and try to understand how they work.<br>
Have you already used pgRouting and written pl/pgsql functions?<br>
<br>
Daniel<br>
<br>
<br>
On Mon, Mar 26, 2012 at 3:42 PM, Jay Mahadeokar<br></div><div class="im">
<<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.<u></u>com</a>>> wrote:<br>
<br>
Hi Jinfu Leng,<br>
<br>
I did GSoc 2011 with pgRouting. I had looked in detail about this<br>
problem last year too. The highway hierarchies is actually not the<br>
fastest method now. Instead Contraction Hierarchies by Giesberger is<br>
a much better and faster heuristic.<br>
<a href="http://algo2.iti.kit.edu/english/routeplanning.php" target="_blank">http://algo2.iti.kit.edu/<u></u>english/routeplanning.php</a><br>
will give you all the details of latest research in this area. The<br>
source code of Contraction hierarchies is also available for<br>
download, so you could check it out too.<br>
<br>
I would also suggest you look at last years' mailing list<br>
discussions regarding this topic.<br>
<br>
Best of luck!<br>
<br>
On Mon, Mar 26, 2012 at 10:15 AM, Jinfu Leng <<a href="mailto:logicnut@gmail.com" target="_blank">logicnut@gmail.com</a><br></div><div class="im">
<mailto:<a href="mailto:logicnut@gmail.com" target="_blank">logicnut@gmail.com</a>>> wrote:<br>
<br>
Hi all,<br>
<br>
I am interested in applying the GSoC project, and I want to work<br>
on pgRouting. The description of the idea is pasted at the<br>
bottom. I want to get some suggestions from you guys. Any<br>
suggestion is welcome. And if some previous GSoC students can<br>
share your previous applications, that would be great.<br>
<br>
In addition, I am looking for a potential mentor.<br>
<br>
Thanks a lot,<br>
Jinfu<br>
<br></div>
*Title* : Highway Hierarchies Routing Support for pgRouting<br>
<br>
*Describe your idea*<div><div class="h5"><br>
<br>
1. Introduction<br>
<br>
One of the main challenges of routing is the huge size of road<br>
networks. Especially, given source node and sink node in long<br>
distance, shortest path computation will be very time consuming.<br>
I would like to improve current routing algorithm by adding<br>
highway hierarchies routing support.<br>
<br>
2. Background<br>
<br>
Routing is a very common task in GIS, and pgRouting is a famous<br>
routing library which provides routing functions for many GIS<br>
software, such as PostGIS/PostgreSQL. Due to the huge size of<br>
road networks, finding path requires significant computing time,<br>
especially for long distance source and destination. This<br>
results in slow response time and unfriendly user experience.<br>
<br>
3. The idea<br>
<br>
In fact, this algorithm is not my idea. My work will base on the<br>
paper [P. Sanders, D. Schultes]. Basically, this algorithm<br>
includes two steps: construct the highway hierarchies; query on<br>
the highway hierarchies. According to their experiments, this<br>
new approach can be about 2000 times faster than the original<br>
Dijkstra’s algorithm. The tradeoff is spending a few hours for<br>
generating highway hierarchies. I want to implement this<br>
algorithm in pgRouting library.<br>
<br>
4. Project plan<br>
<br>
5.10-5.20: Read the source code and talk with the mentor -<br>
understand its structure and working flow<br>
<br>
5.21-6:10: Read the paper and start to do some experiments on it<br>
– understand the algorithm<br>
<br>
6.11-6.30: Code and test the first step: construction of highway<br>
hierarchies<br>
<br>
7.1-7.5: Write middle term report<br>
<br>
7.6-7.20: Code and test the second step: the query – compare the<br>
output with the output generated by other algorithms<br>
<br>
7.21-7.31: Comprehensively test the algorithm and the library -<br>
call functions from other software<br>
<br>
8.1-8.10: Improve documents and write final report.<br>
<br>
5. Future ideas / How can your idea be expanded?<br>
<br>
None<br>
<br>
<br>
______________________________<u></u>_________________<br>
pgrouting-dev mailing list<br></div></div>
<a href="mailto:pgrouting-dev@lists.osgeo.org" target="_blank">pgrouting-dev@lists.osgeo.org</a> <mailto:<a href="mailto:pgrouting-dev@lists.osgeo.org" target="_blank">pgrouting-dev@lists.<u></u>osgeo.org</a>><div class="im">
<br>
<a href="http://lists.osgeo.org/mailman/listinfo/pgrouting-dev" target="_blank">http://lists.osgeo.org/<u></u>mailman/listinfo/pgrouting-dev</a><br>
<br>
<br>
<br>
<br>
--<br>
Regards,<br>
-Jay Mahadeokar<br>
<br>
<br>
______________________________<u></u>_________________<br>
pgrouting-dev mailing list<br></div>
<a href="mailto:pgrouting-dev@lists.osgeo.org" target="_blank">pgrouting-dev@lists.osgeo.org</a> <mailto:<a href="mailto:pgrouting-dev@lists.osgeo.org" target="_blank">pgrouting-dev@lists.<u></u>osgeo.org</a>><div class="im">
<br>
<a href="http://lists.osgeo.org/mailman/listinfo/pgrouting-dev" target="_blank">http://lists.osgeo.org/<u></u>mailman/listinfo/pgrouting-dev</a><br>
<br>
<br>
<br>
<br>
--<br>
Georepublic UG & Georepublic Japan<br></div>
eMail: <a href="mailto:daniel.kastl@georepublic.de" target="_blank">daniel.kastl@georepublic.de</a> <mailto:<a href="mailto:daniel.kastl@georepublic.de" target="_blank">daniel.kastl@<u></u>georepublic.de</a>><br>
Web: <a href="http://georepublic.de" target="_blank">http://georepublic.de</a> <<a href="http://georepublic.de/" target="_blank">http://georepublic.de/</a>><div class="im"><br>
<br>
<br>
______________________________<u></u>_________________<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/<u></u>mailman/listinfo/pgrouting-dev</a><br>
</div></blockquote><div class="HOEnZb"><div class="h5">
<br>
______________________________<u></u>_________________<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/<u></u>mailman/listinfo/pgrouting-dev</a><br>
</div></div></blockquote></div><br><br clear="all"><div><br></div>-- <br>Steve Horn<br><br>
</div>