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

[Tristram Gräbener]

Hi,

I use boost::graph

The data structure used is what they call a compressed sparse row
(http://www.boost.org/doc/libs/1_36_0/libs/graph/doc/compressed_sparse_row.html),
I must admit that I never did any comparaison against adjacency lists.
However I thing that a matrix wouldn't be a good idea: the graph is
extreamly sparse!

I use Navteq database (yeah... shame on me... I still hadn't time to
work on a osm parser) arround Toulouse with about 80K arcs

I used the boost dijkstra implementation (stoping the search once the
target has been reached). The search time is arround 100ms on a
core2duo 1.6Ghz. The whole graph is loaded in ram (about 100MB) thus
loading is a bit slow, but the search quite effective.

I didn't notice any real gain of performance using A*, but I have to
experiment a little bit arround that.

On Tue, Oct 14, 2008 at 6:27 PM, 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)?
>
> How big is your graph in term of number of routing nodes and routing links
> or number of vertices and edges?
>
> Can you load the whole graph into memory when you calculate a route?
>
> How long does it take to calculate a 35km shortest route through NewYork
> city?
>
> Do you use any special technic to speed up A* algorithm? (like using sorted
> open list,...)
>
> Thank for sharing your idea in advance.
>
> Regards,
>
> --
> View this message in context: http://www.nabble.com/How-big-is-your-graph--How-long-to-find-30km-route-in-your-graph--tp19985191p19985191.html
> Sent from the OpenStreetMap - Routing mailing list archive at Nabble.com.
>
>
> _______________________________________________
> Routing mailing list
> Routing at openstreetmap.org
> http://lists.openstreetmap.org/listinfo/routing
>