Design: connection planning¶

This is the agreed design for ConnectionPlanner, which plans how to connect a set of points (schools, clinics, villages) to an existing network (fibre, a power grid, water mains) along a spatial network at the smallest shared cost. It records the decisions from the design round of 30 October 2026 and splits the work into sub-tasks. Each sub-task starts by reading this document, the glossary, ADR 0004, ADR 0008, and the spatial network design.

This page is not in the docs site navigation. The user-facing description will be in the spatial networks concept note, and the evidence in design and algorithm decisions.

1. The problem¶

Given a spatial network with a non-negative weight on every edge, a set of terminals that must be connected, and a set of roots that are already connected to each other through an existing network, find the set of edges of smallest total weight such that every terminal can reach some root. A terminal may reach a root directly or through other terminals, and an edge used by several terminals counts once.

Joining every root to one virtual root at weight 0 makes this the Steiner tree problem in graphs over the terminals and the root (ADR 0008). Removing the root from the tree leaves a forest whose every tree contains at least one root.

• Directions are ignored. A cable or a duct does not follow one-way streets.
• The cost is per edge used, paid once. That is trench length, or a cost per metre of trench through weight=. A cost per cable, which grows with the number of terminals behind an edge, is out of scope: it makes the problem fixed-charge network design.
• The roots are one backbone. Reaching any root is enough. Separate networks, each terminal assigned to one of them, are deferred.
• No roots gives an unrooted Steiner tree joining the terminals, as connecting_subnetwork(terminals) does today.

Complexity: NP-hard, and NP-hard to approximate within 96/95. The best known approximation is ln 4 + ε ≈ 1.39 (Byrka et al., 2010), through large linear programs. Mehlhorn's algorithm gives at most 2(1 − 1/ℓ) times the optimum for ℓ leaves in O(m + n log n), and is within a few percent in practice. SCIP-Jack solves instances of a few hundred thousand edges exactly, typically in minutes.

On the concept note's example (197 schools and 5 fibre nodes in Kigali, on Rwanda's roads):

The rooted tree was computed with today's code by joining the fibre nodes with zero-length edges; it took 0.19 s.

2. Names and modules¶

The docs use fibre as the main example, but the names and docstrings stay generic, so the planner reads as naturally for a power grid or water mains.

3. API¶

planner = ConnectionPlanner(
    network,                    # a SpatialNetwork, with terminals and roots already inserted
    terminals,                  # node IDs to connect
    roots=(),                   # node IDs already connected to each other
    weight=None,                # edge column to minimise; the network's weight otherwise
    bridge_cost=None,           # weight per metre of a straight-line link; no bridges when None
    bridge_max_distance=5000,   # metres
)
plan = planner.plan(method="shortest_path")  # or "steiner", "nearest_root", "all_pairs"
plan = planner.improve(plan, time_limit=None)
bound = planner.lower_bound(time_limit=60)   # also sets plan.bound and plan.gap when given a plan

SpatialNetwork.connecting_subnetwork(terminals, roots=None, method="steiner", weight=None) builds a planner and returns planner.plan(method).network. Its sources= parameter becomes roots=, and method="nearest_source" becomes "nearest_root"; neither is released yet.

Inputs are node IDs of the network. Inserting points is the user's step (insert_points, then plan), so insertion's options and its skipped points stay visible. A root that is also a terminal is connected from the start. Unknown IDs raise KeyError. Weights must be present on every edge and not negative; zero is allowed.

ConnectionPlan¶

Order and marginal cost come only from shortest_path. A Steiner tree's shared trenches have no natural per-terminal marginal cost, and a made-up one would mislead.

4. The rooted Steiner tree¶

The adjacency matrix of the undirected network (_graph(weight, directed=False)) gets one extra node, the virtual root, joined to every root node. scipy's minimum spanning tree drops zero entries, so these joins get the smallest positive float, as zero weights already do. Mehlhorn's routine then runs unchanged with terminals ∪ {root}:

1. One multi-source Dijkstra from terminals and root gives every node its nearest terminal. Because the virtual root is joined to every root node at (almost) zero, its Voronoi region is everything nearer to some root node than to any terminal.
2. Edges between regions give candidate links; an MST over the cheapest link per pair of regions picks the pairs.
3. The links are expanded into paths, a second MST removes cycles, and leaves that are neither terminals nor the root are pruned.
4. The root and its joins are removed. What is left is the plan's edges.

The cost is the same as today's Steiner tree: one Dijkstra and two MSTs over a matrix with one more row.

5. The rollout order (method="shortest_path")¶

Takahashi and Matsuyama's heuristic, a 2-approximation, is the planner's model of a phased rollout. Start with the roots as the connected set. Repeatedly connect the unconnected terminal nearest (by weight) to anything connected so far, along its shortest path, and add that path to the connected set. A terminal's order is when it was connected, and its marginal_cost the weight of its path, which uses only new edges. Ties go to the terminal listed first, so plans are reproducible. Terminals that the connected set cannot reach are unreachable.

Implemented incrementally:

• One multi-source Dijkstra from the connected set gives every node its distance to it.
• After each addition, distances can only fall, and only near the new path. A Dijkstra from the new path's nodes, limited to the largest distance of any unconnected terminal (limit= in scipy), updates them. Nodes beyond the limit cannot become any terminal's best connection.
• Terminals are kept in a heap by distance.

Sub-task 3 benchmarks this against the naive version (one full Dijkstra per terminal), and against a version that recomputes only when the nearest terminal's distance changed. A compiled Dijkstra would need a new build dependency and is not planned.

As built (benchmarks/connection_planning/rollout.py, results in benchmarks/connection_planning/results.md):

• Ties go to the terminal listed first in terminals, not the lower ID: IDs may mix integers and text, which do not sort, and the order given is as reproducible. Without roots, the rollout starts from the first listed terminal it can connect, with order 1 and marginal_cost 0. A terminal that is a root has order 0; an unreachable one has none.
• The update is a pruned Dijkstra in Python, not scipy's limited one. The limit above is the largest distance of any waiting terminal, which a few remote terminals keep at tens of kilometres, so each update searched about 40,000 nodes. Only nodes nearer to the new path than to anything connected before need updating, and a Dijkstra that stops wherever a distance does not fall searches only those: 6 million node updates in a whole 10,000-terminal rollout on Rwanda, against 455 million nodes searched. scipy's Dijkstra cannot stop that way, but even in Python the pruned update is much faster:

• The version that recomputes only when the nearest terminal's distance changed is not valid. Stale distances are upper bounds, since distances only fall, so the top of a heap of stale distances need not be the nearest terminal. It would need lower bounds, which the problem does not provide.
• On Rwanda the rollout was shorter than Mehlhorn's rooted tree: 1,163 against 1,194 km for 100 terminals, 3,845 against 3,942 km for 1,000, and 10,760 against 10,954 km for 10,000, 1.8 to 2.6% shorter. Both are 2-approximations, and Takahashi and Matsuyama's is known to be the better of the two in practice. steiner stays the default for now, since it takes 0.2 s against 1.1 s; sub-tasks 4 and 6 measure both against the optimum before deciding.

6. Bridges¶

With bridge_cost=c, the planner may use straight-line links between the network's connected components, for terminals that no road connects to a root: microwave, wireless, or a planned road.

• Candidates are found with a KD-tree on all nodes, on the unit sphere as connect_components does: for each component, its nearest node pairs to up to 5 other components within bridge_max_distance.
• Each candidate gets the weight c times its great-circle length in metres, in the units of weight, and is added to the planner's internal network with kind="bridge" and a straight-line geometry.
• Only links between components are offered. Within a component, the roads already connect.
• The Steiner tree uses a bridge only when it is cheaper than the alternatives. A terminal unreachable even with bridges is unreachable.

As built:

• A component with more than 2,000 nodes, or most of the network, gets its own KD-tree, queried once with every node outside it, as connect_components does. That gives its closest pair to every other component exactly. Smaller components query the KD-tree of all nodes with their nodes' 16 nearest neighbours, doubled while none lies outside the component and the farthest is within bridge_max_distance. The closest pair per pair of components is kept, and each component keeps its 5 nearest. On Rwanda's roads cut in two along a meridian (23 components, two of 70,000 and 55,000 nodes), finding the candidates takes 0.1 s.
• Bridges join the planner's graph as extra entries, not as a new SpatialNetwork, so offering them costs no copy of the tables. A bridge's length stays its great-circle length; its weight is bridge_cost times that, stored in the weight column unless the weight is length. cost and distance always count bridges at their weight.
• Bridge ends are kept as nodes when the plan is contracted, so a bridge stays one edge of kind bridge in plan.network.
• bridged is whether a terminal's path to its root along the plan crosses a bridge. Without roots, it is whether the terminal lies outside the road component that holds the most planned terminals.

A network loaded through OSMRoadsHandler keeps only its largest connected part by default, so bridges matter for networks loaded with retain_all=True, combined with concat, or clipped.

7. Local search (improve)¶

improve(plan) applies two of Uchoa and Werneck's moves until neither improves the plan or time_limit passes. Neither ever makes a plan worse.

A key vertex is a node of the tree that is a terminal, a root, or a Steiner node of degree 3 or more; a key path is a path of the tree between two key vertices whose inner nodes are Steiner nodes of degree 2.

• Key-path exchange. Remove one key path; the tree falls into two parts. Find the cheapest path joining the two parts, with a Dijkstra from one part limited to the removed path's weight. If it is cheaper, replace the key path with it.
• Key-vertex elimination. Remove one Steiner key vertex and its key paths; the tree falls into three or more parts. A multi-source Dijkstra labelled by part, as in Mehlhorn's algorithm, gives the cheapest links between parts, and an MST over them reconnects all parts. If the reconnection is cheaper than what was removed, keep it.

Moves are tried cheapest-to-evaluate first (key paths in decreasing weight), and each Dijkstra is limited by the weight it must beat, so most searches stop early. Vertex insertion and elimination are deferred, until real data shows a large remaining gap. Sub-task 6 found none on roads: improved plans were within 0.86% of the optimum on Kigali.

As built (benchmarks/connection_planning/improve.py):

• The plan is rebuilt as one tree first. With roots, the virtual root is joined to every root the plan touches, and a spanning tree with pruned dangling branches is taken. This alone never costs more, and turns a nearest_root or all_pairs plan, which may hold cycles, into a tree.
• Key paths are listed once per pass. An earlier move can leave a listed path's end only continuing it; such a path is extended to the next key vertex before it is tried, and paths whose edges are gone are skipped.
• Key-vertex elimination searches only near the removed nodes: its links start from the parts' nodes within the removed weight of them. Searching from every node left in the plan took 20 ms per vertex on Rwanda; the local search found plans within 0.01% of it on Kigali, in half the time.
• A move must save a billionth of the weight it replaces, so rounding cannot make it loop.
• On Rwanda with 1,000 terminals and 20 roots, a pass takes 5.8 s from steiner, and the plan improves 4.7%, from 3,942 to 3,755 km. From shortest_path it improves 2.2%, and from nearest_root 31.8%. All three end within 0.1% of each other, so with improve() the choice of first method matters little.

8. Lower bound (lower_bound)¶

Wong's dual ascent (1984) gives a lower bound on the optimum, and with it the gap of any plan.

• The undirected network becomes a directed one with both directions of every edge, rooted at the virtual root (or at one terminal when there are no roots). Each arc starts with its weight as its reduced cost.
• Repeatedly, pick a terminal that cannot yet be reached from the root along arcs of reduced cost 0, and the set of nodes that reach it along such arcs. Raise the bound by the smallest reduced cost of the arcs entering that set, and lower those arcs' reduced costs by it.
• Stop when every terminal is reachable along arcs of reduced cost 0.

The sum of the raises is a lower bound on the optimal tree's weight. Each round costs a search over arcs of reduced cost 0, and the number of rounds can be large, so time_limit stops early and returns the bound reached so far, which is still valid, only looser. Terminals unreachable from the root are left out of the bound and reported.

As built (benchmarks/connection_planning/bound.py):

• Wong's rule chooses the terminal. Every step, the active terminal whose region (the nodes that reach it at reduced cost 0) has the fewest entering arcs raises the bound by their smallest reduced cost. A first version gave each terminal one whole turn, until its region held the root, nearest the root first; it was valid but much weaker. Against SteinLib's proven optima its bound was on average 9.7% below the optimum on set C, at worst 45%, against 0.42%, at worst 3.1%, for Wong's rule; on Rwanda with 1,000 terminals it left a gap of 10.9% to the improved plan, against 1.4%.
• Regions are kept between steps. Reduced costs only fall, so a region only grows. Each terminal keeps its region and its entering arcs, and a step checks only those arcs for any that reached 0, growing the region from their tails. Recomputing each region every step gave the same bounds and took 41 s for 100 terminals on Rwanda, against 1.5 s.
• A complete bound is kept by the planner, so the gap of every later plan costs nothing. A bound stopped by time_limit is still valid, only looser, and is recomputed on the next call.
• On Rwanda with 20 roots the bound takes 1.7 s for 100 terminals, 5.0 s for 1,000, and 40.5 s for 10,000. Improved plans have gaps of 2.1%, 1.4%, and 0.6%.

9. Edge cases¶

• No roots: the unrooted tree over the terminals.
• One terminal and no roots: an empty plan.
• A terminal that is a root: status="root", distance 0.
• A terminal unreachable, even through bridges: status="unreachable", left out of the plan and the bound.
• Weights: zero allowed, negative or missing refused with ValueError, as the algorithms do today.
• bridge_cost set without any component to bridge: no bridges, no warning.

10. Performance targets¶

On Rwanda's simplified network (125,058 nodes, 332,535 edges), with 1,000 terminals and 20 roots, on the benchmark laptop:

11. Validation¶

• Tests. The rooted tree against networkx's steiner_tree on the virtual-root graph; every method on small graphs against brute-force optima; improve never worse, and better on constructed cases; the bound never above the brute-force optimum; and every edge case above.
• Benchmarks. benchmarks/connection_planning/ writes instances in SteinLib's STP format and solves them exactly with SCIP-Jack, which is installed only there, never as a dependency. Instances: Kigali, and Rwanda with 100 and 1,000 terminals, by length and by cost. Reported for each method: its gap to the optimum, with and without improve; and the bound's gap. If SCIP-Jack cannot be built, networkx's steiner_tree gives another upper bound, and the planner's own bound the lower one.

As built, without SCIP-Jack, whose source code must now be requested from its developers:

• SteinLib's sets B, C, D, and E (78 random sparse graphs of 50 to 2,500 nodes, every optimum proven; steinlib.py). Improved plans were on average 0.4 to 2.2% above the optimum, at worst 9%; the bound was on average 0.05 to 0.42% below it, at worst 4.4%. The first version of the dual ascent was 7 to 10% below on average, at worst 45%, which led to Wong's rule in sub-task 5.
• Exact optima on Kigali's roads with scipy's milp (HiGHS) and the multi-commodity flow model, whose relaxation equals the directed cut relaxation (exact.py; 30 and 60 terminals, 3 roots, 5 draws each, 4 to 110 s each). Improved plans were 0.00 to 0.86% above the optimum, shortest_path 0.65 to 5.9%, steiner 3.0 to 8.8%, and the bound 0.07 to 1.1% below. The single-commodity flow model did not solve such an instance in 600 s.
• Rwanda is too large for HiGHS; there the bound alone gives the gap: 2.1%, 1.4%, and 0.6% for improved plans of 100, 1,000, and 10,000 terminals.
• The default method became shortest_path. Without improve() it was about twice as close to the optimum as steiner, on Kigali and on SteinLib, and it still takes seconds at country scale (4.4 s for 10,000 terminals on Rwanda, against 0.2 s). After improve(), both end within about 0.1% of each other.
• exact.py also writes its instances in SteinLib's STP format, with the virtual root as the last node, so an exact solver can take them as they are; exact.py --rwanda 100 1000 10000 writes Rwanda's instances of bound.py without solving them.

12. Sub-tasks¶

Each sub-task is its own pull request on feat/connection-planner, stacked on #21.

13. Deferred¶

• Prize-collecting plans (prizes=, a value per terminal such as its pupils): connect only the terminals worth their cost, or the most value within a budget. Goemans and Williamson's 2-approximation, with Hegde, Indyk, and Schmidt's nearly linear version (pcst_fast), fits the planner's virtual root.
• Capacities (demands= per terminal, capacities= per root): the capacitated Steiner tree, with the capacitated shortest-path heuristic (PLOS One, 2022); and Ito, Zhou, and Nishizeki's partitioning of a tree among capacitated roots as a second stage.
• Separate root networks, each terminal assigned to one.
• Cost per cable: fixed-charge network design or buy-at-bulk.
• Vertex insertion and elimination in improve. On SteinLib's dense random graphs the improved plans were up to 9% above the optimum, so these moves would help there; on roads, within 0.86%.
• SCIP-Jack as an exact column in the benchmarks, once its source code arrives from its developers: exact optima for the Rwanda-scale instances that HiGHS cannot solve, from the STP files exact.py writes.

14. Why "roots"¶

The existing network's nodes are called roots, not sources. "Source" is already a glossary term: the place a dataset is requested for (a country, a geometry, points, a frame), which every handler and fetcher uses. Using it for fibre nodes would give one word two meanings in the same library. "Root" is the Steiner literature's term and matches the virtual root the roots join. connecting_subnetwork's sources= and method="nearest_source" become roots= and "nearest_root" in sub-task 1, before their first release. "Anchors" and "connected nodes" were considered and rejected as less precise.

15. References¶

• Mehlhorn, K. (1988). A faster approximation algorithm for the Steiner problem in graphs. Information Processing Letters 27(3).
• Takahashi, H., and Matsuyama, A. (1980). An approximate solution for the Steiner problem in graphs. Math. Japonica 24.
• Wong, R. T. (1984). A dual ascent approach for Steiner tree problems on a directed graph. Mathematical Programming 28.
• Uchoa, E., and Werneck, R. F. (2012). Fast local search for the Steiner problem in graphs. ACM Journal of Experimental Algorithmics 17.
• Byrka, J., Grandoni, F., Rothvoß, T., and Sanità, L. (2013). Steiner tree approximation via iterative randomized rounding. Journal of the ACM 60(1).
• Gamrath, G., Koch, T., Maher, S., Rehfeldt, D., and Shinano, Y. (2017). SCIP-Jack: a solver for STP and variants with parallelization extensions. Mathematical Programming Computation 9.
• Hegde, C., Indyk, P., and Schmidt, L. (2015). A nearly-linear time framework for graph-structured sparsity. ICML.
• Ito, T., Zhou, X., and Nishizeki, T. (2005). Partitioning trees of supply and demand. International Journal of Foundations of Computer Science 16(4).
• A construction heuristic for the capacitated Steiner tree problem (2022). PLOS One.