routing.core.finders#

Finders module.

class routing.core.finders.SmartAStar(heuristic: Callable | None = None, weight: int = 1, diagonal_movement: int = 2, time_limit: float = inf, max_runs: int | float = inf)[source]#

Bases: _SmartFinderMixin, AStarFinder

A* pathfinding with routing priority multiplier and processed-node tracking.

class routing.core.finders.SmartBestFirst(heuristic: Callable | None = None, weight: int = 1, diagonal_movement: int = 2, time_limit: float = inf, max_runs: int | float = inf)[source]#

Bases: _SmartFinderMixin, BestFirst

Best-first search with routing priority multiplier and processed-node tracking.

class routing.core.finders.SmartBiAStar(heuristic: Callable | None = None, weight: int = 1, diagonal_movement: int = 2, time_limit: float = inf, max_runs: int | float = inf)[source]#

Bases: _SmartFinderMixin, BiAStarFinder

Bidirectional A* with routing priority multiplier and processed-node tracking.

class routing.core.finders.SmartBreadthFirst(heuristic: Callable | None = None, weight: int = 1, diagonal_movement: int = 2, time_limit: float = inf, max_runs: int | float = inf)[source]#

Bases: _SmartFinderMixin, BreadthFirstFinder

Breadth-first search with routing priority multiplier and processed-node tracking.

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; ‘IDAStar’, ‘idastar’, ‘ida’, ‘Idastar’, ‘IDAStarFinder’ for IDA*; ‘BiAStar’, ‘biastar’, ‘Biastar’, ‘BiAStarFinder’ for bidirectional A*; ‘BestFirst’, ‘bestfirst’, ‘best’, ‘BestFirstFinder’ for best-first; ‘MSP’, ‘msp’, ‘spanning tree’, ‘MinimumSpanningTree’, ‘MinimumSpanningTreeFinder’ for minimum spanning tree; ‘BreadthFrist’, ‘breadthfirst’, ‘BreadthFristFinder’ for breadth-first; ‘ThetaStar’, ‘Theta’, ‘theta’, ‘thetastar’, ‘theta*’ for Theta*. 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; ‘obstacle’ for diagonal only if no obstacle; ‘no_obstacle’ for diagonal only if no obstacle in path. 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) → list[GridPath][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.

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:

List of GridPath objects. Contains 1 path if n_iterations==0 or ThetaStar, otherwise up to n_iterations paths sorted by cost.

class routing.core.finders.SmartIDAStar(heuristic: Callable | None = None, weight: int = 1, diagonal_movement: int = 2, time_limit: float = inf, max_runs: int | float = inf, track_recursion: bool = True)[source]#

Bases: _SmartFinderMixin, IDAStarFinder

Iterative-deepening A* with routing priority multiplier and processed-node tracking.

class routing.core.finders.SmartMinimumSpanningTree(*args, **kwargs)[source]#

Bases: _SmartFinderMixin, MinimumSpanningTree

Minimum-spanning-tree search with routing priority multiplier and processed-node tracking.

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.