[pgrouting-dev] GSoC Project: Highway Hierarchies Routing Support
for pgRouting
Stephen Woodbridge
woodbri at swoodbridge.com
Mon Mar 26 14:14:41 EDT 2012
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
More information about the pgrouting-dev
mailing list