[GraphHopper] get instructions from path

[Peter K]

Hi Ottavio,

> my idea is to create another file, let's call it names, with all the
street names and to add an offset for each node

sorry for the confusion, that is exactly what I mentioned :) !

But rather than per node I would add a pointer for every edge instead.
(Also - at a later stage - one could think about how to store the names
so that they could be used for address lookup. e.g. sorted etc)


> do nodes correspond to the nodes of OSM?

Nodes do not correspond to OSM ids. As we need to use them as array
indices. This avoids costly HashMap lookups and memory waste (maps are
1.5 to 2 times larger than an array).
Also see the osmIdToIndexMap in OSMReaderHelperDoubleParse where I map
OSM ids (long) to node ids (integer)


> In the picture of the data layout I don't understand the
> meaning of the arrows that go from the nodes to the edge

The arrow from one node to an edge is just the first edge of this node.
It is an implementation of a linked list.
See my updated description:

/One node has several edges which is implemented with a linked list.
E.g. node 3 points to its first edge in the edge area at position 0 to
edge 0-3 (nodeA-nodeB where nodeA is always smaller than nodeB). To get
the next edge of node 3 you need nextB and this goes to edge 1-3, again
node 3 is nodeB, but for the next edge 3-5 node 3 is nodeA ... and so on.//

/
> Finally, do properties have a fixed length? Do you plan to store the
name of the stree there? But I think
> that this solution would duplicate the name of the street for all the
nodes. Would it be more efficient to
> store an offset for the content of a file holding all the names of the
street?

Exactly. See also how I'm using a separate 'file' (or DataAccess object)
for wayGeometry, which is refered from one of the edge properties and
uses the 'geometry' DataAccess object.


> Can you please explain me how you thought about using a byte-oriented
DataAccess
> to handle the street names?

I just meant again a 'file'. But DataAccess is a bit more generic as one
can use it for in-memory access (fast for server-side)
or memory mapped (for android). At the moment one can only store integer
values (to keep it simple), but we need
to store strings which could be easily converted to a byte array but not
so easy to an integer array. So I would have to change or extend the
DataAccess interface to make it possible to hold and access an in-memory
byte array (or the memory-mapped ByteBuffer equivalent).

Regards,
Peter.

> Il 12/03/2013 17:41, Peter K ha scritto:
>> Hi Ottavio,
>>
>> thanks for reaching out. That is still on the todo list. I would be
>> very happy for your contribution! But you'll have to digg deep into
>> GraphHopper - just to warn you ;)
>>
>> See the newly created issue:
>> https://github.com/graphhopper/graphhopper/issues/23
>>
>> Let me know if you need assistance or further details. I could
>> probably do the first step relative fast in a separate instructions
>> branch if that would help a bit.
>
> Hello Peter,
>
> yesterday I studied the issue #23 and I think that the second and the
> third point are clear,
>
> I think that the first point is not clear. Let me explain: you say
> that you would like to add a DataAccess to GraphStorage. If I
> correctly understand, the DataAccess interface is a way to access the
> graph information. I don't understand why you think that changing the
> access from int to byte would be sufficient to have it implemented.
>
> I've read https://github.com/graphhopper/graphhopper/wiki/Developers ,
> and I have some questions about the data layout:
>
>  1. do nodes correspond to the nodes of OSM? In the picture of the
>     data layout I don't understand the meaning of the arrows that go
>     from the nodes to the edges.
>  2. are the edges the adjacency of the nodes? The would explain nextA
>     and nextB, but I don't understand why in the picture you have the
>     nodes 0 and 3 pointing to the same row.
>  3. what is the meaning of nodeA and nodeB? and what does nodeA<nodeB
>     mean? Really, I tried to understand but I was not able to get the
>     structure.
>  4. Finally, do properties have a fixed length? Do you plan to store
>     the name of the stree there? But I think that this solution would
>     duplicate the name of the street for all the nodes. Would it be
>     more efficient to store an offset for the content of a file
>     holding all the names of the street?
>
> my idea is to create another file, let's call it names, with all the
> street names and to add an offset for each node so that it would be
> fast to retrieve the name of the streets when the evaluated path is
> converted to instructions. Can you please explain me how you thought
> about using a byte-oriented DataAccess to handle the street names?
>
> Ottavio
>

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.openstreetmap.org/pipermail/graphhopper/attachments/20130314/f90d92d8/attachment.html>