fn get_coreness_values()

in src/dachshund/algorithms/coreness.rs [102:157]

• 42 lines of code
• 6 McCabe index (conditional complexity)

    fn get_coreness_values(&self) -> HashMap<NodeId, usize> {
        // Traverse the nodes in increasing order of degree to calculate coreness.
        // See: https://arxiv.org/abs/cs/0310049 for an explanation of the bookkeeping details.

        // The initial value for the coreness of each node is its degree.
        let mut coreness: HashMap<NodeId, usize> = self
            .get_nodes_iter()
            .map(|x| (x.get_id(), x.degree()))
            .collect();

        // Nodes in increasing order of coreness. We process this in order
        // and keep in order as we delete edges.
        let mut nodes: Vec<NodeId> = coreness.keys().cloned().collect();
        nodes.sort_unstable_by_key(|node_id| coreness[node_id]);

        let mut bin_starts = self._init_bin_starts(&nodes, &coreness);

        let mut node_idx: HashMap<NodeId, usize> = HashMap::new();
        for (i, &node) in nodes.iter().enumerate() {
            node_idx.insert(node, i);
        }

        let mut neighbors: HashMap<NodeId, FxHashSet<NodeId>> = HashMap::new();
        for node in self.get_nodes_iter() {
            neighbors.insert(
                node.get_id(),
                FxHashSet::<NodeId>::from_iter(node.get_edges().map(|edge| edge.get_neighbor_id())),
            );
        }

        for i in 0..nodes.len() {
            let node_id = nodes[i];
            let node_nbrs: Vec<NodeId> = neighbors.get(&node_id).unwrap().iter().cloned().collect();
            for nbr_id in node_nbrs {
                let nbr_coreness = coreness[&nbr_id];
                if nbr_coreness > coreness[&node_id] {
                    neighbors.get_mut(&nbr_id).unwrap().remove(&node_id);
                    let nbr_idx = node_idx[&nbr_id];
                    let nbr_bin_start = bin_starts[nbr_coreness];

                    let nbr_idx_ptr = node_idx.get_mut(&nbr_id).unwrap() as *mut usize;
                    let bin_start_node_idx_ptr =
                        node_idx.get_mut(&nodes[nbr_bin_start]).unwrap() as *mut usize;
                    unsafe {
                        std::ptr::swap(nbr_idx_ptr, bin_start_node_idx_ptr);
                    }
                    nodes.swap(nbr_idx, nbr_bin_start);

                    bin_starts[nbr_coreness] += 1;
                    *coreness.entry(nbr_id).or_default() -= 1;
                }
            }
        }

        coreness
    }