optiwindnet.heuristics

Package Contents

optiwindnet.heuristics.constructor(Aʹ: networkx.Graph, capacity: int, method: str = 'rootlust', *, rootlust_: tuple[float, float] | None = None, maxiter: int = 10000, bias_margin: float | None = None, weigh_detours: bool = True, straight_feeder_route: bool = False, keep_log: bool = False, blockage_link_cos_lim: float = 0.85, blockage_link_feeder_lim: float = 2.0, blockage_subtree_feeder_lim: float = 2.5) → networkx.Graph[source]

Create a network using a constructive greedy heuristic.

The overall structure of the constructive algorithm is based on:

Esau, L. R., and K. C. Williams. “On Teleprocessing System Design,

Part II: A Method for Approximating the Optimal Network.” IBM Systems Journal 5, no. 3 (1966): 142–47. https://doi.org/10.1147/sj.53.0142.

However, this implementation uses the extended Delaunay triangulation (given in A) as the base connectivity, and implements terminal-terminal crossing prevention. This means that even the method named 'esau_williams' does not match exactly the paper’s description, but the similarities are still substantial.

Note that constructor cannot be constrained in the number of feeders and that only method 'radial_EW' is constrained to producing radial topologies (i.e. subtrees are always simple paths) as opposed to the branched topologies produced by the others.

Available Methods:
'esau_williams'

Esau-Williams C-MST heuristic modified to avoid crossings (EW).

'biased_EW'

EW with a bias towards moving radially (root-ward) on quasi-ties.

'rootlust'

EW with a tunable root-ward bias that increases as capacity decreases.

'radial_EW'

EW variant that produces radial subtrees (simple paths from root).

'ringed'

Grows simple-path subtrees that are closed into rings at finalization: each endpoint connects to its nearest root (two feeders, which may bridge two roots), joined at a zero-load link (load=0, no current). capacity is the per-arm limit, so a ring holds up to 2 * capacity terminals. Unions are ranked by their total saving — the feeders shed at the two joined endpoints minus the connecting edge’s length (Clarke-Wright style) — with a bias_margin window favoring the more root-ward union on quasi-ties.

Parameters:

  • Aʹ – available links graph

  • capacity – max number of terminals in a subtree

  • method – choice of method (see Available Methods)

  • bias_margin – (biased_EW | radial_EW | ringed) fractional margin within which candidates are equivalent, resolving the quasi-tie root-ward. For 'ringed' the margin is a fraction of the best union saving (not the edge extent, since the ringed saving also depends on the peer feeders). Defaults to 0.02.

  • weigh_detours – (!= esau_williams) only add edges whose tradeoff is not outweighted by detours

  • straight_feeder_route – prevent crossings of feeders (incompatible with weigh_detours=True)

  • maxiter – fail-safe to avoid locking in an infinite loop

Returns:

Solution topology S.