[pgrouting-dev] PostGIS 2 Release

[Stephen Woodbridge]

On 2/11/2012 10:46 AM, Steve Horn wrote:
> Was wondering what impact, if any does the pending PostGIS 2 release
> have on the pgRouting project?
>
> I noticed that PostGIS 2 will include the ability to create network
> topology (similar to pgRouting's assign_vertex_id???). Are there other
> potential replacement functions included up that anyone knows of?

This question came up on the postGIS list not too long ago and the 
answer was probably does not help pgRouting. As some background on how 
pgRouting works, a request is handle like this:

1. request is passed start and end and a SQL query for the edges of the 
network
2. internally, we read the edges and build a graph
3. we solve the graph using the appropriate algorithm
4. we return the results
5. we destroy the graph and other internal structures

The problem with passing the topology to pgRouting is that while it is a 
graph, it is not in a form that we can easily and quickly access from a 
solvers point of view. In the above, it normally takes more time to read 
the graph data and build the graph than it does to solve the graph. So 
it would be nice to have a persistent graph, but then you have other 
issues, like:

Do you keep the whole graph? or only the part needed for the solution? 
If you keep the whole graph, then where do you cache it? how fast is it 
to access the graph when you need it? how to you update the graph if you 
want to change the edge weights, or the topology? If you want to keep 
only a portion of the graph, how do you cache and will you have a high 
enough cache hit rate to make it worth you effort?

And these are only a few of the issues, so you can see it is not a 
trivial problem. The current method of building the graph based on the 
bounding box or some other tricks to get the data needed for a given 
request is fast and it has the added flexibility of allowing the request 
to be high dynamic. For example I have implemented, realtime traffic 
feeds where the cost values are updated based on the feed data. And we 
can modify the edge set based on the vehicle class such as car, truck, 
emergency vehicle, or pedestrian.

That said, the dev team is aware that there is a need for solutions that 
might not be as highly dynamic but need better performance and we are 
discussing what it would take to build a route server using a saved 
graph that would probably exist outside of postgresql. I don't know if 
we will ever do this or not, but it is possible and straight forward if 
it were funded. But we really need to fix some bugs and cut a new 
release of the existing code before we do anything else.

-Steve