pygraphs.bfs_k_disk

bfs_k_disk(graph, start, distance, *, self_neighborhood=True, _skip_check=False)

Return all vertices with distance lower than \(k\) (ie \(\{v \in V | \text{dist}(i, v) \leq k\}\)) where \(k\) is the specified distance.

Parameters:

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

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

• distance (Integral) – The adjacency radius \(k\) for the neighborhood of the starting vertex, where the neighborhood includes all vertices that are within this distance from the vertex.

• self_neighborhood (bool, optional (default: True)) – 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.

• _skip_check (bool)

Returns:

A list of vertex indices representing the vertices in the adjacency disk of the starting vertex in the graph (i.e., the set of vertices that are within the specified distance from the starting vertex).

Return type:

List[int]

See also

pygraphs.bfs()

Core implementation of BFS.

pygraphs.bfs_k_annulus()

Call this function with inner_distance = 0 and outer_distance = k to extract the vertices in a adjacency annulus of a starting vertex in the graph.

Examples

Create a simple disconnected graph of 7 vertices and extract the vertices within distance range.

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 distance = 2.

from pygraphs import bfs_k_disk, Graph

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

neighborhood = bfs_k_disk(
    graph, start_vertex, distance, self_neighborhood=True
)
print(neighborhood)

[0, 1, 2, 3]

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

from pygraphs import bfs_k_disk, Graph

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

neighborhood = bfs_k_disk(
    graph, start_vertex, distance, self_neighborhood=False
)
print(neighborhood)

[1, 3]