icentral-graph 0.1.0

A Rust library for advanced graph manipulation, focusing on minimum union cycles, betweenness centrality, and biconnected components.
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

crate::ix!();

impl<GH> FindSingleSourceShortestPaths for Graph<GH> {

    fn find_single_source_shortest_paths(&self, s: NodeId) 
    -> Result<DistanceMap,BetweennessCentralityError> 
    {
        let distances_name = name!(self.name(), format!("sssp_distances_for_{}", s));

        let mut distances = DistanceMap::new(
            self.num_nodes(), 
            distances_name
        );

        let queue_name = name![
            self.name(), 
            format!("find_single_source_shortest_paths_for_{}::queue", s)
        ];

        let mut queue = NodeIdQueue::empty(queue_name);

        queue.enqueue(s);

        distances.set_zero_distance(s);

        while let Some(v) = queue.dequeue() {

            let nbr_vec = self.neighbors(v);

            for &nbr in nbr_vec.iter() {

                if distances.is_infinite(nbr) {

                    distances.set_one_step_away(nbr, v);

                    queue.enqueue(nbr);
                }
            }
        }

        Ok(distances)
    }
}