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

[j2megps]

@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.