[pgrouting-dev] GSoC Project: Highway Hierarchies Routing Support for pgRouting

[Stephen Woodbridge]

Created a wiki page for this:

http://github.com/pgRouting/pgrouting/wiki/Developer---Getting-Started


On 3/26/2012 2:14 PM, Stephen Woodbridge wrote:
> I'm pretty old school and do everything from the command line. So to get
> started:
>
> git clone git at github.com:pgRouting/pgrouting.git
> cd pgrouting
> # to keep it simple to start leave -DWITH_TSP=ON -DWITH_DD=ON off the
> # next line
> cmake -DWITH_TSP=ON -DWITH_DD=ON .
> make
> sudo make install
>
> This is the basics to compile and install.
> make install will copy librouting.so librouting_dd.so librouting_tsp.so
> to /usr/lib/postgresql/8.3/lib/ or the appropriate path on your system.
> the later two .so files are for -DWITH_DD=ON and -DWITH_TSP=ON
> respectively and will not get copied if you don't need them.
>
> You need to restart the server if you change these libraries when
> developing.
>
> Debugging is trickier. There is a way to start the postgresql server in
> single user mode running in gdb and you can set a break point in your
> code to trace and examine it, but I have not used this.
>
> In your C code you can call DBG(format, args...) if you use:
>
> //#undef DEBUG
> #define DEBUG 1
>
> #ifdef DEBUG
> #define DBG(format, arg...) \
> elog(NOTICE, format , ## arg)
> #else
> #define DBG(format, arg...) do { ; } while (0)
> #endif
>
> This will display NOTICE messages in the out put when it runs. If you
> are calling C++, you will need to figure out how to call this from C++
> or open a log file and write messages to that. Yeah, these are stoneage
> tools :( but if you find a better way please share.
>
> If you look at the trsp branch you will find the code in extra and this
> is probably a good example to follow for how to add code. It builds into
> its own librouting_trsp.so so this can be installed separate from change
> the core code.
>
> extra/trsp/sql/ -- has the plpgsql wrappers that link to the library
> extra/trsp/src/ -- has the C and C++ code to build the library
>
> When this project was done, Ashraf working in Bangladesh developer the
> C++ code and wrote his own main for testing and debuging from a
> postgresql free environment. Once this code was working and debuggged, I
> wrote the trsp.c and trsp_core.cpp to link to his code and debugged the
> postgresql side of things using the DBG() macros above.
>
> So try to just walk through this much to start. I think the key here is
> to divide and conquer. If you notice the C code really does little more
> than talk to the server and create structs that get passed to the solver
> and then take the solver results and pass them back to postgresql. The
> solver should get developed and tested outside this environment and once
> it is vetted then drop it in and you can focus you debugging on the data
> handling and not the solver. Also we made the solver main so that we
> could easily pass create a dump of the data from sql to a text file and
> then read that into the solver for testing. When something broke, it was
> easy to verify if it was a solver or interface issue.
>
> -Steve
>
> On 3/26/2012 1:04 PM, Steve Horn wrote:
>> I have a Ubuntu box set up that I can use for development.
>>
>> A 30-45 minute virtual meeting with screen sharing would be really
>> helpful. I'd hope to see stuff like how you have your development
>> environment configured, how you go about debugging the code, and how the
>> build process works.
>>
>> To make the time more valuable I was thinking we could set something up
>> to where many people could join in and learn at the same time.
>>
>>
>> On Mon, Mar 26, 2012 at 11:09 AM, Stephen Woodbridge
>> <woodbri at swoodbridge.com <mailto:woodbri at swoodbridge.com>> wrote:
>>
>> I am happy to give my insights on this and to answer questions if I
>> can. If we do it via email I will try to collect the information and
>> create a new documentation page on the website to help future hackers.
>>
>> I have Linux and work in Linux, but I have a small amount of know
>> about Windows, but if you go very deep into Windows I will not be of
>> much help. My strength is finding solutions to problems so ask
>> questions and I will do my best to answer them and explain as much
>> as I can.
>>
>> What OS are you working on?
>>
>> -Steve
>>
>> On 3/26/2012 10:10 AM, Steve Horn wrote:
>>
>> 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.
>>
>> Perhaps others would be interested in this as well?
>>
>> On Mon, Mar 26, 2012 at 9:34 AM, Stephen Woodbridge
>> <woodbri at swoodbridge.com <mailto:woodbri at swoodbridge.com>
>> <mailto:woodbri at swoodbridge. com
>> <mailto:woodbri at swoodbridge.com>>> wrote:
>>
>> Hi Jinfu,
>>
>> 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!
>>
>> 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.
>>
>> 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.
>>
>> 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.
>>
>> So if you break this down into tangible tasks that represent
>> potential stopping points you might have something like:
>>
>> 1. write code to extract data from postgresql, preprocess
>> it, write
>> results back to postgresql
>> 2. write code to process a route request, ie: get data, solve
>> request, return results.
>> 3. rewrite algorithm to be AGPL clean
>>
>> 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.
>>
>> I'm willing to co-mentor any pgrouting GSoC projects.
>>
>> Best regards,
>> -Steve
>>
>>
>> On 3/26/2012 2:59 AM, Daniel Kastl wrote:
>>
>> Hi Jinfu,
>>
>> Thank you for posting to the list!
>> And thank you for your comment, Jay!
>>
>> There are already implementations of the contraction
>> hierarchies
>> algorithm available.
>> I know about this one for example: http://project-osrm.org/
>> OpenTripPlanner is using it as well:
>> https://github.com/openplans/ OpenTripPlanner/wiki/
>> <https://github.com/openplans/ OpenTripPlanner/wiki/
>> <https://github.com/openplans/OpenTripPlanner/wiki/>>
>>
>> There are two problems I see with this algorithm:
>>
>> * Can we use an algorithm published under AGPL? Or are
>> only the
>>
>> existing applications AGPL but not the algorithm.
>> * Contraction Hierarchies does a lot of pre-processing.
>>
>> pgRouting's strength is, that the network data can be
>> changed easily.
>> Jinfu, did you already think about details?
>>
>> I think an implementation of this algorithm in pgRouting
>> is a very
>> ambitious GSoC project and should be planned well.
>> But it would be a great contribution for sure.
>>
>> Jinfu, maybe you can look a bit more into details,
>> search for
>> existing
>> implementations and try to understand how they work.
>> Have you already used pgRouting and written pl/pgsql
>> functions?
>>
>> Daniel
>>
>>
>> On Mon, Mar 26, 2012 at 3:42 PM, Jay Mahadeokar
>> <jai.mahadeokar at gmail.com <mailto:jai.mahadeokar at gmail.com>
>> <mailto:jai.mahadeokar at gmail. com <mailto:jai.mahadeokar at gmail.com>>
>> <mailto:jai.mahadeokar at gmail <mailto:jai.mahadeokar at gmail>. com
>> <mailto:jai.mahadeokar at gmail. com
>> <mailto:jai.mahadeokar at gmail.com>>>> wrote:
>>
>> Hi Jinfu Leng,
>>
>> I did GSoc 2011 with pgRouting. I had looked in
>> detail about
>> this
>> problem last year too. The highway hierarchies is
>> actually
>> not the
>> fastest method now. Instead Contraction Hierarchies by
>> Giesberger is
>> a much better and faster heuristic.
>> http://algo2.iti.kit.edu/ english/routeplanning.php
>> <http://algo2.iti.kit.edu/ english/routeplanning.php
>> <http://algo2.iti.kit.edu/english/routeplanning.php>>
>> will give you all the details of latest research in this
>> area. The
>> source code of Contraction hierarchies is also
>> available for
>> download, so you could check it out too.
>>
>> I would also suggest you look at last years' mailing
>> list
>> discussions regarding this topic.
>>
>> Best of luck!
>>
>> On Mon, Mar 26, 2012 at 10:15 AM, Jinfu Leng
>> <logicnut at gmail.com <mailto:logicnut at gmail.com>
>> <mailto:logicnut at gmail.com <mailto:logicnut at gmail.com>>
>> <mailto:logicnut at gmail.com <mailto:logicnut at gmail.com>
>> <mailto:logicnut at gmail.com <mailto:logicnut at gmail.com>>>> wrote:
>>
>> Hi all,
>>
>> I am interested in applying the GSoC project,
>> and I want
>> to work
>> on pgRouting. The description of the idea is
>> pasted at the
>> bottom. I want to get some suggestions from you
>> guys. Any
>> suggestion is welcome. And if some previous GSoC
>> students can
>> share your previous applications, that would be
>> great.
>>
>> In addition, I am looking for a potential mentor.
>>
>> Thanks a lot,
>> Jinfu
>>
>> *Title* : Highway Hierarchies Routing Support
>> for pgRouting
>>
>> *Describe your idea*
>>
>>
>> 1. Introduction
>>
>> One of the main challenges of routing is the
>> huge size
>> of road
>> networks. Especially, given source node and sink
>> node in
>> long
>> distance, shortest path computation will be very
>> time
>> consuming.
>> I would like to improve current routing
>> algorithm by adding
>> highway hierarchies routing support.
>>
>> 2. Background
>>
>> Routing is a very common task in GIS, and
>> pgRouting is a
>> famous
>> routing library which provides routing functions for
>> many GIS
>> software, such as PostGIS/PostgreSQL. Due to the
>> huge
>> size of
>> road networks, finding path requires significant
>> computing time,
>> especially for long distance source and
>> destination. This
>> results in slow response time and unfriendly user
>> experience.
>>
>> 3. The idea
>>
>> In fact, this algorithm is not my idea. My work will
>> base on the
>> paper [P. Sanders, D. Schultes]. Basically, this
>> algorithm
>> includes two steps: construct the highway
>> hierarchies;
>> query on
>> the highway hierarchies. According to their
>> experiments,
>> this
>> new approach can be about 2000 times faster than the
>> original
>> Dijkstra’s algorithm. The tradeoff is spending a few
>> hours for
>> generating highway hierarchies. I want to
>> implement this
>> algorithm in pgRouting library.
>>
>> 4. Project plan
>>
>> 5.10-5.20: Read the source code and talk with
>> the mentor -
>> understand its structure and working flow
>>
>> 5.21-6:10: Read the paper and start to do some
>> experiments on it
>> – understand the algorithm
>>
>> 6.11-6.30: Code and test the first step:
>> construction of
>> highway
>> hierarchies
>>
>> 7.1-7.5: Write middle term report
>>
>> 7.6-7.20: Code and test the second step: the query –
>> compare the
>> output with the output generated by other algorithms
>>
>> 7.21-7.31: Comprehensively test the algorithm
>> and the
>> library -
>> call functions from other software
>>
>> 8.1-8.10: Improve documents and write final report.
>>
>> 5. Future ideas / How can your idea be expanded?
>>
>> None
>>
>>
>> ______________________________ _________________
>> pgrouting-dev mailing list
>> pgrouting-dev at lists.osgeo.org <mailto:pgrouting-dev at lists.osgeo.org>
>> <mailto:pgrouting-dev at lists. osgeo.org
>> <mailto:pgrouting-dev at lists.osgeo.org>>
>> <mailto:pgrouting-dev at lists <mailto:pgrouting-dev at lists>.
>> osgeo.org <http://osgeo.org>
>> <mailto:pgrouting-dev at lists. osgeo.org
>> <mailto:pgrouting-dev at lists.osgeo.org>>>
>>
>> http://lists.osgeo.org/ mailman/listinfo/pgrouting-dev
>> <http://lists.osgeo.org/ mailman/listinfo/pgrouting-dev
>> <http://lists.osgeo.org/mailman/listinfo/pgrouting-dev> >
>>
>>
>>
>>
>> --
>> Regards,
>> -Jay Mahadeokar
>>
>>
>> ______________________________ _________________
>> pgrouting-dev mailing list
>> pgrouting-dev at lists.osgeo.org <mailto:pgrouting-dev at lists.osgeo.org>
>> <mailto:pgrouting-dev at lists. osgeo.org
>> <mailto:pgrouting-dev at lists.osgeo.org>>
>> <mailto:pgrouting-dev at lists <mailto:pgrouting-dev at lists>.
>> osgeo.org <http://osgeo.org>
>> <mailto:pgrouting-dev at lists. osgeo.org
>> <mailto:pgrouting-dev at lists.osgeo.org>>>
>>
>> http://lists.osgeo.org/ mailman/listinfo/pgrouting-dev
>> <http://lists.osgeo.org/ mailman/listinfo/pgrouting-dev
>> <http://lists.osgeo.org/mailman/listinfo/pgrouting-dev> >
>>
>>
>>
>>
>> --
>> Georepublic UG & Georepublic Japan
>> eMail: daniel.kastl at georepublic.de
>> <mailto:daniel.kastl at georepublic.de>
>> <mailto:daniel.kastl@ georepublic.de
>> <mailto:daniel.kastl at georepublic.de>> <mailto:daniel.kastl@
>> <mailto:daniel.kastl@>
>> georepublic.de <http://georepublic.de> <mailto:daniel.kastl@
>> georepublic.de <mailto:daniel.kastl at georepublic.de>>>
>> Web: http://georepublic.de <http://georepublic.de/>
>>
>>
>>
>> ______________________________ _________________
>> pgrouting-dev mailing list
>> pgrouting-dev at lists.osgeo.org
>> <mailto:pgrouting-dev at lists.osgeo.org>
>> <mailto:pgrouting-dev at lists. osgeo.org
>> <mailto:pgrouting-dev at lists.osgeo.org>>
>> http://lists.osgeo.org/ mailman/listinfo/pgrouting-dev
>> <http://lists.osgeo.org/ mailman/listinfo/pgrouting-dev
>> <http://lists.osgeo.org/mailman/listinfo/pgrouting-dev> >
>>
>>
>> ______________________________ _________________
>> pgrouting-dev mailing list
>> pgrouting-dev at lists.osgeo.org
>> <mailto:pgrouting-dev at lists.osgeo.org>
>> <mailto:pgrouting-dev at lists. osgeo.org
>> <mailto:pgrouting-dev at lists.osgeo.org>>
>> http://lists.osgeo.org/ mailman/listinfo/pgrouting-dev
>> <http://lists.osgeo.org/ mailman/listinfo/pgrouting-dev
>> <http://lists.osgeo.org/mailman/listinfo/pgrouting-dev> >
>>
>>
>>
>>
>> --
>> Steve Horn
>>
>>
>>
>> ______________________________ _________________
>> pgrouting-dev mailing list
>> pgrouting-dev at lists.osgeo.org <mailto:pgrouting-dev at lists.osgeo.org>
>> http://lists.osgeo.org/ mailman/listinfo/pgrouting-dev
>> <http://lists.osgeo.org/mailman/listinfo/pgrouting-dev>
>>
>>
>> ______________________________ _________________
>> pgrouting-dev mailing list
>> pgrouting-dev at lists.osgeo.org <mailto:pgrouting-dev at lists.osgeo.org>
>> http://lists.osgeo.org/ mailman/listinfo/pgrouting-dev
>> <http://lists.osgeo.org/mailman/listinfo/pgrouting-dev>
>>
>>
>>
>>
>> --
>> Steve Horn
>>
>>
>>
>> _______________________________________________
>> pgrouting-dev mailing list
>> pgrouting-dev at lists.osgeo.org
>> http://lists.osgeo.org/mailman/listinfo/pgrouting-dev
>
> _______________________________________________
> pgrouting-dev mailing list
> pgrouting-dev at lists.osgeo.org
> http://lists.osgeo.org/mailman/listinfo/pgrouting-dev