Store way_id values for all edges

[danpat]

For debugging, it's very handy to be able to quickly cross-reference OSM. Currently, you have to do this manually using coordinates - get the location of the issue from OSRM, then browse to that location in OSM to get the way tag information.

I propose a new osrm-extract flag called --save-way-ids. When enabled, this will create a new, optional datafile called .osrm.edge_ways. At runtime, this file can be optionally mmap-ed, and data returned with annotations=ways and as a property on edges in the debug tiles.

Related: #5104

[MichalPP]

#4071 is related as well

[nnseva]

Hi people, I would like to implement this feature, but I need to have some explanations. Unfortunately, there is no enough documentation about the internal structure of the program data.

For the very first, I need to understand what does the Edge mean? Is it just a pair of Nodes directly connected? Or it is some sequence of nodes in one way from one branch of ways to another? Or something else? When the EdgeID appears? Is there some data storage indexed by the Edge ID?

I am looking into the code of osrm::engine::guidance::assembleGeometry() and don't understand, how to get there the EdgeID of the correspondent edges.

1. I've tried to use the FindEdge method of the facade (providing it to the BaseDataFacade from the AlgorithmDataFacade using virtual functions), and passing there the same parameters as passed to the facade.GetOSMNodeIDOfNode() in the code (they all typed as NodeID), but got an assertion error inside a FindEdge implementation of the StaticGraph. What I did improperly?
2. I've noticed that although the GetUncompressedForwardGeometry() (and several other methods of the BaseDataFacade class) parameter is marked as an EdgeID, the actual parameter passed to this (and others) method in the code is the geometry ID. Such code inconsistency leads to a full misunderstanding of what does the Edge (and EdgeID) mean really.
3. I could use a totally separate map<pair<OSMNodeID,OSMNodeID>,OSMWayID> in the function, but I am not sure, whether I can use it in such a multithreaded environment, and also, when and how to create this map. Additionally, I am afraid that this is not an optimal solution.

[danpat]

OSRM uses a line graph to represent the road network. This means that in the code where you're looking, a node is a road, and an edge is a turn.

The line graph is generated by the osrm-extract tool - it parses the OSM data into a regular graph (where nodes = intersections, and edges = roads). It then converts that into the line graph in the osrm::extractor::EdgeBasedGraphFactory.

When you're modifying things, it's important to understand whether you are working on the expanded line graph, or the unexpanded graph - the meaning of nodes/edges basically inverts at that point in the processing pipeline, and it can be hard to keep straight in your head. For a feature like you're proposing, you will have to touch both before and after generation of the line graph.

1. That won't work - OSM node IDs are not the types of nodes that FindEdge is looking for. There is no index for looking up OSM nodes in the graph. FindEdge is looking for a line-graph edge (i.e. a turn from one road to another).
2. Yes, it's unfortunate that NodeID was thrown about in the code as a simple type - there really should be a different type in that signature.
3. Creating a lookup from OSM node IDs to OSM way IDs is not the best way to tackle this problem.

My original thought here was to create the .edge_ways file using the same indexing as the .geometry file - then you can use the EdgeBasedNode.geometry_id to simply jump straight to the 64 bit OSM Way ID in the .edge_ways file.

Hope this helps you get started. It is, unfortunately, a fairly complex codebase. There are lots of intermediary data structures at play, and it takes a while to understand the full flow from OSM data through to routable graph.

[nnseva]

Great @danpat,

As I understand, the following code:

    const auto source_node_id =
        reversed_source ? source_node.reverse_segment_id.id : source_node.forward_segment_id.id;
    const auto source_geometry_id = facade.GetGeometryIndex(source_node_id).id;

gets the source_geometry_id of the first 'node' (i.e. road piece) - the geometry ID described by you. The same way looks like an appropriate to get the geometry ID of the last element which is passed to the function together with the first one as PhantomNodes.

But, what about intermediate elements - path_point, - got as PathData? I don't see any data to get the geometry ID from this data ... probably from_edge_based_node or some derivation, like:

const auto next_geometry_id = facade.GetGeometryIndex(path_point.from_edge_based_node).id;

?

[danpat]

@nnseva Yes, path_point.from_edge_based_node can be passed to that function.

Take a look at https://github.com/Project-OSRM/osrm-backend/blob/master/include/engine/routing_algorithms/routing_base.hpp#L422 for an example of what you do with the geometry_id once you have it.

[wangyoucao577]

@nnseva It's great to hear that you can help to implement this very useful feature.
I wrote some docs here, hope that can help you to understand the internals a little bit easier, FYI:

• Understanding OSRM Graph Representation
• OSRM toolchain files

On the other hand, for the map<pair<OSMNodeID,OSMNodeID>,OSMWayID> approach, I have implemented it by independent Golang service that stores the mapping in boltdb, see more in Telenav#257 (comment).
I agree with @danpat that it's not the best way to tackle this problem. But it's the simplest way without modify OSRM internals. It can be a gateway service that on front of osrm-routed to generate way_ids properly. I may need to re-organize the codes so that people can use it easier before you get this done in OSRM internal.

[danpat]

Indeed - here's a Javascript module that I wrote a long time ago that performs a similar job: https://github.com/mapbox/route-annotator

[nnseva]

Hi @danpat,

It looks like the geometry ID is not appropriate to index OSM Way ID because there are some geometries that may cross several ways.

I've found a place in the code where the geometry ID is generated. It is NodeBasedGraphFactory::CompressGeometry() method. (Almost) every circle through edge starting and ending geometry nodes generates a new geometry ID:

            auto packed_geometry_id = compressed_edge_container.ZipEdges(edge_id_1, edge_id_2);

At this place, I can calculate an original OSM Node ID there from from = nbg_node_u, and to = nbg_node_v node ids using the following code:

            const auto osm_from_id = GetOsmNodes().peek(from);
            const auto osm_to_id = GetOsmNodes().peek(to);

I've added a data structure and algorithms to collect and find OSMWayID using these OSMNodeIDs (for the beginning, I was trying to use a node ID pair of neighbor nodes as a map key to store the way ID, for the second, I was calculating intersection between way ID sets identified by a node ID of every node in the u->v pair).

Unfortunately, I've found, that not all, but some geometries created there, cross two ways (even more? probably)

Here I am applying the data file I was using to investigate the code.

singapore_291019.osm.pbf.zip

For example, one geometry ID is generated (using an applied file) for the u->v node pair (OSM ids) 6912865225->6912865211. Analyzing the original file, you can find that these nodes are not connected directly by the same way, but included in two different, directly connected ways instead:

  <way id="738264498" version="1" timestamp="2019-10-24T14:29:16Z" uid="7671560" changeset="76159526">
    <nd ref="6912865225"/> <!-- from -->
    <nd ref="6912865217"/>
    <nd ref="6912865220"/>
    <nd ref="6912865219"/>
    <nd ref="6912865218"/>
    <nd ref="6912865223"/>
    <tag k="highway" v="residential"/>
    <tag k="lanes" v="1"/>
    <tag k="maxspeed" v="50"/>
    <tag k="name" v="Tampines Street 44"/>
    <tag k="oneway" v="yes"/>
    <tag k="surface" v="asphalt"/>
  </way>
  <way id="738264499" version="1" timestamp="2019-10-24T14:29:16Z" uid="7671560" changeset="76159526">
    <nd ref="6912865223"/>
    <nd ref="6912865222"/>
    <nd ref="6912865214"/>
    <nd ref="6912865221"/>
    <nd ref="6912865211"/> <!-- to -->
    <tag k="highway" v="residential"/>
    <tag k="lanes" v="1"/>
    <tag k="maxspeed" v="50"/>
    <tag k="name" v="Tampines Street 44"/>
    <tag k="oneway" v="yes"/>
    <tag k="surface" v="asphalt"/>
  </way>

Do you have any ideas?

[danpat]

Yep - this is the point where I'd stop, and instead use an external indexing system :-)

You're right - "compatible" ways get merged during graph generation. The graph_compressor.cpp code is what does this.

The process is roughly as follows:

1. We parse the OSM file, and create a detailed in-memory graph containing an edge for every pair of coordinates, with properties on those edges.
2. We "compress" that graph by merging compatible edges (same name, other properties).
3. The compressed graph is then converted into the line graph.
4. We perform the graph speedup steps (contraction heirarchy, or MLD) on the line graph.

You will want to modify the edges inserted in (1) to add the way_id as a new property, then modify step (2) to consider the way id property when deciding whether to merge edges or not. You then need to ensure the new way ID property is propogated through steps (3) and (4).

[nnseva]

Hi @danpat,

it's a fine plan, but i'm afraid it will dramatically increase routing engine response time, because no any two ways will be compatible and compressed because of different way ids. Our team experimented before with name property adding there the way id. It slows down routing and even matrix response 2-3 times.

I see some '"segment" entity in the code. What is this, may I try to use it instead?

[danpat]

Well, you can't have your cake and eat it too unfortunately.

Another way to tackle this might be to take a similar approach to geometry - in the graph compressor, when two edges are merged, build up an array of the way IDs for all the merged edges, and store these arrays similarly to how we store geometry.

Two edges get merged here: https://github.com/Project-OSRM/osrm-backend/blob/master/src/extractor/graph_compressor.cpp#L310-L329

this is where the "compressed_edge_container" comes into play, holding all the properties that need to be kept, even though their parent edges are merged (e.g. the nodes along the way, the coordinates, etc).

[nnseva]

Hi @danpat,

Would it be useful to have information about the way direction also?

I've almost finished the implementation, and annotation will now provide way IDs along the found path. But the way direction is still unknown explicitly. If the way is two-directional, it might be not enough to have the only way ID, but the way direction is probably required also.

I propose to provide positive Way ID for segments with straight direction, and negative for segments with reverse direction. What do you think about it?

[MichalPP]

negative is sometimes (osm2pgsql) used to distinguish ways from relations (in order to save a column)

but OSRM does not work with relations when there is highway tag on relation, but not on relation elements (?). this tagging is not common now, but it can start to be common in future.

[SamuelBrucksch]

The ways annotation feature is something, that I need as well. Was there a reason to not merge this yet? Is the implementation finished and there was just no agreement so far if it's the right solution? Or why is that PR open so long now?

@nnseva is the code in a stable state, so i could cherry pick it into my own OSRM instance and use it without restrictions or is this still highly experimental?

Btw thanks for adding it, even if it will not make it into main, i should still be able to make use of your efforts, so thanks.

[nnseva]

@SamuelBrucksch as you can see in the discussion for my PR, it adds some significant (8-10%) amount of memory consumption by default. This behaviour was turned off by the additional command line arg.
People, able to approve PR, didn't like such a solution, and proposed the cmdline arg to opt in the feature.
I didn't like proposed (feature opt-in instead of feature opt-out) exception for the available annotation options.
It was a final misagreement, I switched to other projects and could not support this branch futher.
The annotation feature has a significant amount of potential customization capabilities although. It might be useful to have a separate annotation pipeline, where any, even scriptable, annotation keys may be introduced on the runtime stage. Then the existent annotations may appear as a part of such pipeline. Such a pipeline will give the full control of the annotation memory consumption to the user.

[nnseva]

The code was in stable state, but now it requires merging anyway @SamuelBrucksch

[SamuelBrucksch]

@nnseva thanks for answering. The tags from lua is actually something we want to achieve in the end. Right now we use an intermediate step via mapbox/route-annotator and i adjusted it, so we can feed the way IDs directly instead of the node IDs, which reduces memory consumption by more than half in the route-annotator, as we do not have to store the node pairs anymore. However I still think this is not such a nice solution and would preferibly get the tags from OSRM directly. I went through your PR and tried to do the same with data we took in the lua file, but it's quite complex and i'm a bit stuck now. You think you could help me a bit out here (if it's more time consuming with a monetary compensation of course). Let me know what you think, you can also respond to samuel@iternio.com, so we do not distract this issue too much.

[github-actions]

This issue seems to be stale. It will be closed in 30 days if no further activity occurs.