pysdic.compute_neighborhood#

compute_neighborhood(graph, max_distance=1, self_neighborhood=True)[source]#

Compute the neighborhood of each 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.

Note

The neighborhood of a vertex is computed using a breadth-first search (BFS) algorithm for each vertex in the graph, where the BFS is limited to a maximum distance specified by max_distance.

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 (Integral, optional) – The maximum distance to consider for the neighborhood of each vertex. The neighborhood will include all vertices that are within this distance from the vertex in the connectivity of the mesh. By default 1, which means that only directly adjacent vertices will be included in the neighborhood.

  • self_neighborhood (bool, optional) – If True, the neighborhood of each vertex will include the vertex itself (i.e., the vertex will be considered as part of its own neighborhood). If False, the neighborhood of each vertex will not include the vertex itself. By default True.

Returns:

A list where each element is a list containing the indices of the neighboring vertices for the corresponding vertex in the graph.

Return type:

List[List[int]]

Notes

The neighborhood of a vertex i in the graph is defined as all vertices j such that the distance between vertex i and vertex j in the graph is less than or equal to 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.

compute_vertices_neighborhood()

Compute the neighborhood of each vertex in the mesh based on the connectivity and a specified maximum distance.

compute_elements_neighborhood()

Compute the neighborhood of each element in the mesh based on the connectivity and a specified maximum distance.

Examples

Create a simple disconnected graph of 7 vertices and compute the neighborhood of each 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.

../_images/graph_bfs.png

Disconnected graph with 7 vertices for BFS example. Neighborhood of vertex 0 with max_distance=2 includes vertices 0, 1, 2 and 3 since they are within a distance of 2 from vertex 0 in the graph.#

 1from pysdic import compute_neighborhood
 2
 3graph = [[1, 2], [0, 2], [0, 1, 3], [2, 4], [3], [6], [5]]
 4start_vertex = 0
 5max_distance = 2
 6
 7neighborhoods = compute_neighborhood(
 8    graph, max_distance, self_neighborhood=True
 9)
10
11print(f"neighborhood length: {len(neighborhoods)}")
12subneighborhood = neighborhoods[0]
13print(f"neighborhood of vertex 0 with max_distance={max_distance}: {subneighborhood}")

neighborhood length: 7
neighborhood of vertex 0 with max_distance=2: [0, 1, 2, 3]
On this page

This Page