fn get_shortest_paths()

in src/dachshund/algorithms/shortest_paths.rs [15:68]

• 46 lines of code
• 11 McCabe index (conditional complexity)

    fn get_shortest_paths(
        &self,
        source: NodeId,
        // nodes in the connected component to which source belongs. If you don't have
        // this available, just pass None. Returned distances will only be to those
        // nodes anyway (but this optimization saves some compute)
        nodes_in_connected_component: &Option<Vec<NodeId>>,
    ) -> (
        HashMap<NodeId, Option<usize>>,
        HashMap<NodeId, HashSet<NodeId>>,
    ) {
        // TODO: this should be changed to a binary heap
        let mut queue: HashSet<&NodeId> = HashSet::new();
        let mut dist: HashMap<NodeId, Option<usize>> = HashMap::new();
        let mut parents: HashMap<NodeId, HashSet<NodeId>> = HashMap::new();

        let targets: Vec<NodeId> = match nodes_in_connected_component {
            Some(x) => x.to_vec(),
            None => self.get_ids_iter().cloned().collect(),
        };
        for id in &targets {
            queue.insert(&id);
            dist.insert(*id, None);
            parents.insert(*id, HashSet::new());
        }
        *dist.get_mut(&source).unwrap() = Some(0);

        while !queue.is_empty() {
            let mut min_dist: Option<usize> = None;
            let mut u: Option<&NodeId> = None;
            // find next node u to visit
            for maybe_u in &queue {
                let d: Option<usize> = dist[maybe_u];
                if d != None && (min_dist == None || d.unwrap() < min_dist.unwrap()) {
                    min_dist = Some(d.unwrap());
                    u = Some(maybe_u);
                }
            }
            // remove u from queue
            queue.remove(u.unwrap());
            for e in self.get_node(*u.unwrap()).get_edges() {
                let v = &e.get_neighbor_id();
                if queue.contains(v) {
                    let alt = min_dist.unwrap() + 1;
                    if dist[v] == None || alt <= dist[v].unwrap() {
                        *dist.get_mut(v).unwrap() = Some(alt);
                        parents.get_mut(v).unwrap().insert(*u.unwrap());
                    }
                }
            }
        }
        parents.get_mut(&source).unwrap().insert(source);
        (dist, parents)
    }