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?
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