optiwindnet.interarraylib ========================= .. py:module:: optiwindnet.interarraylib Module Contents --------------- .. py:class:: TerseLinks Bases: :py:obj:`collections.abc.Sequence`\ [\ :py:obj:`int`\ ] Compact links plus the metadata needed to reconstruct their graph. ``RADIAL`` and ``BRANCHED`` values use one parent target per non-root node. ``RINGED`` values use the flattened route representation. A topology value represents ``S``; a routeset value additionally carries the clone mapping needed to reproduce ``G`` against its location graph. Either scope can be bound to an exact location geometry with ``nodeset_digest``. .. py:attribute:: links :type: tuple[int, Ellipsis] .. py:attribute:: topology :type: optiwindnet.types.Topology .. py:attribute:: scope :type: LinkScope .. py:attribute:: T :type: int .. py:attribute:: R :type: int .. py:attribute:: B :type: int :value: 0 .. py:attribute:: C :type: int :value: 0 .. py:attribute:: D :type: int :value: 0 .. py:attribute:: clone2prime :type: tuple[int, Ellipsis] :value: () .. py:attribute:: nodeset_digest :type: bytes | None :value: None .. py:method:: __post_init__() .. py:method:: __len__() -> int .. py:method:: __iter__() -> collections.abc.Iterator[int] .. py:method:: __getitem__(index) .. py:method:: __array__(dtype=None, copy=None) -> numpy.ndarray .. py:method:: __repr__() -> str .. py:method:: tolist() -> list[int] Return the encoded links as a plain list. .. py:method:: to_dict() -> dict[str, Any] Return a versioned representation suitable for JSON serialization. .. py:method:: from_dict(data: collections.abc.Mapping[str, Any]) -> TerseLinks :classmethod: Restore a value created by :meth:`to_dict`. .. py:method:: from_topology(S: networkx.Graph, *, nodeset_digest: bytes | None = None) -> TerseLinks :classmethod: Encode solution topology ``S``, optionally bound to a node set. .. py:method:: from_routeset(G: networkx.Graph) -> TerseLinks :classmethod: Encode routed solution ``G``, including its clone mapping. .. py:method:: from_array(links: collections.abc.Sequence[int], *, topology: optiwindnet.types.Topology | str | None = None, R: int | None = None, T: int | None = None) -> TerseLinks :classmethod: Adapt a legacy topology array to a self-describing value. .. py:method:: to_topology(**graph_attrs) -> networkx.Graph Reconstruct topology ``S``. .. py:method:: to_routeset(L: networkx.Graph, **graph_attrs) -> networkx.Graph Reconstruct routeset ``G`` against location graph ``L``. .. py:function:: assign_cables(G: networkx.Graph, cables: list[tuple[int, float | int]], currency: str = '€') Assign a cable type to each edge of ``G`` and update attribute ``'cost'``. Each edge is assigned the cheapest cable type that can carry its load. The edge attribute ``'cable'`` is the index in ``cables`` of the type chosen. Changes ``G`` in place. :param G: networkx graph with edges having a ``'load'`` attribute (use ``calcload(G)``) :param cables: [(«capacity», «cost»), ...] in increasing capacity order (each cable entry must be a tuple) :param currency: symbol representing the unit of the cost .. py:function:: describe_G(G: networkx.Graph, significant_digits: int = 5) -> list[str] Create a 3-4 line summary of G's properties. ``significant_digits`` applies only to total length and is enforced only when the integer part has fewer significant digits than ``significant_digits``. :param G: route set instance :param significant_digits: minimum number of significant digits used for total length :returns: capacity and T, excess feeders and feeders per root, total length, total cost. :rtype: Text lines .. py:function:: pathdist(G, path) Calculate the total length of a ``path`` of nodes in ``G``. Uses the nodes' coordinates (does not rely on edge attributes). .. py:function:: count_diagonals(S: networkx.Graph, A: networkx.Graph) -> int Count the number of Delaunay diagonals (extended edges) of ``A`` in ``S``. :param S: solution topology :param A: available edges used in creating ``S`` :returns: number of non-gate edges of ``S`` that are of kind ``'extended'`` or ``'contour_extended'`` (kind is read from ``A``). :raises ValueError: if an edge of unknown kind is found. .. py:function:: bfs_subtree_loads(G, parent, children, subtree, visited=None) Recurse down the subtree, updating edge and node attributes. Meant to be called by :func:`calcload`, but can be used independently (e.g. from PathFinder). Nodes must not have a ``'load'`` attribute. :param G: graph to traverse. :param parent: node the recursion descends from. :param children: nodes of ``G`` to descend into. :param subtree: subtree id to assign to every node visited. :param visited: nodes already claimed by this traversal; pass one set across several calls to keep them from claiming a node twice. A fresh set is used when omitted. :returns: Total number of descendant nodes :raises ValueError: a node is reached twice, so the traversal is not descending a tree -- ``G`` holds a cycle, or two roots reach the same node. .. py:function:: split_rings_and_calc_loads(S: networkx.Graph, A: networkx.Graph) -> None Close path-form ring arms into canonical rings and compute their loads. Only the ringed builders (HGS, LKH and the ``method='ringed'`` constructor) call this, on a solution ``S`` that is still a set of simple ``root → … → root`` paths missing their zero-load links. Each path is walked and closed into a canonical ring (see :func:`add_ring_to_S`), using ``A`` to pick the longer zero-load link on odd-length rings; a tail already touching a root bridges two roots ``(r1, r2)``. Every ring receives exactly one zero-load link (``load=0``, no current flows through it), and each node's subtree id and load, the edges' loads, and the graph's ``max_load`` / ``has_loads`` / root loads are set. All ringed solvers must call this before returning a solution, so that every ringed ``S`` carries exactly one ``load=0`` link per ring. .. py:function:: calcload(G: networkx.Graph) -> None Calculate link loads and update edge and node attributes of ``G``. ``G`` must already be in final form (a forest, or a ring-form graph whose ``load=0`` zero-load links are present). A breadth-first traversal of each root's subtree propagates the loads, treating ``load=0`` links (ring zero-load links) as breaks. Each node's subtree id and outgoing load land on its ``'subtree'`` / ``'load'`` attributes, the edges' ``'load'`` attributes are updated, and the graph's ``'max_load'``, ``'has_loads'`` and root loads are set. Ring construction — closing path-form arms into rings — lives in :func:`split_rings_and_calc_loads`, which the ringed builders call instead. .. py:function:: add_ring_to_S(S: networkx.Graph, roots: tuple[int, int], ordered: list[int], subtree: int, A: networkx.Graph | None = None) -> None Add a single ring to topology graph ``S`` in canonical form. A ring is the union of two radial arms, fed by ``r1`` and ``r2`` and joined at their tail ends; it bridges two substations when ``r1 != r2``. ``ordered`` is the terminal sequence ``[t1, ..., tn]`` walked along the ring, so that ``t1`` and ``tn`` are the feeder-connected terminals. Both feeders ``(r1, t1)`` and ``(r2, tn)`` are real, load-bearing cables; the ring's single zero-load link is the edge at the load midpoint, marked by ``load=0`` (a real cable, no current flows through it). Arm 1 (the ``t1`` side) gets ``m = ceil(n / 2)`` terminals, so each arm holds at most ``ceil(n / 2)`` — i.e. half of the doubled ring capacity. When the ring has an even number of nodes (odd ``n``), the middle terminal has two candidate split edges yielding balanced arms; if ``A`` is provided, the longer of the two is chosen as the zero-load link. Node ``'load'``/``'subtree'`` and edge ``'load'``/``'reverse'`` are all set here; the caller is responsible for the root node's aggregate load. :param S: topology graph to add the ring to (modified in place). :param roots: the pair ``(r1, r2)`` of (negative) root node ids, equal when both feeders share one root. :param ordered: terminal sequence ``[t1, ..., tn]`` along the ring. :param subtree: subtree id to assign to every node of the ring (both arms). :param A: optional available-links graph, used to pick the longer split edge on odd-node rings. .. py:function:: rings_from_S(S: networkx.Graph) -> list[tuple[tuple[int, int], list[int]]] Recover ordered ring terminal sequences from a RINGED solution graph. Each ring is returned as ``((r1, r2), [t1, ..., tn])`` with ``t1`` and ``tn`` the feeder-connected terminals, obtained by walking the terminal adjacency from the head subroot to the tail one; ``r1`` feeds ``t1`` and ``r2`` feeds ``tn``. The ring bridges two substations when ``r1 != r2``. Feeders are identified by having exactly one negative (root) endpoint; a ring with a single terminal (``n == 1``) has both feeders on that terminal. .. py:function:: validate_topology(S: networkx.Graph, capacity: int | None = None) -> list[str] Check ``S`` against the invariants of the topology it declares. The canonical shape of a solution is a contract of the library, not of the test suite, so the invariants live next to the builders that establish them. Together these invariants make ``S`` representable: a topology that passes survives a round-trip through its ``terse_links`` encoding unchanged, which is what makes it storable and usable as a MILP warm start. :param S: topology graph to check. ``S.graph['topology']`` is mandatory: it is one of ``'ringed'``, ``'radial'`` or ``'branched'``. Loads are mandatory too -- ``S`` without them is reported as a violation. :param capacity: cable capacity; defaults to ``S.graph['capacity']``. Capacity checks are skipped when neither is available. :returns: list of human-readable violations; ``S`` is valid if it is empty. Example:: violations = validate_topology(S, capacity) if violations: print('\n'.join(violations)) .. py:function:: validate_routeset(G: networkx.Graph) -> list[str] Check a routeset ``G`` for load, topology and crossing violations. Orchestrates the specific checkers: the loads ``G`` carries are compared against those its links imply (:func:`calcload` on a copy, so ``G`` is left untouched), the topology is checked against the shape it declares (:func:`validate_topology`), and the routes are checked for crossings and branch splits (:func:`~optiwindnet.crossings.find_routeset_crossings`). Every routeset producer emits loads, so they are verified rather than recomputed: a routeset whose loads disagree with its links is reported, not silently corrected. Crossings are geometry alone, so they are reported even when the loads are unusable. :param G: routeset graph to evaluate. :returns: list of human-readable violations; ``G`` is valid if it is empty. Example:: violations = validate_routeset(G) if violations: print('\n'.join(violations)) .. py:function:: directed_links(S: networkx.Graph) -> collections.abc.Iterator[tuple[int, int, int]] Yield ``(source, sink, flow)`` for every link of ``S``. Forest topologies read each link's orientation off its ``'reverse'`` flag (see the note above :func:`bfs_subtree_loads`), so ``flow`` is just the link's load. A RINGED ``S`` -- as declared by ``S.graph['topology']`` -- stores each ring split into two arms at a zero-load link, which is not how a flow formulation sees it: there a ring is one directed chain of its ``n`` terminals, fed by a flowless closing feeder at one end and draining through a feeder carrying the whole ring at the other. Such rings are *radialized* into that chain here (walking across the zero-load link with :func:`rings_from_S`), so the zero-load link becomes an ordinary flow-carrying link. A ring bridging two roots drains through the one feeding the head of the walk and closes on the other; which of the two drains is arbitrary, as it moves no cable. :param S: solution topology. :Yields: ``(source, sink, flow)`` per link, current flowing ``source`` -> ``sink``. ``flow`` is 0 for links carrying no current: a ring's closing feeder. .. py:function:: L_from_site(*, VertexC: numpy.ndarray, T: int, R: int, B: int = 0, border: numpy.ndarray | None = None, obstacles: list[numpy.ndarray] | None = None, name: str = '', handle: str = 'L_from_site', landscape_angle: float | None = None) -> networkx.Graph Create L from a location's attributes. :param VertexC: numpy.ndarray (V, 2) with all (x, y) coordinates (V = R + T + B) :param T: int number of wtg :param R: int number of oss :param B: number of border and obstacle zones' vertices :param border: array (B,) of VertexC indices that define the border (ccw) :param obstacles: sequence of numpy.ndarray of VertexC indices :param name: site name :param handle: site identifier :returns: Graph containing ``N = R + T`` nodes and no edges (all args become graph attributes). .. py:function:: G_from_S(S: networkx.Graph, A: networkx.Graph) -> networkx.Graph Create G from S and A. Graph ``S`` contains the topology of a routeset network (nodes only, no contours or detours). ``S`` must have been created from the available edges in ``A``, whose contour information is used to obtain a routeset ``G`` (possibly with contours, but not with detours – use PathFinder afterward). .. py:function:: S_from_G(G: networkx.Graph) -> networkx.Graph Get ``G``'s topology (contours, detours, lengths, coords are dropped). If using S to warm-start a MILP model, call after :func:`S_from_G`: * :func:`as_hooked_to_nearest`: if the model uses ``topology='branched'`` * :func:`as_hooked_to_head`: if the model uses ``topology='radial'`` This ensures that topology ``S`` is feasible (if radial) and not trivially suboptimal (if branched). RINGED routesets are supported: the rings' cycle-closing links are preserved (see the traversal note below), so ``S`` keeps the ring partition of ``G``. :param G: must contain a feasible solution (tree, path or ring) :returns: Topology of ``G`` .. py:function:: L_from_G(G: networkx.Graph) -> networkx.Graph Return new location with nodes and site attributes from G. The returned location graph ``L`` retains only roots, nodes and basic graph attributes. All edges and remaining attributes are not carried from ``G``. :param G: routeset graph to extract site data from. :returns: Site graph (no edges) with lean attributes. .. py:function:: S_from_terse_links(terse_links, R=None, T=None, topology=None, **kwargs) Create topology ``S`` from a self-describing or legacy encoding. .. py:function:: terse_links_from_S(S) Return the self-describing compact representation of topology ``S``. .. py:function:: as_obstacle_free(Lʹ: networkx.Graph) -> networkx.Graph Make a shallow copy of an instance and remove its obstacles. The vertices that are used only by obstacles are also removed. To be used on locations (edge-less graphs). :param Lʹ: input location :returns: location without obstacles. .. py:function:: as_single_root(Lʹ: networkx.Graph) -> networkx.Graph Make a shallow copy of an instance and reduce its roots to one. The output's root is the centroid of the input's roots. This may not work well for locations with obstacles, use ``as_obstacle_free()`` first. :param Lʹ: input location :returns: location with a single root. .. py:function:: as_normalized(Aʹ: networkx.Graph, *, offset: optiwindnet.geometric.CoordPair | None = None, scale: float | None = None) -> networkx.Graph Make a shallow copy of an instance and shift and scale its geometry. Coordinates are subtracted by graph attribute ``'norm_offset'``. All lengths and coordinates are multiplied by graph attribute ``'norm_scale'``. Graph attribute ``'is_normalized'`` is set to ``True``. Affected linear attributes: ``'VertexC'``, ``'d2roots'`` (graph); ``'length'`` (edge). :param Aʹ: (or Gʹ) any instance that has inherited ``'scale'`` from an edgeset ``Aʹ``. :param offset: coordinates (2,) offset to override graph's ``'norm_offset'`` :param scale: multiplicative scaling factor to override graph's ``'norm_scale'`` :returns: A copy of the instance with changed coordinates and linear metrics. .. py:function:: as_rescaled(Gʹ: networkx.Graph, L: networkx.Graph) -> networkx.Graph Revert normalization done by :func:`as_normalized`. :param Gʹ: routeset to rescale to pre-normalization size. :param L: (or G or A) locations or routeset to get ``'VertexC'`` from (also ``'d2roots'``, if available). :returns: Routeset with coordinates and lengths at site scale. .. py:function:: as_undetoured(Gʹ: networkx.Graph) -> networkx.Graph Create an undetoured version of Gʹ. Creates a shallow copy of ``Gʹ`` without detour nodes (and possibly *with* the resulting crossings). Changed links' ``'kind'`` become ``'tentative'``. This is to be applied to a routeset that already has detours. It serves to re-run PathFinder on a detoured routeset, but it is not the best solution to prepare a routeset to be used as warmstart (re-hooking is missing). .. py:function:: as_hooked_to_nearest(Gʹ: networkx.Graph, d2roots: numpy.ndarray) -> networkx.Graph Make tentative feeders link to the nearest-to-root node of each subtree. Output may be branched (use with care with path routesets). Sifts through all ``'tentative'`` gates' subtrees and choose the hook closest to the respective root according to ``d2roots``. Should be called after :func:`as_undetoured` if the goal is to use G as a warmstart for MILP models. :param G: routeset or topology S :param d2roots: distance from nodes to roots (e.g. ``A.graph['d2roots']``) .. py:function:: as_hooked_to_head(Sʹ: networkx.Graph, d2roots: numpy.ndarray) -> networkx.Graph Make tentative feeders link to the nearest-to-root end of each string. Only works with solutions where subtrees are paths (radial topology). Sifts through the subtrees of ``'tentative'`` feeders and re-hook the subtree via the end-node that is nearest to the respective root according to ``d2roots``. Should be called after :func:`as_undetoured` if the goal is to use S as a warmstart for MILP models. :param S: solution topology :param d2roots: distance from nodes to roots (e.g. ``A.graph['d2roots']``) .. py:function:: as_stratified_vertices(Lʹ: networkx.Graph) -> networkx.Graph Ensure border-vertices are all in the B-range of VertexC. Apply this to L when terminal or root coordinates are to be updated by writting to the array elements of VertexC. In order to keep the borders in place, they must not rely on vertices in the terminal or root sections (T-range, R-range). This function creates duplicates of any terminal-vertex or root-vertex used by borders/obstacles. :param L: location geometry to be stratified :returns: New location geometry with stratified vertices .. py:function:: make_remap(G, refG, H, refH) Create a mapping between two representations of the same site. CAUTION: only WTG node remapping is implemented. If the nodes in ``G`` and in ``H`` represent the same site, but have different orientation, scale and node order, the mapping produced here can be used with ``NetworkX.relabel_nodes(G, remap)`` to translate a routeset in G to a routeset in H. :param G: routeset with obsolete representation. :param refG: two nodes to used as references. :param H: routeset with valid representation. :param refH: two nodes corresponding to ``refG`` .. py:function:: add_terminal_closest_root(A: networkx.Graph) -> None Add attributes ``'root'`` to terminals and ``'rootmap__'`` to ``A``. Changes A in-place. * node attribute ``'root'`` is the index of the root closest to node. * graph attribute ``'rootmap__'`` is an R-long list of T-long bitarrays. :param A: available-links graph .. py:function:: add_link_blockmap(A: networkx.Graph) Add edge attributes ``'blocked__'``. Edges' attribute ``'blocked__'`` are R-long list of T-long bitarray maps. If an edge's ``blocked__[r][t] == 1``, then this edge crosses the line-of-sight t-r. Changes ``A`` in place. ``A`` should have no feeder edges. .. note:: * this function neglects borders and contours. * the space taken scales with ``R × T × num_edges(A)`` .. py:function:: add_link_cosines(A: networkx.Graph) Add cosine of the angle wrt each root to all links of A as attribute ``'cos_'``. Changes A in-place. The cosine is of the acute angle between the link line and the line that contains the mid-point of the link and the root (for each root). .. py:function:: scaffolded(G: networkx.Graph, P: networkx.PlanarEmbedding) -> networkx.Graph Create a new graph merging G and P. Useful for visualizing the funnels explored by :class:`.pathfinding.PathFinder`. ``G`` must have been created using ``P``. :param G: network graph for location :param P: planar embedding of location :returns: Merged graph (pass to :func:`.plotting.gplot` or :func:`.svg.svgplot`).