pygraphs.dijkstra_k_annulus#

dijkstra_k_annulus(graph, start, inner_distance, outer_distance, *, weight_key='weight', _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 Dijkstra.

  • inner_distance (Optional[Real]) – 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[Real]) – 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.

  • weight_key (str (default: 'weight')) – The key-name of the weight to use in the graph dictionnary structure. If an edge does not have weight, default weight is 1.0.

  • _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.dijkstra()

Core implementation of Dijkstra.

pygraphs.dijkstra_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.

Examples

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

../../_images/weighted_graph.png

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

 1from pygraphs import dijkstra_k_annulus, Graph
 2
 3graph = [
 4    [(1, 1.2), (2, 0.2)],
 5    [(0, 1.2), (2, 1.5)],
 6    [(0, 0.2), (1, 1.5), (3, 3.2)],
 7    [(2, 3.2), (4, 1.4)],
 8    [(3, 1.4)],
 9    [(6, 2.3)],
10    [(5, 2.3)]
11]
12graph = Graph.from_adjacency(graph)
13start_vertex = 0
14inner_distance = 0.1
15outer_distance = 4.0
16
17neighborhood = dijkstra_k_annulus(graph, start_vertex, inner_distance, outer_distance)
18print(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/weighted_graph_directed.png

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

 1from pygraphs import dijkstra_k_annulus, Graph
 2
 3graph = [
 4    [(1, 1.2), (2, 0.2)],
 5    [(0, 1.2), (2, 1.5)],
 6    [(1, 1.5), (3, 3.2)],
 7    [(2, 1.4), (4, 1.4)],
 8    [(3, 1.4)],
 9    [(6, 2.3)],
10    []
11]
12graph = Graph.from_adjacency(graph)
13start_vertex = 2
14inner_distance = 1.0
15outer_distance = 3.5
16
17neighborhood = dijkstra_k_annulus(graph, start_vertex, inner_distance, outer_distance)
18print(neighborhood)

[1, 3]