On Tue, 14 Oct 2008 18:27:18 -0700 (PDT), j2megps <[EMAIL PROTECTED]> 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 _______________________________________________ Routing mailing list [email protected] http://lists.openstreetmap.org/listinfo/routing
