optiwindnet.clustering

Module Contents

optiwindnet.clustering.clusterize(A: networkx.Graph, capacity: int) → list[set[int]]

Partition the terminals of A into one cluster per root.

Clustering never costs the location a feeder:

Σ_c ceil(T_c / capacity) == ceil(T / capacity)

Several clusters may hold a partly filled feeder, as long as their remainders together need no more feeders than they occupy.

Terminals start at their closest root (distance measured in P_paths - see mesh.make_planar_embedding()), which minimizes the total terminal-to-root distance but may waste up to R - 1 feeders. The wasted feeders are then shed: each way of doing so is a feeder budget (few of them, the waste being at most R - 1), and _assign() deals the terminals out exactly for each. The cheapest one wins.

That distance is only a proxy for cable length – it has each terminal reach its root alone, which is what the routers avoid – so optimizing it harder does not pay off.

A cluster is empty iff its budget is zero, which happens when no terminal is closest to that root, or when the feeders are too few to go around (ceil(T / capacity) < R), or when draining the root is simply cheaper. Callers must handle a root with no terminals.

Parameters:

• A – available-edges graph, needs graph attributes R, T and d2roots

• capacity – maximum number of terminals a feeder may serve

Returns:

One set of terminals per root, in root order (-R to -1).