Write preprocessed edge-based graph in osrm-extract or osrm-partition

[oxidase]

Added in #3765 edge-based-graph edges loading requires graph pre-processing using functions partition::splitBidirectionalEdges and partition::prepareEdgesForUsageInGraph. Loading of an EBG file should be adjusted in osrm-contractor, osrm-partitioner, osrm-customizer and osrm-storage.

The preprocessing should be moved into Extractor::WriteEdgeBasedGraph or in osrm-partitioner:

• saving in Extractor::WriteEdgeBasedGraph has downside that osrm-contractor uses only forward edges
• saving in osrm-partitioner has downside that two EBG files must be created, one for osrm-contractor and another for MLD tools

[daniel-j-h]

Related: check out the graph contractor doing the same here

https://github.com/Project-OSRM/osrm-backend/blob/master/src/contractor/graph_contractor.cpp

and before we split edges here

https://github.com/Project-OSRM/osrm-backend/blob/master/include/contractor/graph_contractor_adaptors.hpp

getting called here on the edge list

https://github.com/Project-OSRM/osrm-backend/blob/264cec12e9344599ec4edfe77d4724858e2391c9/src/contractor/contractor.cpp#L395

[TheMarex]

Currently we handle this by writing out an own graph mldgr after osrm-customize. This works toolchain wise, but adds unnecessary overhead for IO.

I have been thinking a little bit on how to address this and I think the most efficient way would be to save the graph as adjacency array (StaticGraph like encoding) at the end of osrm-extract. There are a few things this needs to be able to works:

1. We need unified graph loading/serialization for osrm-extract, osrm-contract, osrm-partition and osrm-customize, osrm-routed. All need the same graph but with slight variations on the data structure:
   • extractor only needs to write, does not actually use any queries on the EBG (yet)
   • contractor needs to load, update the weight and then modify the graph. So we need a way to load the graph from the file and create a DynamicGraph for GraphContractor in an efficient way. GraphContractor creates a list of edges again and then creates a graph again that goes on disk: this logic should be refactored because creating a graph from a list of edges is already handled by StaticGraph and DynamicGraph.
   • customizer needs to load, update the weights, but not modify the graph. This needs to create a StaticGraph from the graph file.
   • partition only needs the structure of the graph: We don't actually need to have any edge data in memory. Currently we also don't modify any of it, so it should be a StaticGraph. (could change)
   • engine needs the graph with edge-weights but does not modify it. Bonus point: Graph needs to be non-owning since we use shared memory as backing store, so this is a StaticGraphView.
   • updater doesn't modify the graph structure but needs access to the data
2. updater should not do the graph loading: What kind of graph data-structure we need is based on who uses the graph.
3. updater code should be adapted to work on a real graph not an edge list. After the refactor that landed in #3737 this should be straight forward: The turn_id is the only data element we need to extract from the graph to re-compute the weight/duration of every edge.

To summarize we need to come up with a storage that allows the following things:

1. Load graph into StaticGraph (customizer, engine, partition)or DynamicGraph (contractor) from the file
2. Load data conditionally
3. Support more then one weight layer per graph (needed for multi-metric)

[TheMarex]

This issue is very relevant now that we support updating the metric independently. By making the graph topology static for MLD we can reduce the memory usage for data update even further. Weights make up at least 1/3 of the .mldgr file, so we can reduce the memory usage by another 20%.

The current memory needed to update the metric breaks down as follows:

File	Size	Percentage
.osrm.mldgr	381,368,832	~30%
.osrm.cell_metrics	512,986,112	~41%
.osrm.datasource_names	69,632	~0.0056%
.osrm.geometry	293,922,816	~23%
.osrm.turn_weight_penalties	22,256,640	~1.8%
.osrm.turn_duration_penalties	22,256,640	~1.8%

[github-actions[bot]]

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