floyd-warshall 0.0.3

Efficient all-pairs-shortest-paths algorithm for the petgraph library using the floyd-warshall algorithm.
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

use super::floyd_warshall;

#[test]
fn test_no_intermediate() {
    use petgraph::Graph;
    let mut graph = Graph::new_undirected();

    let a = graph.add_node(0);
    let b = graph.add_node(1);
    let c = graph.add_node(2);
    let d = graph.add_node(3);

    graph.extend_with_edges(
        &[
            (a, b, 1usize),
            (a, c, 1usize),
            (a, d, 1usize),
            (b, c, 1usize),
            (b, d, 1usize),
            (c, d, 1usize),
        ],
    );

    let m = floyd_warshall(&graph);
    println!("{:?}", m);

    for i in 0..4 {
        for j in 0..4 {
            if i == j {
                assert_eq!(m.get_path_len(i, j), 0);
            } else {
                assert_eq!(m.get_path_len(i, j), 1);
            }
        }
    }
}

#[test]
fn test_intermediate() {
    use petgraph::Graph;
    let mut graph = Graph::new_undirected();

    let a = graph.add_node(0);
    let b = graph.add_node(1);
    let c = graph.add_node(2);

    graph.extend_with_edges(&[(a, b, 1usize), (b, c, 1), (a, c, 3)]);

    let m = floyd_warshall(&graph);
    println!("{:?}", m);

    assert_eq!(m.get_path_len(0, 0), 0);
    assert_eq!(m.get_path_len(1, 1), 0);
    assert_eq!(m.get_path_len(2, 2), 0);

    assert_eq!(m.get_path_len(0, 1), 1);
    assert_eq!(m.get_path_len(1, 2), 1);
    assert_eq!(m.get_path_len(0, 2), 2);
}

// #[test]
// fn test_cache_friendliness() {
//     use petgraph::Graph;

//     let mut graph: Graph<usize, usize, _, _> = Graph::new_undirected();
//     for i in 0..10 {
//         graph.add_node(i);
//     }
//     let dists = floyd_warshall(&graph);

//     println!("{:?}", dists);
// }

#[test]
#[ignore]
fn test_random() {
    use petgraph::Graph;
    use rand;
    use rand::Rng;

    let mut graph = Graph::new_undirected();
    let mut rng = rand::thread_rng();
    let mut vec = Vec::new();

    for i in 0..10 {
        vec.push(graph.add_node(i));
    }

    for v1 in &vec {
        for v2 in &vec {
            if v1 != v2 && rng.next_f32() < 0.1 {
                let w = (rng.next_u64() as usize) % 100;
                graph.add_edge(*v1, *v2, w);
            }
        }
    }

    let m = floyd_warshall(&graph);
    println!("{:?}", m);

    use petgraph::dot::Dot;
    use std::fs::File;
    use std::io::prelude::*;

    let mut file = File::create("random.dot").unwrap();
    let b = format!("{:?}", Dot::new(&graph));
    let b = b.as_bytes();
    file.write_all(b).unwrap();

    loop {
        let i: usize = read!();
        let j: usize = read!();

        if m.does_path_exist(i, j) {

            let len = m.get_path_len(i, j);
            let path = m.get_path_iter(i, j);

            let path: Vec<&usize> = if i > j {
                path.rev().collect()
            } else {
                path.collect()
            };

            println!("The path from {} to {} has total length {}.", i, j, len);
            println!("Path: {:?}", path);
        } else {
            println!("There is no path from {} to {}.", i, j)
        }
    }
}