pysdic.compute_adjacency_matrix#

compute_adjacency_matrix(graph, max_distance=None)[source]#

Compute the adjacency matrix from the adjacency graph of the vertices, where the distance between two vertices is defined as the minimum number of elements that must be traversed to go from one vertex to another.

The output is a symmetric square matrix of shape (\(N_v\), \(N_v\)), where \(N_v\) is the number of vertices, and the value at position (i, j) represents the distance between vertex i and vertex j in the graph.

Note

The computation of the adjacency matrix is performed using a breadth-first search (BFS) algorithm for each vertex 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.

  • max_distance (Optional[Integral], optional) – The maximum distance to consider between vertices. If the distance between two vertices exceeds this value, the corresponding entry in the adjacency matrix will be set to -1. If None, there is no maximum distance and all distances will be computed. By default None.

Returns:

A square array of shape (\(N_v\), \(N_v\)) representing the path distance matrix between vertices, where the value at position (i, j) represents the distance between vertex i and vertex j in the graph.

Return type:

numpy.ndarray

See also

bfs_distance()

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.

compute_vertices_adjacency_matrix()

Convenience function to compute the vertices path distance matrix (adjacency matrix) from the connectivity of the mesh.

compute_elements_adjacency_matrix()

Convenience function to compute the elements path distance matrix (adjacency matrix) from the connectivity of the mesh.

Notes

The distance between two vertices i and j in the graph is defined as follows:

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

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

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

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

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

Examples

Create a simple disconnected graph of 7 vertices and build the adjacency matrix from the adjacency graph of the vertices, where the distance between two vertices is defined as the minimum number of elements that must be traversed to go from one vertex to another.

../_images/graph_bfs.png

Disconnected graph with 7 vertices for adjacency matrix example.#

1from pysdic import compute_adjacency_matrix
2
3graph = [[1, 2], [0, 2], [0, 1, 3], [2, 4], [3], [6], [5]]
4start_vertex = 0
5max_distance = None
6
7adjacency_matrix = compute_adjacency_matrix(graph, max_distance=max_distance)
8print(f"adjacency_matrix (shape={adjacency_matrix.shape}):")
9print(adjacency_matrix)

adjacency_matrix (shape=(7, 7)):
[[ 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]]
On this page

This Page