routing.core.finders#

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: AStarFinder

A class representing an A* pathfinding algorithm with routing-specific enhancements.

This class inherits from AStarFinder, and extends the standard A* algorithm to work with SmartGridNode objects that have routing-specific attributes (like priority multiplier p). The heuristic is multiplied by the node’s priority to incorporate routing preferences into the pathfinding process.

apply_heuristic(node_a: SmartGridNode, node_b: SmartGridNode, heuristic: Callable | None = None) → float[source]#

Apply heuristic with routing priority multiplier.

Computes the heuristic distance between two nodes and multiplies it by the source node’s priority multiplier (node_a.p). This allows routing preferences to influence the heuristic estimate, making paths through preferred regions more attractive.

Parameters:

  • node_a – Source SmartGridNode (current node).

  • node_b – Target SmartGridNode (goal node).

  • heuristic – Optional heuristic function. If None, uses the finder’s default heuristic.

Returns:

Heuristic value multiplied by node_a.p (priority multiplier).

process_node(grid: SmartGrid, node: SmartGridNode, parent: SmartGridNode, end: SmartGridNode, open_list: list, open_value: int = 1) → None[source]#

Process a node during A* pathfinding with routing tracking.

Adds the node to the grid’s processed_nodes list for tracking and analysis, then calls the parent class’s process_node method to perform standard A* node processing (updating costs, adding to open list, etc.).

Parameters:

  • grid – SmartGrid instance containing the search space.

  • node – Current SmartGridNode being processed.

  • parent – Parent SmartGridNode that led to this node.

  • end – Target SmartGridNode (goal).

  • open_list – List of nodes to be explored (priority queue).

  • open_value – Value indicating node is in open list. Defaults to 1.

Returns:

None

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: BestFirst

A class representing a best-first pathfinding algorithm with routing-specific enhancements.

This class inherits from BestFirst, and extends best-first search to work with SmartGridNode objects. Best-first search uses a heuristic to guide the search, always exploring the most promising node first (greedy approach).

apply_heuristic(node_a: SmartGridNode, node_b: SmartGridNode, heuristic: Callable | None = None) → float[source]#

Apply heuristic with routing priority multiplier.

Computes the heuristic distance between two nodes and multiplies it by the source node’s priority multiplier (node_a.p).

Parameters:

  • node_a – Source SmartGridNode (current node).

  • node_b – Target SmartGridNode (goal node).

  • heuristic – Optional heuristic function. If None, uses the finder’s default heuristic.

Returns:

Heuristic value multiplied by node_a.p (priority multiplier).

process_node(grid: SmartGrid, node: SmartGridNode, parent: SmartGridNode, end: SmartGridNode, open_list: list, open_value: int = 1) → None[source]#

Process a node during best-first pathfinding with routing tracking.

Adds the node to the grid’s processed_nodes list, then calls the parent class’s process_node method.

Parameters:

  • grid – SmartGrid instance containing the search space.

  • node – Current SmartGridNode being processed.

  • parent – Parent SmartGridNode that led to this node.

  • end – Target SmartGridNode (goal).

  • open_list – List of nodes to be explored (priority queue).

  • open_value – Value indicating node is in open list. Defaults to 1.

Returns:

None

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: BiAStarFinder

A class representing a bidirectional A* pathfinding algorithm with routing-specific enhancements.

This class inherits from BiAStarFinder, and extends bidirectional A* to work with SmartGridNode objects. Bidirectional A* searches from both start and end simultaneously, meeting in the middle for improved performance on large grids.

apply_heuristic(node_a: SmartGridNode, node_b: SmartGridNode, heuristic: Callable | None = None) → float[source]#

Apply heuristic with routing priority multiplier.

Computes the heuristic distance between two nodes and multiplies it by the source node’s priority multiplier (node_a.p).

Parameters:

  • node_a – Source SmartGridNode (current node).

  • node_b – Target SmartGridNode (goal node).

  • heuristic – Optional heuristic function. If None, uses the finder’s default heuristic.

Returns:

Heuristic value multiplied by node_a.p (priority multiplier).

process_node(grid: SmartGrid, node: SmartGridNode, parent: SmartGridNode, end: SmartGridNode, open_list: list, open_value: int = 1) → None[source]#

Process a node during bidirectional A* pathfinding with routing tracking.

Adds the node to the grid’s processed_nodes list, then calls the parent class’s process_node method.

Parameters:

  • grid – SmartGrid instance containing the search space.

  • node – Current SmartGridNode being processed.

  • parent – Parent SmartGridNode that led to this node.

  • end – Target SmartGridNode (goal).

  • open_list – List of nodes to be explored.

  • open_value – Value indicating node is in open list. Defaults to 1.

Returns:

None

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: BreadthFirstFinder

apply_heuristic(node_a: SmartGridNode, node_b: SmartGridNode, heuristic: Callable | None = None) → float[source]#

Helper function to apply heuristic.

Parameters#

node_aGridNode

first node

node_bGridNode

second node

heuristicCallable

heuristic used to calculate distance of 2 points

Returns#

float

heuristic value

process_node(grid: SmartGrid, node: SmartGridNode, parent: SmartGridNode, end: SmartGridNode, open_list: list, open_value: int = 1) → None[source]#

We check if the given node is part of the path by calculating its cost and add or remove it from our path.

Parameters#

gridGrid

grid that stores all possible steps/tiles as 3D-list

nodeGridNode

the node we like to test (the neighbor in A* or jump-node in JumpPointSearch)

parentGridNode

the parent node (of the current node we like to test)

endGridNode

the end point to calculate the cost of the path

open_listList

the list that keeps track of our current path

open_valuebool

needed if we like to set the open list to something else than True (used for bi-directional algorithms)

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.

Raises:

StopIteration – When no path exists or all paths have been found.

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: IDAStarFinder

A class representing an IDA* pathfinding algorithm with routing-specific enhancements.

This class inherits from IDAStarFinder, and extends the Iterative Deepening A* algorithm to work with SmartGridNode objects. IDA* uses memory-efficient depth-first search with iterative deepening, making it suitable for large search spaces.

apply_heuristic(node_a: SmartGridNode, node_b: SmartGridNode, heuristic: Callable | None = None) → float[source]#

Apply heuristic with routing priority multiplier.

Computes the heuristic distance between two nodes and multiplies it by the source node’s priority multiplier (node_a.p).

Parameters:

  • node_a – Source SmartGridNode (current node).

  • node_b – Target SmartGridNode (goal node).

  • heuristic – Optional heuristic function. If None, uses the finder’s default heuristic.

Returns:

Heuristic value multiplied by node_a.p (priority multiplier).

process_node(grid: SmartGrid, node: SmartGridNode, parent: SmartGridNode, end: SmartGridNode, open_list: list, open_value: int = 1) → None[source]#

Process a node during IDA* pathfinding with routing tracking.

Adds the node to the grid’s processed_nodes list, then calls the parent class’s process_node method.

Parameters:

  • grid – SmartGrid instance containing the search space.

  • node – Current SmartGridNode being processed.

  • parent – Parent SmartGridNode that led to this node.

  • end – Target SmartGridNode (goal).

  • open_list – List of nodes to be explored.

  • open_value – Value indicating node is in open list. Defaults to 1.

Returns:

None

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

Bases: MinimumSpanningTree

A class representing a minimum spanning tree pathfinding algorithm with routing-specific enhancements.

This class inherits from MinimumSpanningTree, and extends MST-based pathfinding to work with SmartGridNode objects. Minimum spanning tree algorithms find the tree that connects all nodes with minimum total edge weight, useful for network design problems.

apply_heuristic(node_a: SmartGridNode, node_b: SmartGridNode, heuristic: Callable | None = None) → float[source]#

Apply heuristic with routing priority multiplier.

Computes the heuristic distance between two nodes and multiplies it by the source node’s priority multiplier (node_a.p).

Parameters:

  • node_a – Source SmartGridNode (current node).

  • node_b – Target SmartGridNode (goal node).

  • heuristic – Optional heuristic function. If None, uses the finder’s default heuristic.

Returns:

Heuristic value multiplied by node_a.p (priority multiplier).

process_node(grid: SmartGrid, node: SmartGridNode, parent: SmartGridNode, end: SmartGridNode, open_list: list, open_value: int = 1) → None[source]#

Process a node during MST pathfinding with routing tracking.

Adds the node to the grid’s processed_nodes list, then calls the parent class’s process_node method.

Parameters:

  • grid – SmartGrid instance containing the search space.

  • node – Current SmartGridNode being processed.

  • parent – Parent SmartGridNode that led to this node.

  • end – Target SmartGridNode (goal).

  • open_list – List of nodes to be explored.

  • open_value – Value indicating node is in open list. Defaults to 1.

Returns:

None

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.