Dijkstra: local search and internal data structure control

[Becheler]

Story

addy90 runs map matching at scale: hundreds of millions of short-range Dijkstra queries over a 60M-node Germany road network. He identified two concrete performance killers.

1. dijkstra_shortest_paths_no_init still allocates a full-size array. On a 60M-node graph, this single allocation dominates runtime for a search that only touches a few hundred nodes.
2. all internal maps (distance, color, predecessor, heap index) are sized to the full graph even when the search radius covers only a tiny local region. His fix: replace vectors with flat_map, track only visited vertices in discover_vertex, clean only those on reset. This reduces working memory from O(|V|) to O(search radius): huge improvement for local search.

andreacassioli at Maersk has the same use case: short-range routing queries over large road networks, millions of times per day.

jcelerier (OSSIA) confirmed the same problem from a real-time audio perspective: hidden allocations inside algorithms are a correctness issue, not just a performance one.

addy90's solution:

// track only visited vertices
void discover_vertex(vertex_descriptor& v, const graph_type&) {
    visited_.push_back(v);
}

// clean only what was touched
for (const auto& v : visited_) {
    put(predecessor_map, v, v);
    put(distance_map, v, inf);
    put(color_map, v, white);
    put(heap_index_map, v, 0);
}
visited_.clear();

Dream solution

Dijkstra's internal data structures are injectable via policy or template parameters. A flat_map-backed variant exists out of the box for local searches. dijkstra_shortest_paths_no_init truly skips all initialization including the hidden array allocation. The combination makes BGL viable for map matching, logistics routing, and any application running millions of short-range queries.

Starting point

addy90's full writeup in discussion #466
jcelerier's writeup in discussion #466
dijkstra_shortest_paths.hpp line 242
dijkstra_shortest_paths.hpp line 360
Boost.Container flat_map
allocator card

Intermediary objective (45 min)

Read addy90 and jcelerier's writeups. Read the source at the links above. Then answer questions in writing:

1. What would a user need to control to make local search fast and allocation-free?
2. What exactly does BGL allocate internally when running Dijkstra, and where?
3. What are the possible designs that could give users that control, and what are the tradeoffs of each?
4. Can you share a code snippet on Compiler Explorer that does not compile but that you would like to compile ?

Note that #481 covers a related problem. Make sure you are at least a bit aware of it and note conflicts or overlaps.

[andrea-cassioli-maersk]

The issue is relevant for large graphs and/or time critical sensitive applications.

I see two possibilities

1. make sure all the temporary data structures are injected and left to the user to detect what needs to be initialised. this way the search is allocation-free and all in the hands of the user. However it might expose data structure the average user would not want to deal with.

2. make possible to inject previous search state, that can be used internally to only initialise what s really needed.

Not sure what to advise. From a user perspective, both ways might be cumbersome.

Maybe point 2 could open up a general approach to inject state to restart algorithms for instance.

[pratzl]

To support flat_map it would be the same for map. I think it's possible to create an adaptor with specializations that presents a common interface. The specializations would exist for vector and flat_map. This is an interface change, so it might be easier to just add overloads to use it, with the consequence of doubling the number of function interfaces.