Boundary nodes in edge-based graph partitioning

[oxidase]

From the review discussion #4558 about using both forward and reverse phantom nodes to check a node MLD level

if you know of a reason we do not keep a single nbg edge in a single cell. Separating a single edge logically into two different cells seems like a strange concept to me and something we might need to rethink.

... . The reason for doing that is in using an NBG partition to make an EBG one with some heuristics how to place EBG boundary nodes in cells and this potentially could lead to the situation "Separating a single edge logically into two different cells". This is not really optimal as also can result in "invalid" boundary nodes that neither sources nor destinations, but number of such nodes is vanishingly small.

The current partitioning can be illustrated for https://github.com/Project-OSRM/osrm-backend/blob/fee2e9f1209bd4b0758d287ce18d1433e3f5153e/features/testbot/multi_level_routing.feature#L41-L49

On the level 1 there are 4 cells that are encoded as 4 different background colors of EBG node IDs. The text color of EBG node IDs is green for forward nodes and red for reverse nodes:

For example nodes 3, 4, 5, 22, 23, 24, 25 are in "yellow" cell and 6, 7, 8, 12, 13, 14, 26, 27 are in "green" cell. EBG nodes 5 and 6 share the same geometry of the same NBG edge and are in different MLD cells.

This aim of the issue is to illustrate the current partitioning and for discussion of partitioning potential improvements for EBG graphs.

/cc @MoKob

[mjjbell]

Interesting to read these discussions from back in the day.

I stumbled across this as I've noticed the heuristic choice makes it more difficult to parallelise an isochrone search of the MLD cell hierarchy.

In an isochrone search we're interested in whether the geometry is visited. So in OSRM's edge-based graph, to validate that a geometry is unvisited, we may have to identify and check a cell adjacent to our current context to find the reverse edge. This can blunt some of the range query optimisations that narrow down the cells of interest.

(There's also an issue around EBG nodes with connected geometries but no connecting EBG edges not being boundary nodes, but that's not due to the heuristic).

Changing the heuristic to instead select the same partition for all EBG nodes of the geometry would fix this, but I can see some discussion around disconnected nodes in #3826 where the current heuristic was implemented that I'd need to fully understand, in addition to regression testing the change.