There are some improvements possible in graph tile storage. We make the distinctions between:
Routing data: data that is used during route planning:
edge length
edge type
vertex ids.
edge enumeration
turn costs: includes turn restrictions and vertex attributes.
Meta data: data is not used during route planning but is needed for a good output and for preprocessing:
Edge attributes.
Vertex attributes.
Turn restrictions and their attributes.
The focus should be on getting storing the routing data as efficiently as possible. The meta data has to be accessible but doesn't not have to be available immediately when accessing an edge.
Current structure
The vertices have the following data:
pointer to first edge.
turn cost table id.
attributepointer: pointer to the attributes. meta
The current graph edges has the following data:
vertex1, vertex2 ids.
nextedgepointer1, nextedgepointer2
(optional) edgeid: only in case the edge doesn't originate in the tile.
edge type: the type of edge.
edge length: the length of the edge.
tail and head orders: turn restrictions.
shapepointer: pointer to the shape. meta
attributepointer: pointer to the attributes. meta
Improvements
Ideal would be to have a data structure where we have vertexids and edgeids that increase by one each time a vertex or edges is added. These IDs remain constant even when changing some of the edge payloads.
The new structure could be
Routing data
One byte array with vertex routing data:
pointer to the first edge.
pointer to turn cost table (if any).
vertex id: The by-one-increasing vertex id. This is considered meta, it won't be used during routing and we won't need to read it unless we want to access the vertex's meta data.
One edge array with edge routing data:
vertex1 pointer: not the vertex id, but the pointer.
vertex2 pointer: not the vertex id, but the pointer.
edge type id: the edge type id (optional).
edge length: the edge length (optional).
head and tail indexes: the head and tail indexes for the turn cost tables (optional).
nextedge1 pointer offset: the offset relative to this edge's pointer.
nextedge2 pointer offset: the offset relative to this edge's pointer.
edge id: the by-one-increasing edge id. This is considered meta, it won't be used during routing and we won't need to read it unless we want to access the edge's meta data.
Meta data
Now that we have one-increasing ids that won't change we can store all meta-data using those ids. We store the edge attributes identified by edge id, the same for the shapes, turn restrictions and vertex attributes.
Basic principles
There are some improvements possible in graph tile storage. We make the distinctions between:
Routing data: data that is used during route planning:
Meta data: data is not used during route planning but is needed for a good output and for preprocessing:
The focus should be on getting storing the routing data as efficiently as possible. The meta data has to be accessible but doesn't not have to be available immediately when accessing an edge.
Current structure
The vertices have the following data:
The current graph edges has the following data:
Improvements
Ideal would be to have a data structure where we have vertexids and edgeids that increase by one each time a vertex or edges is added. These IDs remain constant even when changing some of the edge payloads.
The new structure could be
Routing data
One byte array with vertex routing data:
One edge array with edge routing data:
Meta data
Now that we have one-increasing ids that won't change we can store all meta-data using those ids. We store the edge attributes identified by edge id, the same for the shapes, turn restrictions and vertex attributes.