fn get_shortest_paths_bfs()

in src/dachshund/algorithms/shortest_paths.rs [72:119]

• 38 lines of code
• 8 McCabe index (conditional complexity)

    fn get_shortest_paths_bfs(
        &self,
        source: NodeId,
    ) -> (
        Vec<NodeId>,          // nodes in nondecreasing order by distance
        HashMap<NodeId, u32>, // distances from source
        NodePredecessors,     // immediate predecessors
    ) {
        // Predecessors of v (nodes immediately before v on shortest path from source to v)
        let mut preds: NodePredecessors = HashMap::new();
        // Count of shortest paths to from source to v
        let mut shortest_path_counts: HashMap<NodeId, u32> = HashMap::new();
        // Distances from source to v
        let mut dists: HashMap<NodeId, i32> = HashMap::new();

        for node_id in self.get_ids_iter() {
            preds.insert(*node_id, Vec::new());
            shortest_path_counts.insert(*node_id, if node_id == &source { 1 } else { 0 });
            dists.insert(*node_id, if node_id == &source { 0 } else { -1 });
        }

        // A stack tracking the order in which we explored the nodes.
        let mut stack = Vec::new();
        // A queue tracking the remaining nodes to explore
        let mut queue = VecDeque::new();
        queue.push_back(source);

        while !queue.is_empty() {
            let v = queue.pop_front().unwrap();
            stack.push(v);
            let node = &self.get_node(v);
            for edge in node.get_edges() {
                let neighbor_id = edge.get_neighbor_id();
                // neighbor_id newly discovered
                if dists[&neighbor_id] < 0 {
                    queue.push_back(neighbor_id);
                    *dists.entry(neighbor_id).or_insert(0) = dists[&v] + 1;
                }
                // shortest path to neighbor_id via v?
                if dists[&neighbor_id] == dists[&v] + 1 {
                    *shortest_path_counts.entry(neighbor_id).or_insert(0) +=
                        shortest_path_counts[&v];
                    preds.get_mut(&neighbor_id).unwrap().push(v);
                }
            }
        }
        (stack, shortest_path_counts, preds)
    }