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

[Marcus Wolschon]

On Wed, 15 Oct 2008 20:55:42 -0700 (PDT), j2megps <j2megps at yahoo.com>
wrote:
> You said:
> <<<
> gosmore mmap()s a flat file. So the operating system loads pages as they
> are
> accessed.
>>>>
> 
> Can you tell me more about this? So gosmore did not load the whole graph
> into memory? It store graph data in a flat file and read it whenever
> needed?

Please read up on memory-mapping.
It lets the operating-system load and cache (8kb)pages
from the file while accessing it as if it where in-memory.


> @Marcus 
> You said:
> <<<
> the router loads updates and missing areas from the OSM-server while
> routing.
>>>>
> 
> Do you mean your routing application find route tile by tile?

No. It has a manual download-button. Tiles have nothing to do with this.

> It is very interesting. I do not know how to do routing without the need
of
> knowing graph as the whole. i.e if the graph divide into tiles, I do not
> know how to do the routing.

Each way knows it's ordered list of node-ids.
I have an index of nodeID->tileNumber (as well as wayID->tileNumber and
normalized way/area-name(s) to wayID for address-searches).

> You said:
> <<<
> No, I am using a memory-sensitive cache that uses as much memory as
> is currently unused to cache reat or unwritten data. 
>>>>
> 
> So you cached tile by tile in memory and your routing application just
> calculate within the cached nodes, right?

No. It calculated using all the map and loads parts of it (that need not
have to be complete tiles) into memory as they are needed.

> You said:
> <<<
> That sounds strange. What is the purpose of the device?
> Is it for pedestriand, weelchairs, bikes? 
>>>>
> 
> the device is mobile phone. it is for car routing so it has to support
> million of nodes.

Your phone has just 1MB of memory for the map you are using?
How do you suppose to route from one city to another or within
any larger city? Where do you think of storing symbol-bitmaps for
the map-rendering, the indexed address-database, ... with this little
memory?

Marcus