Graph

class w9_pathfinding.envs.Graph

A basic graph implementation with optional coordinates and edge support.

This class supports both directed and undirected graphs. Nodes can be optionally associated with coordinates.

Parameters:

• num_vertices (int) – The number of vertices (nodes) in the graph.

• directed (bool, default True) – Whether the graph is directed (True) or undirected (False).

• edges (iterable of tuple, optional) –

  Initial edges to populate the graph. Each edge can be either:

  • (from_node, to_node)

  • (from_node, to_node, weight)

  If the weight is omitted, it defaults to 1.0.

• coordinates (list of list of float, optional) – A list of coordinates for each node. Coordinates can be in 2D, 3D, or higher dimensions. Used to enable distance-based heuristics (e.g. Euclidean distance) in A*-like pathfinding algorithms. If not provided, heuristic-based algorithms that depend on node positions will not function.

• edge_collision (bool, default False) – Whether to enable edge collision checks. If set to True, prevents two agents from using the same edge simultaneously, even if they are moving in opposite directions. This helps avoid edge conflicts (e.g. node swapping) in multi-agent pathfinding scenarios.

Example

Create a directed graph with 3 nodes and 2 edges (0 → 1 → 2):

>>>  graph = Graph(3, edges=[(0, 1), (1, 2)])

add_edges(edges)

Add multiple edges to the graph.

Each edge can be a 2-tuple (from_node, to_node) or a 3-tuple (from_node, to_node, weight). If weight is omitted, a default of 1.0 is used.

Parameters:

edges (Iterable[Tuple[int, int] or Tuple[int, int, float]]) – Iterable of edges to add.

Raises:

ValueError – If an edge contains a node not present in the graph.

adjacent(v1, v2) → bool

Check whether two nodes are directly connected.

Parameters:

• v1 (node) – First node.

• v2 (node) – Second node.

Returns:

True if there is a direct edge from v1 to v2.

Return type:

bool

Raises:

ValueError – If either v1 or v2 is not a valid node in the environment.

calculate_cost(path) → double

Calculate the total cost of a given path through the environment.

If the path is invalid (e.g. contains non-adjacent nodes), this will return -1.

Parameters:

path (iterable of nodes) – A sequence of nodes representing the path to evaluate.

Returns:

Total cost of traversing the path, or -1 if the path is invalid.

Return type:

float

Raises:

ValueError – If one of the nodes in the path is not a valid node in the environment.

contains(node) → bool

Check if the environment contains a given node.

Parameters:

node – The node to check.

Returns:

True if the node is in the environment, False otherwise.

Return type:

bool

coordinates

Get the coordinates of all nodes in the graph.

Returns:

A list of coordinate vectors, one per node, or None if coordinates have not been set.

Return type:

List[List[float]] or None

directed

Whether the graph is directed.

edge_collision

Whether edge collision checks are enabled.

edges

Get all edges in the graph.

Returns:

List of edges as (from, to, weight).

Return type:

List[Tuple[int, int, float]]

estimate_distance(v1, v2) → double

Estimate the geometric (Euclidean) distance between two nodes.

Requires that node coordinates are set using set_coordinates() beforehand. If coordinates are not available, a RuntimeError is raised.

Parameters:

• v1 (int) – ID of the first node.

• v2 (int) – ID of the second node.

Returns:

Euclidean distance between the two nodes.

Return type:

float

Raises:

• RuntimeError – If coordinates have not been set.

• ValueError – If one of the nodes is not present in the graph.

find_components()

Find connected components (only for undirected graphs).

Returns:

List of components, each as a list of nodes.

Return type:

List[List[int]]

Raises:

ValueError – If called on a directed graph.

find_scc()

Find strongly connected components (only for directed graphs).

Returns:

List of strongly connected components.

Return type:

List[List[int]]

Raises:

ValueError – If called on an undirected graph.

get_neighbors(node, include_self=False) → list

Get neighboring nodes of a given node, along with the cost of moving to each.

Each neighbor is returned as a tuple of (neighbor_node, cost). For example: [(n1, 1.0), (n2, 2.5)]

Parameters:

• node – The target node.

• include_self (bool, default False) – Whether to include the node itself if there is an self loop.

Returns:

List of neighbors with movement costs.

Return type:

List[Tuple[node, float]]

Raises:

ValueError – If the node is not a valid node in the environment.

has_coordinates() → bool

Check whether node coordinates are defined.

Returns:

True if coordinates have been set.

Return type:

bool

is_valid_path(path) → bool

Check if a given path is valid within the environment.

Parameters:

path (iterable of nodes) – A sequence of nodes representing the path

Returns:

True if the path is valid, False otherwise.

Return type:

bool

Raises:

ValueError – If one of the nodes in the path is not a valid node in the environment.

num_edges

Number of edges in the graph.

num_vertices

Number of vertices in the graph. Equivalent to the size property.

reverse(*, inplace=False)

Reverse the direction of all edges.

Parameters:

inplace (bool, default False) – If True, modify the graph in-place; otherwise return a new reversed graph.

Returns:

Reversed graph if not in-place; otherwise None.

Return type:

Graph or None

set_coordinates(coordinates)

Set spatial coordinates for each node in the graph.

Each coordinate defines the position of a node in space and enables distance-based heuristics (e.g. Euclidean distance) in A*-like algorithms.

Parameters:

coordinates (list of list of float) – A list of coordinates, one per node. All coordinates must have the same number of dimensions (e.g. 2D, 3D, etc.).

Raises:

• ValueError – If the number of coordinates does not match the number of vertices.

• ValueError – If coordinates have inconsistent dimensionality (e.g. some are 2D, others 3D).

size

Total number of nodes in the environment.

to_dict()

Convert environment settings to a serializable dictionary.

Returns:

Dictionary of environment configuration options.

Return type:

dict