optiwindnet.pathfinding
=======================

.. py:module:: optiwindnet.pathfinding




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

.. py:class:: PathFinder(Gʹ: networkx.Graph, planar: networkx.PlanarEmbedding, A: networkx.Graph, *, branched: bool = True, iterations_limit: int = 15000, traversals_limit: int = 3, bad_streak_limit: int = 5, turn_limit: float | None = None)

   Router for feeders that would cross other routes if laid in a straight line.

   PathFinder finds the shortest segmented (or detoured) routes for tentative feeders
   (i.e. those that were created without a check for crossings of other routes). The
   path-finding is performed when the instance is initialized, but a route set is
   returned only with a call to method :meth:`create_detours`.

   Only edges in graph attribute ``'tentative'`` or, lacking that, edges with the
   attribute ``'kind'`` with value ``'tentative'`` are checked for crossings.

   :param G: the route set without detours
   :param P: the planar embedding associated with A
   :param A: the available links graph
   :param branched: if True, any terminal can be linked to root, else only subtrees'
                    heads/tails
   :param iterations_limit: maximum number of steps in the path-finding process
   :param traversals_limit: maximum number of times a single portal may be traversed
   :param bad_streak_limit: limit on how many steps in a row without finding an improved
                            path the traverser is allowed to take

   Example::

     P, A = make_planar_embedding(L)  # L represents the geometry of the location
     S = some_solver(A, ...)  # S is a topology
     G_tentative = G_from_S(S, A)  # G_tentative is almost a route set
     G = PathFinder(G_tentative, planar=P, A=A).create_detours()

   .. note::

      On instances with ``capacity=2``, the default values may not enable finding all
      the shortest feeders. If :func:`.crossings.find_geometric_crossings` reports any
      crossings, retry with ``traversals_limit=10`` and ``iterations_limit=50000``.


   .. py:attribute:: iterations_limit
      :value: 15000



   .. py:attribute:: traversals_limit
      :value: 3



   .. py:attribute:: bad_streak_limit
      :value: 5



   .. py:attribute:: turn_limit
      :value: None



   .. py:attribute:: iterations
      :value: 0



   .. py:attribute:: ST


   .. py:attribute:: fnT


   .. py:attribute:: constraint_bounds


   .. py:attribute:: unrealized_contours_resolved
      :value: False



   .. py:attribute:: fences
      :value: []



   .. py:attribute:: edges_G_primes


   .. py:attribute:: d2roots


   .. py:attribute:: d2rootsRank


   .. py:attribute:: predetour_length


   .. py:attribute:: branched
      :value: True



   .. py:attribute:: stunts_primes


   .. py:attribute:: adv_counter
      :value: 0



   .. py:attribute:: portal_set


   .. py:attribute:: best_pn_by_pair_id
      :value: []



   .. py:method:: get_best_path(n: int)

      ``_.get_best_path(«node»)`` produces a ``tuple(path, dists)``.
      ``path`` contains a sequence of nodes from the original
      ``networkx.Graph`` ``G``, from ``«node»`` to the closest root.
      ``dists`` contains the lengths of the segments defined by ``paths``.



   .. py:method:: best_paths_overlay() -> networkx.Graph

      Merges the shortest paths for all nodes with ``G``.

      The output includes ``G``'s edges, excluding its feeders.

      :returns: Merged graph (pass to :func:`.plotting.gplot` or :func:`.svg.svgplot`).



   .. py:method:: scaffolded() -> networkx.Graph

      Wrapper for :func:`.interarraylib.scaffolded`.

      Also unmarks (as real route, not background mesh) every navigation-mesh
      hop crossed by a route fence. :func:`.interarraylib.scaffolded` cannot do
      this on its own: a contour edge in ``G`` may be a ``shortened_contours``
      shortcut spanning several mesh hops through one shared clone, and only
      ``self.fences`` (built from ``A``'s midpaths during path-finding) has the
      fully expanded, conflict-resolved hop sequence.



   .. py:method:: create_detours() -> networkx.Graph

      Reroute all feeder edges in G with crossings using detour paths.

      :returns: New networkx.Graph (shallow copy of G, with detours).