I'm pretty old school and do everything from the command line. So to get started:
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.
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.
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.
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@swoodbridge.com <mailto:woodbri@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@swoodbridge.com <mailto:woodbri@swoodbridge.com>
<mailto:woodbri@swoodbridge. com
<mailto:woodbri@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@gmail.com <mailto:jai.mahadeokar@gmail.com>
<mailto:jai.mahadeokar@gmail. com <mailto:jai.mahadeokar@gmail.com>>
<mailto:jai.mahadeokar@gmail. com
<mailto:jai.mahadeokar@gmail. com
<mailto:jai.mahadeokar@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@gmail.com <mailto:logicnut@gmail.com>
<mailto:logicnut@gmail.com>
<mailto:logicnut@gmail.com
<mailto:logicnut@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@lists.osgeo.org <mailto:pgrouting-dev@lists.osgeo.org>
<mailto:pgrouting-dev@lists. osgeo.org
<mailto:pgrouting-dev@lists.osgeo.org>>
<mailto:pgrouting-dev@lists.
osgeo.org <http://osgeo.org>
<mailto:pgrouting-dev@lists. osgeo.org
<mailto:pgrouting-dev@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@lists.osgeo.org <mailto:pgrouting-dev@lists.osgeo.org>
<mailto:pgrouting-dev@lists. osgeo.org
<mailto:pgrouting-dev@lists.osgeo.org>>
<mailto:pgrouting-dev@lists.
osgeo.org <http://osgeo.org>
<mailto:pgrouting-dev@lists. osgeo.org
<mailto:pgrouting-dev@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@georepublic.de
<mailto:daniel.kastl@georepublic.de>
<mailto:daniel.kastl@ georepublic.de
<mailto:daniel.kastl@georepublic.de>> <mailto:daniel.kastl@
<mailto:daniel.kastl@>
georepublic.de <http://georepublic.de> <mailto:daniel.kastl@
georepublic.de <mailto:daniel.kastl@georepublic.de>>>
Web: http://georepublic.de/>
______________________________ _________________
pgrouting-dev mailing list
pgrouting-dev@lists.osgeo.org
<mailto:pgrouting-dev@lists.osgeo.org>
<mailto:pgrouting-dev@lists. osgeo.org
<mailto:pgrouting-dev@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@lists.osgeo.org
<mailto:pgrouting-dev@lists.osgeo.org>
<mailto:pgrouting-dev@lists. osgeo.org
<mailto:pgrouting-dev@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@lists.osgeo.org <mailto:pgrouting-dev@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@lists.osgeo.org <mailto:pgrouting-dev@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@lists.osgeo.org
http://lists.osgeo.org/mailman/listinfo/pgrouting-dev