petgraph-live 0.3.1

Generic generation-keyed graph cache, disk snapshot, and graph algorithms for petgraph 0.8
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
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152

use petgraph::visit::{IntoEdges, IntoNeighbors, NodeIndexable, VisitMap, Visitable};

/// The lengths of the shortest paths from the start vertex to all the others.
///
/// Based on BFS. Path length equals number of edges. Returns `Vec<f32>` indexed by
/// `NodeIndexable::to_index`. Unreachable nodes get `f32::INFINITY`.
/// Time complexity: **O(|V| + |E|)**.
///
/// # Examples
///
/// ```
/// use petgraph_live::shortest_path::shortest_distances;
/// use petgraph::Graph;
///
/// let inf = f32::INFINITY;
/// let graph = Graph::<u8, ()>::from_edges(&[(0, 1), (0, 2), (1, 2)]);
///
/// assert_eq!(shortest_distances(&graph, 0.into()), vec![0.0, 1.0, 1.0]);
/// assert_eq!(shortest_distances(&graph, 1.into()), vec![inf, 0.0, 1.0]);
/// ```
pub fn shortest_distances<G>(graph: G, start: G::NodeId) -> Vec<f32>
where
    G: Visitable + NodeIndexable + IntoEdges + IntoNeighbors,
{
    use std::collections::VecDeque;

    let mut visit_map = graph.visit_map();
    visit_map.visit(start);

    let mut dist = vec![f32::INFINITY; graph.node_bound()];
    dist[graph.to_index(start)] = 0.0;

    let mut queue: VecDeque<G::NodeId> = VecDeque::new();
    queue.push_back(start);

    while let Some(current) = queue.pop_front() {
        for v in graph.neighbors(current) {
            if visit_map.visit(v) {
                queue.push_back(v);
                dist[graph.to_index(v)] = dist[graph.to_index(current)] + 1.0;
            }
        }
    }

    dist
}

#[cfg(test)]
mod tests {
    use super::*;
    use petgraph::graph::Graph;

    fn graph1() -> Graph<u8, ()> {
        let mut graph = Graph::<u8, ()>::new();
        let n0 = graph.add_node(0);
        let n1 = graph.add_node(1);
        let n2 = graph.add_node(2);
        let n3 = graph.add_node(3);
        let n4 = graph.add_node(4);
        let n5 = graph.add_node(5);
        let n6 = graph.add_node(6);
        let n7 = graph.add_node(7);
        let n8 = graph.add_node(8);
        let n9 = graph.add_node(9);
        let n10 = graph.add_node(10);
        let n11 = graph.add_node(11);

        graph.add_edge(n0, n1, ());
        graph.add_edge(n0, n2, ());
        graph.add_edge(n2, n3, ());
        graph.add_edge(n2, n5, ());
        graph.add_edge(n3, n4, ());
        graph.add_edge(n4, n8, ());
        graph.add_edge(n5, n9, ());
        graph.add_edge(n5, n6, ());
        graph.add_edge(n6, n3, ());
        graph.add_edge(n6, n7, ());
        graph.add_edge(n6, n10, ());
        graph.add_edge(n7, n8, ());
        graph.add_edge(n7, n11, ());
        graph.add_edge(n8, n11, ());
        graph.add_edge(n9, n1, ());
        graph.add_edge(n9, n10, ());
        graph.add_edge(n10, n6, ());
        graph.add_edge(n11, n6, ());
        graph.add_edge(n11, n10, ());
        graph.add_edge(n0, n9, ());

        graph
    }

    #[test]
    fn test_shortest_distances() {
        let inf = f32::INFINITY;
        let g = graph1();

        assert_eq!(
            shortest_distances(&g, g.from_index(0)),
            vec![0.0, 1.0, 1.0, 2.0, 3.0, 2.0, 3.0, 4.0, 4.0, 1.0, 2.0, 5.0]
        );
        assert_eq!(
            shortest_distances(&g, g.from_index(1)),
            vec![inf, 0.0, inf, inf, inf, inf, inf, inf, inf, inf, inf, inf]
        );
        assert_eq!(
            shortest_distances(&g, g.from_index(2)),
            vec![inf, 3.0, 0.0, 1.0, 2.0, 1.0, 2.0, 3.0, 3.0, 2.0, 3.0, 4.0]
        );
    }

    #[test]
    fn test_shortest_distances_strongly_connected() {
        let mut graph = Graph::<u8, ()>::new();
        let n0 = graph.add_node(0);
        let n1 = graph.add_node(1);
        let n2 = graph.add_node(2);
        let n3 = graph.add_node(3);
        let n4 = graph.add_node(4);
        let n5 = graph.add_node(5);
        let n6 = graph.add_node(6);

        graph.add_edge(n0, n6, ());
        graph.add_edge(n0, n1, ());
        graph.add_edge(n1, n0, ());
        graph.add_edge(n1, n2, ());
        graph.add_edge(n1, n5, ());
        graph.add_edge(n1, n6, ());
        graph.add_edge(n2, n1, ());
        graph.add_edge(n2, n3, ());
        graph.add_edge(n3, n2, ());
        graph.add_edge(n3, n4, ());
        graph.add_edge(n4, n3, ());
        graph.add_edge(n4, n5, ());
        graph.add_edge(n5, n2, ());
        graph.add_edge(n5, n6, ());
        graph.add_edge(n5, n1, ());
        graph.add_edge(n5, n4, ());
        graph.add_edge(n6, n0, ());
        graph.add_edge(n6, n1, ());
        graph.add_edge(n6, n5, ());
        graph.add_edge(n2, n5, ());

        assert_eq!(
            shortest_distances(&graph, graph.from_index(0)),
            vec![0.0, 1.0, 2.0, 3.0, 3.0, 2.0, 1.0]
        );
        assert_eq!(
            shortest_distances(&graph, graph.from_index(1)),
            vec![1.0, 0.0, 1.0, 2.0, 2.0, 1.0, 1.0]
        );
    }
}