7

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?

MerseyViking
  • 14,543
  • 1
  • 41
  • 75
skanatek
  • 629
  • 1
  • 5
  • 13
  • 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 04 '11 at 02:18

1 Answers1

8

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.

Fabien Ancelin
  • 857
  • 4
  • 13