pysdic.bfs_distance#

bfs_distance(graph, start, max_distance=None, *, _skip_type_check=False)[source]#

Perform a breadth-first search (BFS) to compute the shortest path distances from a starting vertex to all other vertices in the graph.

Warning

No tests are performed to check if the input graph is valid (e.g., if the graph contains self-loops, if the graph contains invalid vertex indices, …). The behavior of the function is undefined if the input graph is not valid.

Parameters:

  • graph (Sequence[Iterable[Integral]]) – A sequence of iterables representing the adjacency list of the graph, where each index corresponds to a vertex and the iterable at that index contains the adjacent vertex indices. The length of the input sequence is equal to the number of vertices in the graph.

  • start (Integral) – The starting vertex index for the BFS.

  • max_distance (Optional[Integral], optional) – The maximum distance to search for in the BFS. If None, there is no maximum distance and all reachable vertices will be included in the distance computation. If an integer is provided, the BFS will only consider vertices that are within this distance from the starting vertex, and any vertex that is not reachable within this distance will have a distance of -1. By default None.

  • _skip_type_check (bool)

Returns:

A list of integers representing the shortest path distances from the starting vertex to all other vertices in the graph. The length of the output list is equal to the number of vertices in the graph.

Return type:

List[int]

Notes

The distance from vertex \(A\) to vertex \(T\) is defined as follows:

  • \(\text{dist}(A, T) = 0\) if vertex \(T\) is the same as vertex \(A\), since the distance from a vertex to itself is zero.

  • \(\text{dist}(A, T) = 1\) if vertex \(T\) is a neighbor of vertex \(A\), meaning that there is a direct edge connecting vertex \(A\) to vertex \(T\).

  • \(\text{dist}(A, T) = d \geq 1\) if the shortest path from vertex \(A\) to vertex \(T\) has length \(d\).

  • \(\text{dist}(A, T) = -1\) if vertex \(T\) is not reachable from vertex \(A\), meaning that there is no path connecting vertex \(A\) to vertex \(T\) in the graph.

  • \(\text{dist}(A, T) = -1\) if vertex \(T\) is not reachable from vertex \(A\) within the specified max_distance.

See also

bfs_neighborhood()

Perform a breadth-first search (BFS) to compute the neighborhood of a starting vertex in the graph, where the neighborhood of a vertex is defined as the set of vertices that are within a specified distance from the vertex in the connectivity of the mesh.

Examples

Create a simple disconnected graph of 7 vertices and compute the shortest path distances from a starting vertex (0) to all other vertices in the graph.

../_images/graph_bfs.png

Disconnected graph with 7 vertices for BFS example. Distance from vertex 0 to vertex 4 is 3 (0 -> 2 -> 3 -> 4).#

1from pysdic import bfs_distance
2
3graph = [[1, 2], [0, 2], [0, 1, 3], [2, 4], [3], [6], [5]]
4start_vertex = 0
5max_distance = None
6
7distances = bfs_distance(graph, start_vertex, max_distance)
8print(distances)

[0, 1, 1, 2, 3, -1, -1]
On this page

This Page