optiwindnet.heuristics
======================

.. py:module:: optiwindnet.heuristics




Package Contents
----------------

.. py:function:: 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

   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.

   :param Aʹ: available links graph
   :param capacity: max number of terminals in a subtree
   :param method: choice of method (see Available Methods)
   :param 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.
   :param weigh_detours: (!= esau_williams) only add edges whose tradeoff is not
                         outweighted by detours
   :param straight_feeder_route: prevent crossings of feeders
                                 (incompatible with ``weigh_detours=True``)
   :param maxiter: fail-safe to avoid locking in an infinite loop

   :returns: Solution topology S.