petgraph 0.8.1

Graph data structure library. Provides graph types and graph algorithms.
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131

//! Shortest Path Faster Algorithm.
use super::{bellman_ford::Paths, BoundedMeasure, NegativeCycle};
use crate::prelude::*;
use crate::visit::{IntoEdges, IntoNodeIdentifiers, NodeIndexable};
use alloc::{vec, vec::Vec};

/// \[Generic\] Compute shortest paths from node `source` to all other.
///
/// Using the [Shortest Path Faster Algorithm][spfa].
/// Compute shortest distances from node `source` to all other.
///
/// Compute shortest paths lengths in a weighted graph with positive or negative edge weights,
/// but with no negative cycles.
///
/// ## Arguments
/// * `graph`: weighted graph.
/// * `source`: the source vertex, for which we calculate the lengths of the shortest paths to all the others.
/// * `edge_cost`: closure that returns cost of a particular edge
///
/// ## Returns
/// * `Err`: if graph contains negative cycle.
/// * `Ok`: a pair of a vector of shortest distances and a vector
///   of predecessors of each vertex along the shortest path.
///
/// [spfa]: https://www.geeksforgeeks.org/shortest-path-faster-algorithm/
///
/// # Example
///
/// ```
/// use petgraph::Graph;
/// use petgraph::algo::spfa;
///
/// let mut g = Graph::new();
/// let a = g.add_node(()); // node with no weight
/// let b = g.add_node(());
/// let c = g.add_node(());
/// let d = g.add_node(());
/// let e = g.add_node(());
/// let f = g.add_node(());
/// g.extend_with_edges(&[
///     (0, 1, 3.0),
///     (0, 3, 2.0),
///     (1, 2, 1.0),
///     (1, 5, 7.0),
///     (2, 4, -4.0),
///     (3, 4, -1.0),
///     (4, 5, 1.0),
/// ]);
///
/// // Graph represented with the weight of each edge.
/// //
/// //     3       1
/// // a ----- b ----- c
/// // | 2     | 7     |
/// // d       f       | -4
/// // | -1    | 1     |
/// // \------ e ------/
///
/// let path = spfa(&g, a, |edge| *edge.weight());
/// assert!(path.is_ok());
/// let path = path.unwrap();
/// assert_eq!(path.distances, vec![0.0 ,     3.0,     4.0,    2.0,     0.0,     1.0]);
/// assert_eq!(path.predecessors, vec![None, Some(a), Some(b), Some(a), Some(c), Some(e)]);
///
///
/// // Negative cycle.
/// let graph = Graph::<(), f32>::from_edges(&[
///     (0, 1, 2.0), (1, 2, 2.0), (2, 0, -10.0)]);
///
/// assert!(spfa(&graph, 0.into(), |edge| *edge.weight()).is_err());
/// ```
pub fn spfa<G, F, K>(
    graph: G,
    source: G::NodeId,
    mut edge_cost: F,
) -> Result<Paths<G::NodeId, K>, NegativeCycle>
where
    G: IntoEdges + IntoNodeIdentifiers + NodeIndexable,
    F: FnMut(G::EdgeRef) -> K,
    K: BoundedMeasure + Copy,
{
    let ix = |i| graph.to_index(i);

    let mut predecessors = vec![None; graph.node_bound()];
    let mut distances = vec![K::max(); graph.node_bound()];
    distances[ix(source)] = K::default();

    // Queue of vertices capable of relaxation of the found shortest distances.
    let mut queue: Vec<G::NodeId> = Vec::with_capacity(graph.node_bound());
    let mut in_queue = vec![false; graph.node_bound()];

    queue.push(source);
    in_queue[ix(source)] = true;

    // Keep track of how many times each vertex appeared
    // in the queue to be able to detect a negative cycle.
    let mut visits = vec![0; graph.node_bound()];

    while let Some(i) = queue.pop() {
        in_queue[ix(i)] = false;

        // In a graph without a negative cycle, no vertex can improve
        // the shortest distances by more than |V| times.
        if visits[ix(i)] >= graph.node_bound() {
            return Err(NegativeCycle(()));
        }
        visits[ix(i)] += 1;

        for edge in graph.edges(i) {
            let j = edge.target();
            let w = edge_cost(edge);

            let (dist, overflow) = distances[ix(i)].overflowing_add(w);

            if !overflow && dist < distances[ix(j)] {
                distances[ix(j)] = dist;
                predecessors[ix(j)] = Some(i);

                if !in_queue[ix(j)] {
                    in_queue[ix(j)] = true;
                    queue.push(j);
                }
            }
        }
    }

    Ok(Paths {
        distances,
        predecessors,
    })
}