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 <[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)? > > 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 > [email protected] > http://lists.openstreetmap.org/listinfo/routing > _______________________________________________ Routing mailing list [email protected] http://lists.openstreetmap.org/listinfo/routing
