gale.ai.graph module

This file contains a generic, reusable graph implementation, along with specialized graphs built on top of it: NavGraph for navigation (waypoints/positions), DependencyGraph for prerequisite/build-order relationships, and StateGraph for state-space problems, such as every reachable configuration of the Towers of Hanoi puzzle. They are meant to be paired with the search algorithms in gale.ai.search.

Author: Alejandro Mujica (aledrums@gmail.com)

exception gale.ai.graph.CycleError[source]

Bases: Exception

Raised when an operation that requires an acyclic graph, such as DependencyGraph.topological_sort, finds a cycle.

class gale.ai.graph.Graph(directed=False)[source]

Bases: Generic[T]

A generic graph of hashable nodes connected by weighted edges. It can be directed or undirected, and is meant to be generic and reusable enough to serve as the base for more specific graphs, such as NavGraph, DependencyGraph, or StateGraph, as well as to be searched directly with the functions in gale.ai.search.

Parameters:: directed (bool)

property nodes: Iterable[T]

Every node currently in the graph.

Type:: returns

property edges: Iterator[Tuple[T, T, float]]

Every edge currently in the graph as (source, target, weight) tuples. Each edge of an undirected graph is yielded only once.

Type:: returns

add_node(node)[source]

Add a node to the graph. Does nothing if it is already present.

Parameters:: node (T) – The node to add.
Return type:: None

has_node(node)[source]

Parameters:: node (T) – The node to look for.
Returns:: Whether the node is present in the graph.
Return type:: bool

remove_node(node)[source]

Remove a node and every edge connected to it.

Parameters:: node (T) – The node to remove.
Raises:: KeyError – If the node is not present in the graph.
Return type:: None

add_edge(source, target, weight=1.0)[source]

Add an edge between source and target, creating either node that is not already present. If the graph is undirected, the edge is also added from target to source.

Parameters:

source (T) – The origin node.
target (T) – The destination node.
weight (float) – The cost of traversing the edge. The default value is 1.0.

Return type:

None

has_edge(source, target)[source]

Parameters:

source (T) – The origin node.
target (T) – The destination node.

Returns:

Whether there is an edge from source to target.

Return type:

bool

remove_edge(source, target)[source]

Remove the edge from source to target (and from target to source, if the graph is undirected).

Parameters:

source (T) – The origin node.
target (T) – The destination node.

Raises:

KeyError – If there is no such edge.

Return type:

None

get_weight(source, target)[source]

Parameters:

source (T) – The origin node.
target (T) – The destination node.

Returns:

The weight of the edge from source to target.

Raises:

KeyError – If there is no such edge.

Return type:

float

neighbors(node)[source]

Parameters:: node (T) – The node to get the neighbors of.
Returns:: The nodes directly reachable from node.
Raises:: KeyError – If the node is not present in the graph.
Return type:: Iterable[T]

weighted_neighbors(node)[source]

Parameters:: node (T) – The node to get the neighbors of.
Returns:: Pairs (neighbor, weight) directly reachable from node. This is the shape expected by the search functions in gale.ai.search.
Raises:: KeyError – If the node is not present in the graph.
Return type:: Iterable[Tuple[T, float]]

class gale.ai.graph.NavGraph(directed=False)[source]

Bases: Graph[Tuple[float, float]]

A graph specialized for navigation, where nodes are 2D positions, such as waypoints or the centers of a navigation mesh’s polygons. The weight of an edge defaults to the euclidean distance between the two positions it connects, since that is normally what you want to minimize when pathfinding, but it can still be overridden explicitly, for instance to penalize hazardous terrain.

Parameters:: directed (bool)

add_edge(source, target, weight=None)[source]

Parameters:

source (Tuple[float, float]) – The origin position.
target (Tuple[float, float]) – The destination position.
weight (float | None) – The cost of traversing the edge. The default value is the euclidean distance between source and target.

Return type:

None

class gale.ai.graph.DependencyGraph[source]

Bases: Graph[T]

A directed graph to express prerequisite/build-order relationships, such as a skill tree, a quest chain, or a build pipeline.

add_dependency(item, depends_on)[source]

Declare that item requires depends_on to happen/exist first.

Parameters:

item (T) – The dependent item.
depends_on (T) – The item that must come before it.

Return type:

None

topological_sort()[source]

Returns:: The nodes ordered so that every node comes after all of the items it depends on.
Raises:: CycleError – If the graph has a cycle, since no valid order exists in that case.
Return type:: List[T]

has_cycle()[source]

Returns:: Whether the graph has at least one cycle.
Return type:: bool

class gale.ai.graph.StateGraph[source]

Bases: Graph[T]

A directed graph representing a state space: nodes are problem states and edges are the transitions (actions/moves) between them, such as every reachable configuration of the Towers of Hanoi puzzle and the moves connecting them.

Building the full state space by hand does not scale, so use expand to generate it automatically from a starting state and a function that yields the valid transitions out of any given state. Each transition can optionally carry an action label (for instance, a description of the move that was made), which get/actions_for_path let you recover afterwards from a path found by gale.ai.search — plain states alone don’t always make it obvious what to actually do to go from one to the next.

add_edge(source, target, weight=1.0, action=None)[source]

Parameters:

source (T) – The origin state.
target (T) – The destination state.
weight (float) – The cost of the transition. The default value is 1.0.
action (Any) – An optional label identifying the transition, for instance the move that was made. The default value is None.

Return type:

None

remove_edge(source, target)[source]

Remove the edge from source to target (and from target to source, if the graph is undirected).

Parameters:

source (T) – The origin node.
target (T) – The destination node.

Raises:

KeyError – If there is no such edge.

Return type:

None

remove_node(node)[source]

Remove a node and every edge connected to it.

Parameters:: node (T) – The node to remove.
Raises:: KeyError – If the node is not present in the graph.
Return type:: None

get_action(source, target)[source]

Parameters:

source (T) – The origin state.
target (T) – The destination state.

Returns:

The action associated with the transition from source to target, or None if it was not given one.

Raises:

KeyError – If there is no such edge.

Return type:

Any

actions_for_path(path)[source]

Parameters:: path (Sequence[T]) – A sequence of states, such as one returned by any of the search functions in gale.ai.search.
Returns:: The action associated with each consecutive pair of states in path, in order.
Return type:: List[Any]

classmethod expand(start, successors)[source]

Build the full graph of states reachable from start.

Parameters:

start (T) – The initial state.
successors (Callable[[T], Iterable[Tuple[T, float] | Tuple[T, float, Any]]]) – Callable that, given a state, returns an iterable of (next_state, cost) pairs, or (next_state, cost, action) triples, one for every valid transition out of it. Omitting action leaves the transition unlabeled.

Returns:

A StateGraph with every state reachable from start and the transitions between them.

Return type:

StateGraph[T]