gale.ai.search module

This file contains generic graph search algorithms: depth-first search, breadth-first search, and the shortest-path algorithms Dijkstra and A*. They all work over any graph-like object exposing weighted neighbors, such as a gale.ai.graph.Graph (or one of its subclasses) or a plain callable, so they are not tied to any single graph representation.

Author: Alejandro Mujica (aledrums@gmail.com)

gale.ai.search.path_cost(graph_or_neighbors_fn, path)[source]
Parameters:

  • graph_or_neighbors_fn (Graph | Callable[[T], Iterable[Tuple[T, float]]]) – A Graph, or a callable node -> iterable of (neighbor, weight) pairs, to get edge weights from.

  • path (List[T]) – A sequence of nodes, as returned by any of the search functions in this module.

Returns:

The total weight of traversing path in order.

Return type:

float

Find a path between start and goal using an iterative depth-first search. It does not consider edge weights, and, unlike breadth_first_search, the path it finds is not guaranteed to be the shortest one.

Parameters:

  • start (T) – The node to start the search from.

  • goal (T) – The node to reach.

  • graph_or_neighbors_fn (Graph | Callable[[T], Iterable[Tuple[T, float]]]) – A Graph, or a callable node -> iterable of (neighbor, weight) pairs, describing the graph to search.

Returns:

The list of nodes from start to goal (both included), or None if goal is unreachable from start.

Return type:

List[T] | None

Find the shortest path (in number of edges, ignoring weights) between start and goal using an iterative breadth-first search.

Parameters:

  • start (T) – The node to start the search from.

  • goal (T) – The node to reach.

  • graph_or_neighbors_fn (Graph | Callable[[T], Iterable[Tuple[T, float]]]) – A Graph, or a callable node -> iterable of (neighbor, weight) pairs, describing the graph to search.

Returns:

The shortest list of nodes from start to goal (both included), or None if goal is unreachable from start.

Return type:

List[T] | None

gale.ai.search.dijkstra(start, goal, graph_or_neighbors_fn)[source]

Find the cheapest path (by total edge weight) between start and goal using Dijkstra’s algorithm.

Parameters:

  • start (T) – The node to start the search from.

  • goal (T) – The node to reach.

  • graph_or_neighbors_fn (Graph | Callable[[T], Iterable[Tuple[T, float]]]) – A Graph, or a callable node -> iterable of (neighbor, weight) pairs, describing the graph to search. Weights must not be negative.

Returns:

The cheapest list of nodes from start to goal (both included), or None if goal is unreachable from start.

Return type:

List[T] | None

gale.ai.search.a_star(start, goal, graph_or_neighbors_fn, heuristic)[source]

Find the cheapest path (by total edge weight) between start and goal using the A* algorithm, which uses heuristic to focus the search towards goal instead of expanding outward evenly like dijkstra does.

Parameters:

  • start (T) – The node to start the search from.

  • goal (T) – The node to reach.

  • graph_or_neighbors_fn (Graph | Callable[[T], Iterable[Tuple[T, float]]]) – A Graph, or a callable node -> iterable of (neighbor, weight) pairs, describing the graph to search. Weights must not be negative.

  • heuristic (Callable[[T, T], float]) – Callable (node, goal) -> estimated cost to reach goal from node. For the found path to be guaranteed optimal, it must not overestimate the real cost, for instance euclidean distance when weights are also distances (an admissible heuristic).

Returns:

The cheapest list of nodes from start to goal (both included), or None if goal is unreachable from start.

Return type:

List[T] | None