What does pgRouting's architecture look like?

Question

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?

Answer 1

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.