pygraphs.bfs_k_annulus#

bfs_k_annulus(graph, start, inner_distance, outer_distance, *, _skip_check=False)[source]#

Return all vertices with distance in \([k_1, k_2]\) (ie \(\{v \in V | \text{dist}(i, v) \in [k_1, k_2]\}\)) where \(k_1\) and \(k_2\) are the specified inner and outer distances.

Parameters:

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

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

  • inner_distance (Optional[Integral]) – The minimum distance \(k_1\) for the neighborhood of the starting vertex, where the neighborhood includes all vertices that are at least this distance from the vertex. If None, there is no minimum distance and all vertices that are at least 0 distance from the vertex are included.

  • outer_distance (Optional[Integral]) – The maximum distance \(k_2\) for the neighborhood of the starting vertex, where the neighborhood includes all vertices that are at most this distance from the vertex. If None, there is no maximum distance and all vertices that are reachable from the starting vertex are included.

  • _skip_check (bool)

Returns:

A list of vertex indices representing the vertices in the adjacency annulus of the starting vertex in the graph (i.e., the set of vertices that are between inner_distance and outer_distance from the starting vertex).

Return type:

List[int]

See also

pygraphs.bfs()

Core implementation of BFS.

pygraphs.bfs_k_disk()

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

pygraphs.bfs_k_ring()

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

pygraphs.bfs_distances()

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 extract the vertices within distance range.

../../_images/graph.png

Disconnected graph with 7 vertices for BFS example. Vertices 1, 2 and 3 are the only vertices in the neighborhood of vertex 0 for inner_distance = 1 and outer_distance = 2.#

 1from pygraphs import bfs_k_annulus, Graph
 2
 3graph = [[1, 2], [0, 2], [0, 1, 3], [2, 4], [3], [6], [5]]
 4start_vertex = 0
 5inner_distance = 1
 6outer_distance = 2
 7
 8neighborhood = bfs_k_annulus(
 9    graph, start_vertex, inner_distance, outer_distance
10)
11print(neighborhood)

[1, 2, 3]

This method can be applied for directed graphs as well, where the adjacency list represents the outgoing neighbors of each vertex.

../../_images/graph_directed.png

Directed graph with 7 vertices for BFS example. Vertices 1 and 3 are the only vertices in the neighborhood of vertex 2 for inner_distance = 1 and outer_distance = 1.#

 1from pygraphs import bfs_k_annulus, Graph
 2
 3graph = [[1, 2], [0, 2], [1, 3], [4], [3], [6], []]
 4start_vertex = 2
 5inner_distance = 1
 6outer_distance = 1
 7
 8neighborhood = bfs_k_annulus(
 9    graph, start_vertex, inner_distance, outer_distance
10)
11print(neighborhood)

[1, 3]