xgraph 3.0.0

//! Dominating sets, written once against [`GraphView`].
//!
//! A dominating set is a set of nodes such that every node in the graph is either in the
//! set or adjacent to a member of it. Finding a smallest one is NP-hard, so this is the
//! usual greedy approximation: take nodes in order of decreasing degree, and keep any that
//! is not yet covered.

use crate::core::algo::centrality::Centrality;
use crate::core::algo::traversal::TraversalError;
use crate::core::view::{GraphView, NodeId};
use std::collections::HashSet;

/// Dominating set search, available on every [`GraphView`].
pub trait DominatingSet: GraphView {
    /// Finds a dominating set greedily.
    ///
    /// An isolated node is adjacent to nothing, so it can only be dominated by itself and
    /// always joins the set. Filter the view first if such nodes should be left out.
    fn dominating_set(&self) -> Result<HashSet<NodeId>, TraversalError> {
        let degree = self.degree_centrality();

        // Highest degree first, with the node ID breaking ties so the choice — and hence
        // the resulting set — does not depend on hash iteration order.
        let mut candidates = self.node_id_vec();
        candidates.sort_unstable_by(|&left, &right| {
            degree
                .get(&right)
                .cmp(&degree.get(&left))
                .then_with(|| left.cmp(&right))
        });

        let mut dominating = HashSet::new();
        let mut covered = HashSet::new();

        for node in candidates {
            if covered.contains(&node) {
                continue;
            }
            dominating.insert(node);
            covered.insert(node);
            for link in self.links(node) {
                if !self.contains_node(link.target) {
                    return Err(TraversalError::InvalidNode(link.target));
                }
                covered.insert(link.target);
            }
        }
        Ok(dominating)
    }

    /// Checks that every node is in `candidate` or is reached by an edge out of it.
    ///
    /// The direction matters: a node is dominated when a member of the set has an edge
    /// *to* it, not when it has an edge to a member. The two coincide on an undirected
    /// graph, which is why checking the wrong one went unnoticed there.
    fn is_dominating_set(&self, candidate: &HashSet<NodeId>) -> bool {
        let mut covered: HashSet<NodeId> = candidate.clone();
        for &node in candidate {
            covered.extend(self.links(node).map(|link| link.target));
        }
        self.node_ids().all(|node| covered.contains(&node))
    }
}

impl<G: GraphView + ?Sized> DominatingSet for G {}

#[cfg(test)]
#[cfg(feature = "graph")]
mod tests {
    use super::*;
    use crate::graph::Graph;

    #[test]
    fn test_star_is_dominated_by_its_hub() {
        let mut graph = Graph::<u32, u32, ()>::new(false);
        let hub = graph.add_node(0);
        for i in 1..5 {
            let spoke = graph.add_node(i);
            graph.add_edge(hub, spoke, 1, ()).unwrap();
        }

        let dominating = graph.dominating_set().unwrap();
        assert_eq!(dominating, HashSet::from([hub]));
        assert!(graph.is_dominating_set(&dominating));
    }

    #[test]
    fn test_isolated_node_dominates_itself() {
        let mut graph = Graph::<u32, u32, ()>::new(false);
        let a = graph.add_node(0);
        let b = graph.add_node(1);
        let alone = graph.add_node(2);
        graph.add_edge(a, b, 1, ()).unwrap();

        let dominating = graph.dominating_set().unwrap();
        assert!(dominating.contains(&alone));
        assert!(graph.is_dominating_set(&dominating));
    }

    #[test]
    fn test_result_covers_every_node_of_a_path() {
        let mut graph = Graph::<u32, u32, ()>::new(false);
        let nodes: Vec<_> = (0..7).map(|i| graph.add_node(i)).collect();
        for pair in nodes.windows(2) {
            graph.add_edge(pair[0], pair[1], 1, ()).unwrap();
        }

        let dominating = graph.dominating_set().unwrap();
        assert!(graph.is_dominating_set(&dominating));
        // A path of seven needs at least three; greedy must not do worse than every node.
        assert!(dominating.len() >= 3 && dominating.len() < nodes.len());
    }

    #[test]
    fn test_empty_graph_has_an_empty_dominating_set() {
        let graph = Graph::<u32, u32, ()>::new(false);
        assert!(graph.dominating_set().unwrap().is_empty());
        assert!(graph.is_dominating_set(&HashSet::new()));
    }

    #[test]
    fn test_result_is_reproducible() {
        let mut graph = Graph::<u32, u32, ()>::new(false);
        let nodes: Vec<_> = (0..12).map(|i| graph.add_node(i)).collect();
        for pair in nodes.windows(2) {
            graph.add_edge(pair[0], pair[1], 1, ()).unwrap();
        }

        // Ties are broken by node ID, so repeated runs agree.
        let first = graph.dominating_set().unwrap();
        for _ in 0..5 {
            assert_eq!(graph.dominating_set().unwrap(), first);
        }
    }
}