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

[Nic Roets]

The 35km route has 529 points. Don't ask me how many nodes were evaluated.
http://www.yournavigation.org/?flat=40.730599&flon=-73.98658&tlat=40.895796&tlon=-74.108587&fast=1&v=motorcar&layer=mapnik
The amount of memory was what the operating system reported and should
include everything.

gosmore mmap()s a flat file. So the operating system loads pages as they are
accessed.

The heap is a binary heap stored in an array and algorithms are really
undergrad / textbook stuff. Roughly 10 lines of code.

On Wed, Oct 15, 2008 at 12:38 PM, j2megps <j2megps at yahoo.com> wrote:

>
> @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
> Routing at openstreetmap.org
> http://lists.openstreetmap.org/listinfo/routing
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.openstreetmap.org/pipermail/routing/attachments/20081015/6df77179/attachment.html>