optiwindnet.pathfinding

Module Contents

class optiwindnet.pathfinding.PathFinder(Gʹ: networkx.Graph, planar: networkx.PlanarEmbedding, A: networkx.Graph, *, 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 create_detours().

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

Feeders are rerouted within the topology Gʹ declares in its mandatory 'topology' graph attribute, which decides where a feeder may re-hook: 'branched' allows any terminal of the subtree, 'radial' only its head or tail, 'ringed' only the current subroot.

Parameters:

• G – the route set without detours

• P – the planar embedding associated with A

• A – the available links graph

• iterations_limit – maximum number of steps in the path-finding process

• traversals_limit – maximum number of times a single portal may be traversed

• 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 crossings.find_geometric_crossings() reports any crossings, retry with traversals_limit=10 and iterations_limit=50000.

iterations_limit = 15000

traversals_limit = 3

bad_streak_limit = 5

turn_limit = None

iterations = 0

ST

fnT

constraint_bounds

unrealized_contours_resolved = False

fences = []

edges_G_primes

d2roots

d2rootsRank

predetour_length

topology

stunts_primes

adv_counter = 0

portal_set

best_pn_by_pair_id: list[int | None] = []

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.

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 plotting.gplot() or svg.svgplot()).

scaffolded() → networkx.Graph

Wrapper for interarraylib.scaffolded().

Also unmarks (as real route, not background mesh) every navigation-mesh hop crossed by a route fence. 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.

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