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, allow_root_change: bool = True)

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 routeset 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 (a Topology member), 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 routeset 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

• allow_root_change – if False, create_detours() connects each subtree to the root it has in Gʹ, and the paths from each root are searched as if the other roots did not compete for the same terminals

Warns:

UserWarning – if the input routeset contains links absent from the mesh.

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 routeset
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

allow_root_change = True

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

XY

stunts_primes

adv_counter = 0

portal_set

wall_free_vertices

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