optiwindnet.pathfinding

Module Contents

class optiwindnet.pathfinding.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 create_detours().

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

Parameters:

• G – the route set without detours

• P – the planar embedding associated with A

• A – the available links graph

• branched – if True, any terminal can be linked to root, else only subtrees’ heads/tails

• 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

branched = True

stunts_primes

adv_counter = 0

portal_set

best_pn_by_pair_id = []

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