pygraphs.bfs_k_ring

bfs_k_ring(graph, start, distance, *, _skip_check=False)

Return all vertices with distance equal to \(k\) (ie \(\{v \in V | \text{dist}(i, v) = 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 at this distance from the starting vertex.

• _skip_check (bool)

Returns:

A list of vertex indices representing the vertices in the adjacency ring of the starting vertex at the specified distance. If no vertices are found at the specified distance, an empty list is returned.

Return type:

List[int]

See also

pygraphs.bfs()

Core implementation of BFS.

pygraphs.bfs_k_annulus()

Call this function with inner_distance = k 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 1 and 2 are the only vertices in the neighborhood of vertex 0 for distance = 1.

from pygraphs import bfs_k_ring, Graph

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

neighborhood = bfs_k_ring(
    graph, start_vertex, distance
)
print(neighborhood)

[1, 2]

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

from pygraphs import bfs_k_ring, Graph

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

neighborhood = bfs_k_ring(
    graph, start_vertex, distance
)
print(neighborhood)

[1, 3]