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

.. py:module:: optiwindnet.heuristics




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

.. py:function:: ClassicEW(L: networkx.Graph, capacity: int, delaunay_based: bool = False, maxiter: int = 10000, weightfun: Callable | None = None, weight_attr: str = 'length') -> networkx.Graph

   Classic Esau-Williams heuristic for C-MST.

   :param L: location graph
   :param capacity: max number of terminals in a subtree
   :param maxiter: fail-safe to avoid locking in an infinite loop

   :returns: Routeset graph G


.. py:function:: constructor(Aʹ: networkx.Graph, capacity: int, method: str = 'rootlust', *, rootlust_: tuple[float, float] = (), maxiter: int = 10000, bias_margin: float = _DEFAULT_BIAS_MARGIN, 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.

   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).

   :param Aʹ: available links graph
   :param capacity: max number of terminals in a subtree
   :param method: choice of method (see Methods)
   :param bias_margin: (biased_EW | radial_EW) fractional margin within with edges
                       are equivalent
   :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.


.. py:function:: CPEW(L: networkx.Graph, capacity: int, delaunay_based: bool = True, maxiter: int = 10000, weightfun: Callable | None = None, weight_attr: str = 'length') -> networkx.Graph

   Crossing Preventing Esau-Williams heuristic for C-MST

   :param L: location graph
   :param capacity: max number of terminals in a subtree
   :param maxiter: fail-safe to avoid locking in an infinite loop

   :returns: Routeset graph G


.. py:function:: EW_presolver(Aʹ: networkx.Graph, capacity: int, maxiter: int = 10000, keep_log: bool = False) -> networkx.Graph

   Modified Esau-Williams heuristic for C-MST with limited crossings

   :param Aʹ: available links graph
   :param capacity: max number of terminals in a subtree
   :param maxiter: fail-safe to avoid locking in an infinite loop

   :returns: Solution topology S.


.. py:function:: NBEW(L: networkx.Graph, capacity: int, delaunay_based: bool = True, rootlust: float = 0.0, maxiter: int = 10000, weightfun: Callable | None = None, weight_attr: str = 'length') -> networkx.Graph

   Non-branching Esau-Williams heuristic for C-MST.

   :param L: networkx.Graph
   :param capacity: max number of terminals in a subtree
   :param rootlust: weight of the reduction of subroot length in calculating savings
                    (use some value between 0 and 1, e.g. 0.6)

   :returns: Routeset graph G


.. py:function:: OBEW(L: networkx.Graph, capacity: int, rootlust: str | None = None, maxiter: int = 10000, maxDepth: int = 4, MARGIN: float = 0.0001, warnwhere: Callable | None = None, weightfun: Callable | None = None, keep_log: bool = False) -> networkx.Graph

   Obstacle Bypassing Esau-Williams heuristic for C-MST.

   Recommended `rootlust`: '0.6*cur_capacity/capacity'

   :param L: location graph
   :param capacity: max number of terminals in a subtree
   :param rootlust: expression to use for biasing weights
   :param warnwhere: print debug info based on utils.Alerter

   :returns: Routeset graph G