dsalgo 0.3.10

A package for Datastructures and 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

use crate::{
    graph::edge::{
        To,
        Weight,
    },
    negative_cycle::NegativeCycleError,
};

/// BFS based bellman ford
/// O(VE) but usually faster than bellman ford.

pub fn spfa<E>(
    sparse_graph: &[Vec<E>],
    src: usize,
) -> Result<Vec<Option<i64>>, NegativeCycleError>
where
    E: To<V = usize> + Weight<i64>,
{
    let n = sparse_graph.len();

    let mut dist = vec![None; n];

    dist[src] = Some(0);

    let mut que = vec![src];

    let mut in_que = vec![false; n];

    in_que[src] = true;

    for _ in 0..n {
        let mut next_que = vec![];

        for u in que.into_iter() {
            in_que[u] = false;

            for e in &sparse_graph[u] {
                let v = *e.to();

                let dv = Some(dist[u].unwrap() + e.weight());

                if dist[v].is_some() && dv >= dist[v] {
                    continue;
                }

                dist[v] = dv;

                if !in_que[v] {
                    next_que.push(v);

                    in_que[v] = true;
                }
            }
        }

        que = next_que;

        if que.is_empty() {
            return Ok(dist);
        }
    }

    Err(NegativeCycleError::new())
}

#[cfg(test)]

mod tests {

    use super::*;

    #[test]

    fn test_negative_edge() {
        let graph = vec![
            vec![(0, 1, 2), (0, 2, 3)],
            vec![(1, 2, -5), (1, 3, 1)],
            vec![(2, 3, 2)],
            vec![],
        ];

        assert_eq!(
            spfa(&graph, 1),
            Ok(vec![None, Some(0), Some(-5), Some(-3)]),
        );
    }
}