pysdic.bfs_neighborhood#

bfs_neighborhood(graph, start, max_distance, self_neighborhood=True, *, _skip_type_check=False)[source]#

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.

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. The neighborhood will include all vertices that are within this distance from the vertex in the connectivity of the mesh.

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

  • _skip_type_check (bool)

Returns:

A list of vertex indices representing the neighborhood of the starting vertex, where the neighborhood includes all vertices that are within the specified distance from the vertex in the connectivity of the mesh.

Return type:

List[int]

Notes

There is some particular cases for the neighborhood of vertex \(A\) depending on the value of max_distance:

  • For max_distance = 0, the neighborhood of vertex \(A\) will include only

vertex \(A\) itself (if self_neighborhood is True). - For max_distance = 1, the neighborhood of vertex \(A\) will include vertex \(A\) itself (if self_neighborhood is True) and all its neighbors (directly extracted from the graph).

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.

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. Vertices 0, 1, 2 and 3 are the only vertices in the neighborhood of vertex 0 for max_distance = 2.#

 1from pysdic import bfs_neighborhood
 2
 3graph = [[1, 2], [0, 2], [0, 1, 3], [2, 4], [3], [6], [5]]
 4start_vertex = 0
 5max_distance = 2
 6
 7neighborhood = bfs_neighborhood(
 8    graph, start_vertex, max_distance, self_neighborhood=True
 9)
10print(neighborhood)

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

This Page