pygraphs.dijkstra_k_disk#

dijkstra_k_disk(graph, start, distance, *, weight_key='weight', self_neighborhood=True, _skip_check=False)[source]#

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 Dijkstra.

  • 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.

  • 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.

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

Core implementation of Dijkstra.

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

../../_images/weighted_graph.png

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

 1from pygraphs import dijkstra_k_disk, 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
14distance = 4.0
15
16neighborhood = dijkstra_k_disk(graph, start_vertex, distance)
17print(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.

../../_images/weighted_graph_directed.png

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

 1from pygraphs import dijkstra_k_disk, 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
14distance = 3.5
15
16neighborhood = dijkstra_k_disk(graph, start_vertex, distance)
17print(neighborhood)

[0, 1, 3]