@Marcus So you are using database to model a graph, can you show me the graph's table structure in your database?
You are limiting to all of Baden-Württemberg (Germany), can you give the number of vertices and edges (i.e number of records in vertices table and edges table)? You did not load the whole graph into memory --> you are using sql statement to query against database each time your routing algorithmn vist a node? @Tristram Gräbener Thanks for sharing about compressed sparse row graph model. I did not know about its exist until you gave the url. When I devveloped my routing application last time, I did not know about "adjacency list" or "adjacency matrix" data structure. I just based on my own common sense to come out with the following graph data structure: Node int lat int lon LinkNode byte numLink int linkNode[] int linkCost[] So my graph is modeled as: Node Nodes[n] --> this is vertices list LinkNode LinkNodes[n] --> this is edges list where n is number of nodes/vertices My routing application run on a system that has no database and only 1024KB (1MB) memory, so I have no choice but have to store all graph data in flat files. After I come out with my own sommon sense graph data structure, I start to search the net and know about "adjacency list" or "adjacency matrix" data structure. Do you think my own graph data structure is similar or exactly the same with "adjacency list" data structure? I will study the "compressed sparse row" to see whether it will save more space compare to my own data structure or not? But at the first look, I have a feeling "compressed sparse row" will not save more space than my own data structure. Can you give me more example about how to use "compressed sparse row" data structure to model a simple directed graph with link cost on each edge? You use Navteq database arround Toulouse with about 80K arcs --> Did you mean 80K arcs is 80K nodes? If yes, your graph is quite small. If you can load the whole graph into memory (100MB), I am sure A* algorithmn will run faster than dijkstra algorithmn as A* algorithmn only visit the node that have minimun toal cost, while dijkstra algorithmn visit nodes in every possible directions. @Lambertus To compare the 35km route and 120km route in the New York area, I may need to know how many routing nodes in the route as some route is very long but contains a few nodes --> run very fast, while shorter route contains a lot or nodes run very slow. You said the query required about 145MB ram, so the 145MB ram is used to store the whole graph data or just to store A* algorithmn's open and closed list? @Nic Roets So you use "Compressed sparse row" to model your graph, and your NewYork graph has about 5 millions nodes --> space required is 200MB --> do you load the whole into memory or store in database and use sql statement to query? You said: gosmore uses A*. A heap is used to find the next node to evaluate. --> So you used binary heap (sorted heap) to pick up the next node? Can you share how you sort the heap? How to remove the first element from heap and how to update the heap when a node in open list has better total cost? -- View this message in context: http://www.nabble.com/How-big-is-your-graph--How-long-to-find-30km-route-in-your-graph--tp19985191p19990939.html Sent from the OpenStreetMap - Routing mailing list archive at Nabble.com. _______________________________________________ Routing mailing list [email protected] http://lists.openstreetmap.org/listinfo/routing
