[Routing] How big is your graph? How long to find 30km route in your graph?

[Marcus Wolschon]

On Tue, 14 Oct 2008 18:27:18 -0700 (PDT), j2megps <j2megps at yahoo.com>
wrote:
> Hi everyone,
> 
> Please share with me the following information:
> 
> Which data structure you used to model a graph (i.e adjacency list or
> adjacency matrix data structure)?

A database indexed by way-ID and nodeID+node-location.
These 2 data-structures are not exactly usable for big graphs.
(O(n) search-time for the list and O(n^2) memory-footprint + O(n)
search-time
for the matrix)

> How big is your graph in term of number of routing nodes and routing
links
> or number of vertices and edges?

I am limiting myself to all of Baden-Württemberg (Germany) for testing,
mainly because I am rebuilding my test-database from time to time.
There should be no problem having the world in there.

> Can you load the whole graph into memory when you calculate a route?

No chance.

> How long does it take to calculate a 35km shortest route through NewYork
> city?

Don't know. I don't do tests on any US-data and it heavily depends on the
database-backend, metric and routing-algorithm I choose. (There are a
number
of each of these to choose from in Traveling-Salesman.)

Marcus