routing.core.finders#

Finders module.

class routing.core.finders.SmartFinder(algorithm: str = 'AStar', heuristic: str | None = None, diagonal: str = 'never', name: str = '')[source]#

Bases: DessiaObject

A class representing a wrapper for pathfinding algorithms with routing-specific enhancements.

This class inherits from DessiaObject, and provides a unified interface to various pathfinding algorithms (A*, Dijkstra, etc.) with routing-specific features like design rule integration, port connection handling, and k-shortest paths.

Parameters:

  • algorithm – The pathfinding algorithm name. Options: ‘AStar’, ‘astar’, ‘Astar’, ‘AStarFinder’, ‘a*’ for A*; ‘Dijkstra’, ‘dijkstra’, ‘DijkstraFinder’ for Dijkstra; ‘BestFirst’, ‘bestfirst’, ‘best’, ‘BestFirstFinder’ for greedy best-first; ‘BreadthFirst’, ‘breadthfirst’, ‘BreadthFirstFinder’ for breadth-first; ‘ThetaStar’, ‘Theta’, ‘theta’, ‘thetastar’, ‘theta*’ for Theta*. All run the compiled search; A*, Dijkstra, best-first and breadth-first over (node, arrival direction) states, so the turn penalty is priced exactly; Theta* over cells, with any-angle segments. Defaults to ‘AStar’.

  • heuristic – The heuristic function name. Options: None for no heuristic; ‘manhattan’ for L1 norm; ‘euclidean’ for L2 norm; ‘chebyshev’ for L∞ norm; ‘octile’ for octile distance. Defaults to None.

  • diagonal – The diagonal movement policy. Options: ‘never’ for no diagonal movement; ‘always’ for always allow diagonal; ‘only_when_no_obstacle’ for diagonal only if every cell it passes is walkable; ‘if_at_most_one_obstacle’ for diagonal if at most one of them is blocked. Defaults to ‘never’.

  • name – The name to identify this finder. Defaults to ‘’.

all_shortest_paths(grid: SmartGridInterface, solution: Solution) → Iterator[GridPath][source]#

Generate k-shortest paths using Yen’s algorithm.

Implements Yen’s k-shortest paths algorithm to find multiple shortest paths between two ports in order of increasing cost. The algorithm:

  1. Finds the first shortest path using standard pathfinding

  2. For subsequent paths, explores “spur nodes” (nodes where alternative paths branch off) by: - Taking root path from start to spur node - Blocking edges from previous paths to avoid duplicates - Finding new spur path from spur node to end - Combining root + spur as candidate path

  3. Maintains candidates in a priority queue, selecting cheapest next

  4. Stops when no more unique paths exist or path length <= 3

Parameters:

  • grid – SmartGridInterface containing the routing space, weights, and design rules. Grid state is modified during pathfinding.

  • solution – Solution object with input_port, output_port, and pipe_type.

Returns:

Iterator yielding GridPath objects in order of increasing cost. Each GridPath contains path, cost, indicators, runs, runtime, and metadata.

find_path(start: SmartGridNode, end: SmartGridNode, grid: SmartGridInterface) → tuple[list[SmartGridNode], int, float][source]#
search_ports_connections(solution: Solution, grid: SmartGridInterface, n_iterations: int = 0, grid_forced_zones: tuple[GridForcedZone, ...] = ()) → list[Alternative][source]#

Search for paths connecting input and output ports.

Main entry point for finding paths between ports. If n_iterations is 0 or the algorithm is ThetaStar, returns only the first shortest path. Otherwise, uses k-shortest paths algorithm to find multiple alternatives. Through forced zones only the best path is searched.

ThetaStar doesn’t support k-shortest paths because it uses line-of-sight optimization that doesn’t work well with the spur node blocking mechanism.

Parameters:

  • solution – Solution object containing input_port, output_port, and pipe_type information.

  • grid – SmartGridInterface containing the routing space and weights.

  • n_iterations – Number of alternative paths to find. If 0 or using ThetaStar, returns only the first path. Defaults to 0.

Returns:

One Alternative per route found, with the ports it joins: the goal reached stands as the end port, a tee’s tap port. One route if n_iterations==0 or ThetaStar, otherwise up to n_iterations sorted by cost. Empty when no path joins the ports.

routing.core.finders.remove_duplicated_paths(cheapest: tuple[float, GridPath], path_candidates: list[tuple[float, GridPath]]) → list[tuple[float, GridPath]][source]#

Remove duplicate paths from candidates that have the same cost as the cheapest path.

When multiple paths have the same cost as the cheapest path, this function removes duplicates (paths with identical node sequences) while preserving unique paths. The cheapest path itself is not included in the result.

The function: 1. Extracts all candidates with the same cost as cheapest 2. Filters out paths that are identical to cheapest.path 3. Re-inserts unique paths back into the candidates heap

This is used in k-shortest paths algorithms to avoid returning multiple identical paths when they have the same cost.

Parameters:

  • cheapest – Tuple of (cost, GridPath) representing the cheapest path found.

  • path_candidates – List of tuples (cost, GridPath) in a heap structure, containing candidate paths sorted by cost.

Returns:

Updated path_candidates list with duplicates removed, maintaining heap structure with unique paths only.