Take the 2-minute tour ×
Geographic Information Systems Stack Exchange is a question and answer site for cartographers, geographers and GIS professionals. It's 100% free, no registration required.

I know that pgRouting is a pretty nice tool, but I would like to use something of my own in my application, mainly because I don't know C and I don't know how to tweak the performance of pgRouting. Thus I am interested in how pgRouting's internals are organized.

How is the actual shortest path calculation done? Is it anything like the following:

  • Load the whole ways/edges table into memory with one 'select * from ways';
  • Build a graph from that;
  • Apply a C-based (based on the Boost library) shortest path algorithm to the graph;
  • Return a result into psql server?

The other interesting thing is - why does pgRouting store vertices coordinates (x1, y1, x2, y2) in the ways table? Is it the only table from which the graph is built?

share|improve this question
    
Even if you don't know c, is that faster to reinvent the wheel? PGRouting already exists, and if you spend 2 days studying the source code, you will get how it works if you know some basic programming. What's more C and C++ are fast, and therefore perfect for this kind of work. I didn't know C when I started working with it, now I have a custom routing engine based on pg_routing that works well. Even with being good at Java and C#, there is no way I could have a done a work of the same quality in the same amount of time. Plus Java or C# would be slower. You should take that into consideration. –  Fabien Ancelin Aug 4 '11 at 2:18

1 Answer 1

up vote 8 down vote accepted

You're right, except that C is the layer between c++ encapsulating the algorithms and postgresql

The components of pgrouting are the following: 1. A c module that use a query in passed in Postgresql in order to build the graph. 2. C++ modules that converts it into a boost graph, and launch the routing. The components used are different depending on the kind of algorithm.

The fields x1, y1,x2,y2 are used by heuristics in order to add a geographic component that increase the search speed of the route. Note that in that case, the path returned by pg_routing is no longer likely to be the shortest one.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.