pygraphs.bfs_matrix

bfs_matrix(graph, *, max_distance=None, _skip_check=False)

Compute the shortest path distance matrix for all pairs of vertices.

Parameters:

• graph (Graph) – An instance of the Graph class representing the graph to be traversed.

• max_distance (Optional[Integral], optional (default: None)) – The maximum distance to search for in the BFS. All vertices that are not reachable within this distance will be ignored.

• _skip_check (bool)

Returns:

A 2D list representing the shortest path distance matrix, where the element at position (i, j) represents the shortest path distance from vertex i to vertex j. If a vertex is not reachable within the specified maximum distance, the distance will be -1.

Return type:

List[List[int]]

Notes

The function uses a BFS approach to compute the shortest path distances, which is efficient for unweighted graphs. The time complexity is \(O(V(V + E))\), where \(V\) is the number of vertices and \(E\) is the number of edges in the graph. For a undirected graph, the distance matrix is symmetric, meaning that the distance from vertex \(A\) to vertex \(B\) is the same as the distance from vertex \(B\) to vertex \(A\) (i.e., \(\text{dist}(A, B) = \text{dist}(B, A)\)), since the edges can be traversed in both directions. For a directed graph, the distance matrix is not necessarily symmetric, since the edges can only be traversed in one direction (i.e., \(\text{dist}(A, B)\) may not be equal to \(\text{dist}(B, A)\)).

See also

pygraphs.bfs()

Core implementation of BFS.

pygraphs.bfs_distances()

Perform a breadth-first search (BFS) to compute the shortest path distances from a starting vertex to all other vertices in the graph, where the distance is defined as the number of edges in the shortest path between the vertices.

Examples

Create a simple disconnected graph of 7 vertices and compute the shortest path distance matrix for all pairs of vertices in the graph.

Disconnected graph with 7 vertices for bfs matrix example. Distance from vertex 0 to vertex 4 is 3 (0 -> 2 -> 3 -> 4). Thus dist[0, 4] = 3 and dist[4, 0] = 3 for this undirected graph.

from pygraphs import bfs_matrix, Graph

graph = [[1, 2], [0, 2], [0, 1, 3], [2, 4], [3], [6], [5]]
graph = Graph.from_adjacency(graph)

adjacency_matrix = bfs_matrix(graph)
print(f"adjacency_matrix (shape={len(adjacency_matrix)}x{len(adjacency_matrix[0])}):")
print(adjacency_matrix)

adjacency_matrix (shape=(7x7)):
[[ 0  1  1  2  3 -1 -1]
 [ 1  0  1  2  3 -1 -1]
 [ 1  1  0  1  2 -1 -1]
 [ 2  2  1  0  1 -1 -1]
 [ 3  3  2  1  0 -1 -1]
 [-1 -1 -1 -1 -1  0  1]
 [-1 -1 -1 -1 -1  1  0]]

Note

For undirected graphs (graph.is_directed() == False), the distance matrix is symmetric.

This method can be applied for directed graphs as well, where the adjacency list represents the outgoing neighbors of each vertex.

Directed graph with 7 vertices for bfs matrix example. Distance from vertex 2 to vertex 0 is 2 (2 -> 1 -> 0) and distance from vertex 0 to vertex 2 is 1 (0 -> 2).

from pygraphs import compute_adjacency_matrix, Graph

graph = [[1, 2], [0, 2], [1, 3], [4], [3], [6], []]
graph = Graph.from_adjacency(graph)

adjacency_matrix = bfs_matrix(graph)
print(f"adjacency_matrix (shape={len(adjacency_matrix)}x{len(adjacency_matrix[0])}):")
print(adjacency_matrix)

adjacency_matrix (shape=(7x7)):
[[ 0  1  1  2  3 -1 -1]
 [ 1  0  1  2  3 -1 -1]
 [ 2  1  0  1  2 -1 -1]
 [ 3  2  1  0  1 -1 -1]
 [ 4  3  2  1  0 -1 -1]
 [-1 -1 -1 -1 -1  0  1]
 [-1 -1 -1 -1 -1 -1 0]]