optiwindnet.clustering
======================

.. py:module:: optiwindnet.clustering




Module Contents
---------------

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

   :param A: available-edges graph, needs graph attributes ``R``, ``T`` and ``d2roots``
   :param capacity: maximum number of terminals a feeder may serve

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