Skip to content

shortest_paths

Algorithms to calculate shortest paths in static networks

The functions in this module allow to compute shortest paths in static networks.

avg_path_length

Compute the average path length of the graph.

Parameters:

Name Type Description Default
graph pathpyG.core.graph.Graph

Input graph.

 required

Returns: float: The average path length of the graph.

Source code in src/pathpyG/algorithms/shortest_paths.py 
42
43
44
45
46
47
48
49
50
51
52
def avg_path_length(graph: Graph) -> float:
    """Compute the average path length of the graph.

    Args:
        graph (Graph): Input graph.
    Returns:
        float: The average path length of the graph.
    """
    m = graph.sparse_adj_matrix()
    dist = dijkstra(m, directed=graph.is_directed(), return_predecessors=False, unweighted=True)
    return _np.sum(dist) / (graph.n * (graph.n - 1))

diameter

Compute the diameter of the graph.

Parameters:

Name Type Description Default
graph pathpyG.core.graph.Graph

Input graph.

 required

Returns:

Name Type Description
float float

The diameter of the graph.
Source code in src/pathpyG/algorithms/shortest_paths.py 
28
29
30
31
32
33
34
35
36
37
38
39
def diameter(graph: Graph) -> float:
    """Compute the diameter of the graph.

    Args:
        graph (Graph): Input graph.

    Returns:
        float: The diameter of the graph.
    """
    m = graph.sparse_adj_matrix()
    dist = dijkstra(m, directed=graph.is_directed(), return_predecessors=False, unweighted=True)
    return _np.max(dist)

shortest_paths_dijkstra

Compute shortest paths using Dijkstra's algorithm.

Parameters:

Name Type Description Default
graph pathpyG.core.graph.Graph

Input graph.

 required

Returns:

Type Description
tuple[numpy.ndarray, numpy.ndarray]

tuple[np.ndarray, np.ndarray]: A tuple containing the distance matrix and the predecessor matrix.
Source code in src/pathpyG/algorithms/shortest_paths.py 
14
15
16
17
18
19
20
21
22
23
24
25
def shortest_paths_dijkstra(graph: Graph) -> tuple[_np.ndarray, _np.ndarray]:
    """Compute shortest paths using Dijkstra's algorithm.

    Args:
        graph (Graph): Input graph.

    Returns:
        tuple[np.ndarray, np.ndarray]: A tuple containing the distance matrix and the predecessor matrix.
    """
    m = graph.sparse_adj_matrix()
    dist, pred = dijkstra(m, directed=graph.is_directed(), return_predecessors=True, unweighted=True)
    return dist, pred