To generate partitions for our MLD implementation, we need to generate a set of partitions P1,..,PL with L equal to the number of levels and for all border vertices P_i \in P_{i+1}.

For the general algorithm, we can refer to http://sommer.jp/roadseparator.htm

Terminology

• partition: mapping V -> [1,k] for every vertex in the graph
• bisection: partition with k == 2
• cell: the set of v in V with the same mapping
• level: in a recursive scheme, this is the depth of the recursion

Recursive Bisection with Inertial Flow

We have had some experience with the inertial flow algorithm which @daniel-j-h implemented. The basic idea of the algorithm is to select nodes in geographic regions to the left/right side of the map and compute a minimal border in between. This create a bisection of the graph.

We reinterpret every partition as a new local graph and recursively apply the interial flow algorithm again.
Recursively cutting the partitions generated in a level l, we can generate level l+1 from it, adding an additional cut in every cell.

To implement this intertial flow partitioning scheme, we require an algorithm to compute the minimum cut between two sets of vertices (the source and the sink).

Finding Spatial Orders

One tool that we require for the inertial flow algorithm is to compute spatial orders.

@daniel-j-h already has a lot of experience here. http://daniel-j-h.github.io/post/selection-algorithms-for-partitioning/ is a nice source to refer to for how to implement this.

Multiple of these spatial orders will have to be compared for their partitioning result on every level. It might be possible to re-use these orders by doing some stable partitioning on them, accoring to our selection on cells.

For starters, I think we should be fine with doing local partitionings on every level, since we are bounded by n log^2(n) here, so the overhead should be negligible in relation to the overhead for the flow algorithm itself.

Tool: Dinics algorithm

One important constraint we can apply is that we don't care about weights or in terms of flow algorithms about capacity. We only care about the minimum number of border vertices.

This allows us to use unit capacities in the flow algorithm for which Dinics algorithm (see paper) offers rather good performance. Flow algorithms in general will remain a big part of the running time though, since even the unit capacities only offer a running time guarantee of (min(V^{2/3},E^{1/2})*E) which in our case with E ~ 4*V would be sqrt(E) * E.

Items to consider:

• memory overhead (we will require a lot of recursion -> copying the graph everytime will be too much)
• parallel execution
• dealing with components

Graph View

To avoid copying the graph, we can use a graph view based on the previously generated output. Such a graph view needs access to the partitions generated so far and will simply restrict all process transparently into smaller subsets

What I imagine is the following:

We start off with a list of vertices [1,...,n] (node array) and a list of their partition IDs (the final output) of [0,...,0] (cell id array).
Each level of inertial flow computations will generate a bisection into a left hand side (0) and a right hand side (1).

So assuming we have the nodes [1,2,3,4,5,6] and partition them according to [0,0,1,1,0,1], we can shuffle the nodes array to [1,2,5,3,4,6]. We can then recursively call the partitioning with the subarrays [1,2,5] and [3,4,6].

When generating the next level, we could end up with [1,0,1] and [0,0,1] for the both subarrays, augmenting our partitioning array to, using the array we partition as an index.
[01,00,10,10,01,11]. The final output of the recursive scheme will be the list of indices.

The additional memory overhead to store/localise everything is two integers per node + the additional overhead used in dinics algorithm.

The flow algorithm can be initialised by using the node array to select nodes and output can be written to the cell id array without conflict, since the different cells are distinct.

A graph view can utilise the cell id array and only consider vertices of/edges between appropriate cell ids.

In total, the only thing that should classify a graph view is the range of nodes in the node array and the partition_id used in the cell id array. Apart from this, the graph view should not have to hold any state and should be immutable.

Computing Flows on a graph view

The flow algorithm requires a residual graph. Luckily we already have reversed edges for every edge in the graph, allowing to store flags per edge.

From chat with @daniel-j-h, we should be able to completely hide the details of how the view works from the partitioner, pretending to only offer a simple graph.

There is some very slight overhead in lower levers for the internal state, since some of the edges in the local view are hidden behind abstractions, but it is only relevant for border edges.

Such a graph view should be enough to result in low memory overhead.

Parallel Execution

The structure of the graph view allows work to be parallelised freely, as long as the global view is only touched when combining all results of a cell (to begin with the entire graph) of a level and stepping down a level. Work in different cells of the graph is completely independent and does not require synchronisation.

We have two ways of parallelising:

• within a single cell: the interial flow requires to generate multiple possible cuts. We can compute bitsets of lhs/rhs values for different geometric orders in parallel. It requires to hold the internal state of our flow algorithm for every thread.
• between cells. Every cell can be computed independently, this even holds between levels.

Components

Not all components are necessarily partitioned in a fair way. If we consider SCCs in our routing algorithm, we can classify three types of partitions:

• Large Components
• Small Components that can only be reached from a large component
• Small Components that cannot be reached from a large component
• Disconnected Small Components

For the small components, I would propose to handle all edges as bidirectional. This would reduce our problem to large Components and disconnected components.
There is a minor downside here, since distance matrices in MLD need not be quadratic but rather should be sized m*n for m entry and n exit locations. Treeting all edges bidirectional would not prefer unidirectional edges over bidirectional edges, but this should be a minor problem.

Disconnected components should probably be grouped into a single partition that is only used to compute shortest paths directly. This cell can be integrated as child of any other cell without connections to the side. We just should make sure not to consider these disconnected parts when updating metrics.

Large Components are problematic, since we cannot partition all cells to the same amount of levels. We need to adapt the output of our partitioning scheme to offer a reasonable scheme to fit the MLD paradigm. It should be alright to have the cell on level L to be equal to the cell on level L+1. This would introduce some minor memory overhead, but it might be possible to handle these situation without additional overhead.

Creating more Components in Partitioning

When we partition the graph, we might create new components in the local graph views. This does not pose a real problem though, since MLD does not require cells to be connected at all. A cell that is in parts in the USA and in parts in Siberia would be ok.
We can use these disconnected components to balance our recursive steps a bit better.

The partition to be chosen for a recursive step can be chosen among the O different spatial orders by the number of cut vertices and by its balance.

Directed vs undirected graphs

Our goal should be to optimise for the minimum number of border nodes. However, the basic flow algorithm will minimise the number of border arcs. If we, at some point, transfer a node-based partition into a edge-based graph, we will get a minimum number of nodes.

Since it does not matter if a road is bidirectional or unidirectional to classify a node as border vertex, we can consider the graph as undirected to compute the minimum cut. This reduces the number of components at the same time.

Next Steps

Personally, I do see the following items as next steps:

• spec out an interface for the graph view
• spec out an interface for Dinics algorithm
• spec out an interface for the Intertial Flow algorithm
• decide on how to handle components