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
88
89
90
91
92
93
94
95
96
97
98
99
100
101

use crate::negative_cycle::NegativeCycleError;

pub fn floyd_warshall(
    weight_matrix: Vec<Vec<Option<i64>>>
) -> Result<Vec<Vec<Option<i64>>>, NegativeCycleError> {
    let mut g = weight_matrix;

    let n = g.len();

    assert!((0..n).all(|i| g[i].len() == n));

    for i in 0..n {
        if g[i][i].is_none() || g[i][i] > Some(0) {
            g[i][i] = Some(0)
        }
    }

    for k in 0..n {
        for i in 0..n {
            for j in 0..n {
                if g[i][k].is_none() || g[k][j].is_none() {
                    continue;
                }

                let d = Some(g[i][k].unwrap() + g[k][j].unwrap());

                if g[i][j].is_none() || d < g[i][j] {
                    g[i][j] = d;
                }
            }
        }
    }

    if (0..n).any(|i| g[i][i] < Some(0)) {
        Err(NegativeCycleError::new())
    } else {
        Ok(g)
    }
}

#[cfg(test)]

mod tests {

    use super::*;

    #[test]

    fn test_positive() {
        let g = vec![
            vec![None, Some(1), Some(5), None],
            vec![None, None, Some(2), Some(4)],
            vec![None, None, None, Some(1)],
            vec![None, None, Some(7), None],
        ];

        assert_eq!(
            floyd_warshall(g),
            Ok(vec![
                vec![Some(0), Some(1), Some(3), Some(4)],
                vec![None, Some(0), Some(2), Some(3)],
                vec![None, None, Some(0), Some(1)],
                vec![None, None, Some(7), Some(0)],
            ]),
        )
    }

    #[test]

    fn test_negative() {
        let g = vec![
            vec![None, Some(1), Some(-5), None],
            vec![None, None, Some(2), Some(4)],
            vec![None, None, None, Some(1)],
            vec![None, None, Some(7), None],
        ];

        assert_eq!(
            floyd_warshall(g),
            Ok(vec![
                vec![Some(0), Some(1), Some(-5), Some(-4)],
                vec![None, Some(0), Some(2), Some(3)],
                vec![None, None, Some(0), Some(1)],
                vec![None, None, Some(7), Some(0)],
            ]),
        )
    }

    #[test]

    fn test_negative_cycle() {
        let g = vec![
            vec![None, Some(1), Some(5), None],
            vec![None, None, Some(2), Some(4)],
            vec![None, None, None, Some(1)],
            vec![None, None, Some(-7), None],
        ];

        assert_eq!(floyd_warshall(g), Err(NegativeCycleError::new()),)
    }
}