icentral_subgraph/
find_single_source_shortest_paths.rs

1crate::ix!();
2
3impl FindSingleSourceShortestPaths for SubGraph {
4
5    fn find_single_source_shortest_paths(&self, s: NodeId) 
6    -> Result<DistanceMap,BetweennessCentralityError> 
7    {
8        debug!("finding single source shortest paths from source {}", s);
9
10        let mut distances = DistanceMap::new(
11            self.nodes_map.len(), 
12            &format!{"node{}_sssp_distance", s}
13        );
14
15        let queue_name = name![
16            self.name(),
17            "find_single_source_shortest_paths::queue"
18        ];
19
20        let mut queue = NodeIdQueue::empty(queue_name);
21
22        queue.enqueue(s);
23
24        distances.set_zero_distance(s);
25
26        while let Some(v) = queue.dequeue() {
27
28            let nbrs = self.neighbors(v).clone();
29
30            for &nbr in nbrs.iter() {
31
32                if distances.is_infinite(nbr) {
33
34                    distances.set_one_step_away(nbr,v);
35
36                    queue.enqueue(nbr);
37                }
38            }
39        }
40
41        Ok(distances)
42    }
43}