icentral_graph/
get_shortest_path.rs

1crate::ix!();
2
3impl<GH> GetShortestPath for Graph<GH> {
4
5    fn get_shortest_path(&mut self, 
6        src:      NodeId,
7        dst:      NodeId)  
8    -> Result<Vec<NodeId>,BetweennessCentralityError> 
9    {
10        debug!("finding the shortest path between src={} and dst={}", src, dst);
11
12        let len = self.num_nodes();
13
14        let distances_name  = name![self.name(), "get_shortest_path::distances"];
15        let parent_vec_name = name![self.name(), "get_shortest_path::parent_vec"];
16
17        // do a BFS from dst to src and store path
18        //
19        let mut distances  = DistanceMap::new(len, distances_name);
20        let mut parent_vec = PredecessorMap::new(len, parent_vec_name);
21
22        let queue_name = name![self.name(), "get_shortest_path::queue"];
23
24        let mut queue = NodeIdQueue::empty(queue_name);
25
26        distances.set_zero_distance(dst);
27
28        queue.enqueue(dst);
29
30        while let Some(node) = queue.dequeue() {
31
32            if node == src {
33                break;
34            }
35
36            let nbr_vec = self.neighbors(node);
37
38            for &nbr_id in nbr_vec.iter() {
39
40                if distances.is_infinite(nbr_id) {
41
42                    distances.set_distance_for_node(
43                        nbr_id, 
44                        distances.distance(node) + 1.0
45                    );
46
47                    parent_vec.set_predecessor_for_node(nbr_id, node);
48
49                    queue.enqueue(nbr_id);
50                }
51            }
52        }
53
54        // fill the output path vector:
55        let mut node_path = vec![];
56
57        let mut nd: NodeId = src;
58
59        while parent_vec.has_predecessor(nd) {
60
61            node_path.push(nd);
62
63            nd = parent_vec.predecessor_for_node(nd);
64        }
65
66        // insert dst
67        node_path.push(nd);
68
69        Ok(node_path)
70    }
71}
icentral_graph/get_shortest_path.rs

icentral_graph/
get_shortest_path.rs
