Make Graphs Actual Containers

[MoKob]

During the work on partitioning, we got caught up in some side-effects of adding logic to our graphs that I feel does not belong in there.

One example is the data field for which @daniel-j-h already proposes https://github.com/Project-OSRM/osrm-backend/issues/3642.

Other parts are the general forced access patterns using IDs that require you to loop over IDs (e.g. getAdjacentEdgeRange and from the IDs refer to the edges with GetData(ID).

I would like to rip out these graphs (and their added logic) for a simpler implementation that only exposes the simpler (and common in the literature) G=(V,E) structure - i.e. a set of vertices and edges.

One example is already available in the branch for partitioning.

Why is it beneficial:

• EdgeIDs are consecutive anyhow. Using direct iterator access allows for better optimisation (e.g. possible prefetching). Using EdgeIDs we have an indirection that might prevent the compiler from optimising
• Increased flexibility: Right now we force fields like data to the edges and require GetEdgeData(eid) to access edge.data. Any graph that we build requires such a data field (which is not always the case, see partitioning)
• Graph access is more fun: for( const auto &node : graph.Nodes() ){ for( const auto &edge : graph.Edges(node) ){ std::cout << "Edge: " << edge.target; }} and direct (instead of using two IDs (node + edge)).
• Adaption into C++/Boost algorithm gets easier (e.g.)

Comparison For Edges:

https://github.com/Project-OSRM/osrm-backend/blob/master/include/engine/routing_algorithms/alternative_path.hpp#L153-L181

const auto relax_edge = [&](const Edge &edge) {
    if( !(search_forwards ? data.forward : data.backward) )
        return;
    // New Node discovered -> Add to Heap + Node Info Storage
    const EdgeWeight edge_weight = data.weight;

    BOOST_ASSERT(edge.weight > 0);
    const EdgeWeight new_weight = weight + edge.weight;
    if (!forward_heap.WasInserted(edge.target))
    {   
        forward_heap.Insert(edge.target, new_weight, node);
    }       
    // Found a shorter Path -> Update weight
    else if (to_weight < forward_heap.GetKey(edge.target))
    {   
        // new parent
        forward_heap.GetData(edge.target).parent = node;
        // decreased weight
        forward_heap.DecreaseKey(edge.target, new_weight);
    }       
};

boost::for_each(graph.Edges(node), relax_edge);

We could even think of using boost filter iterators to allow filtering for forward edges directly.

Implementation

In a first step, we could transform the static_graph / dynamic graph into wrappers that hold a new graph and mimic the old interface (kind of what GraphView does in partition (see here)).

referencing / https://github.com/Project-OSRM/osrm-backend/pull/3558/files#r103703294

[daniel-j-h]

:+1: for having nice interfaces for our graphs; the partition graph was a pleasure to work with.