xgraph 3.0.0

//! Minimum spanning trees, written once against [`GraphView`].
//!
//! A minimum spanning forest is a cycle-free subset of the edges that keeps every pair of
//! nodes connected that was connected before, at the lowest total weight. On a graph with
//! several components there is one tree per component, which is why the result is a forest
//! and the API says so.
//!
//! The library advertises logistics and routing as use cases and had no spanning-tree
//! algorithm at all.

use crate::core::algo::traversal::TraversalError;
use crate::core::view::{EdgeId, GraphView, NodeId};
use std::collections::HashMap;

/// A disjoint-set forest with union by size and full path compression.
///
/// Kruskal's algorithm is only near-linear because this answers "are these two nodes
/// already joined?" in effectively constant time.
#[derive(Debug, Default)]
pub struct DisjointSets {
    parent: HashMap<NodeId, NodeId>,
    size: HashMap<NodeId, usize>,
}

impl DisjointSets {
    /// Creates an empty forest.
    pub fn new() -> Self {
        Self::default()
    }

    /// Puts `node` in a set of its own, if it is not already known.
    pub fn insert(&mut self, node: NodeId) {
        self.parent.entry(node).or_insert(node);
        self.size.entry(node).or_insert(1);
    }

    /// The representative of `node`'s set, compressing the path on the way.
    pub fn find(&mut self, node: NodeId) -> NodeId {
        let mut root = node;
        while let Some(&parent) = self.parent.get(&root) {
            if parent == root {
                break;
            }
            root = parent;
        }

        // Second pass points every node on the path straight at the root.
        let mut current = node;
        while let Some(&parent) = self.parent.get(&current) {
            if current == root {
                break;
            }
            self.parent.insert(current, root);
            current = parent;
        }
        root
    }

    /// Merges the sets containing `left` and `right`.
    ///
    /// Returns `false` if they were already the same set, which is exactly the condition
    /// that makes an edge redundant.
    pub fn union(&mut self, left: NodeId, right: NodeId) -> bool {
        let (left, right) = (self.find(left), self.find(right));
        if left == right {
            return false;
        }

        // Attaching the smaller tree keeps the structure shallow.
        let (large, small) = if self.size.get(&left) >= self.size.get(&right) {
            (left, right)
        } else {
            (right, left)
        };
        self.parent.insert(small, large);
        let moved = self.size.get(&small).copied().unwrap_or(1);
        *self.size.entry(large).or_insert(1) += moved;
        true
    }

    /// Whether two nodes are already in the same set.
    pub fn connected(&mut self, left: NodeId, right: NodeId) -> bool {
        self.find(left) == self.find(right)
    }
}

/// Minimum spanning tree search, available on every [`GraphView`].
pub trait SpanningTree: GraphView {
    /// Finds a minimum spanning forest with Kruskal's algorithm.
    ///
    /// Edges come back in the order they were accepted, which is by increasing weight.
    /// On a disconnected graph the result spans each component separately.
    ///
    /// Direction is ignored: a spanning tree is an undirected notion, and running this on a
    /// directed graph treats its edges as two-way. Self-loops are never included, since
    /// they connect nothing.
    fn minimum_spanning_forest(&self) -> Result<Vec<EdgeId>, TraversalError>
    where
        Self::Weight: PartialOrd,
    {
        // Every edge once, taken from its lower-numbered endpoint so an undirected edge is
        // not considered twice.
        let mut edges: Vec<(Self::Weight, EdgeId, NodeId, NodeId)> = Vec::new();
        for node in self.node_ids() {
            for link in self.links(node) {
                if link.target == node {
                    continue;
                }
                if !self.is_directed() && link.target < node {
                    continue;
                }
                edges.push((link.weight, link.edge, node, link.target));
            }
        }

        // Sorted by weight, with the edge ID breaking ties so the result is reproducible
        // whatever order the adjacency happened to be in.
        edges.sort_by(|left, right| {
            left.0
                .partial_cmp(&right.0)
                .unwrap_or(std::cmp::Ordering::Equal)
                .then_with(|| left.1.cmp(&right.1))
        });

        let mut sets = DisjointSets::new();
        for node in self.node_ids() {
            sets.insert(node);
        }

        let mut chosen = Vec::new();
        for (_, edge, from, to) in edges {
            if sets.union(from, to) {
                chosen.push(edge);
            }
        }
        Ok(chosen)
    }

    /// The total weight of a minimum spanning forest.
    ///
    /// Returns `None` for an empty graph, where there is nothing to sum.
    fn minimum_spanning_weight(&self) -> Result<Option<Self::Weight>, TraversalError>
    where
        Self::Weight: PartialOrd + std::ops::Add<Output = Self::Weight> + Default,
    {
        let edges = self.minimum_spanning_forest()?;
        if self.node_count() == 0 {
            return Ok(None);
        }

        let mut total = Self::Weight::default();
        for edge in edges {
            let Some((from, _)) = self.edge_endpoints(edge) else {
                continue;
            };
            let Some(link) = self.links(from).find(|link| link.edge == edge) else {
                continue;
            };
            total = total + link.weight;
        }
        Ok(Some(total))
    }
}

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

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

    #[test]
    fn test_a_tree_spans_a_connected_graph() {
        let mut graph = Graph::<u32, u32, ()>::new(false);
        let nodes: Vec<_> = (0..4).map(|i| graph.add_node(i)).collect();
        graph.add_edge(nodes[0], nodes[1], 1, ()).unwrap();
        graph.add_edge(nodes[1], nodes[2], 2, ()).unwrap();
        graph.add_edge(nodes[2], nodes[3], 3, ()).unwrap();
        graph.add_edge(nodes[0], nodes[3], 10, ()).unwrap();

        let forest = graph.minimum_spanning_forest().unwrap();
        // A spanning tree of n nodes has n - 1 edges, and the expensive edge is left out.
        assert_eq!(forest.len(), 3);
        assert_eq!(graph.minimum_spanning_weight().unwrap(), Some(6));
    }

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

        assert_eq!(graph.minimum_spanning_forest().unwrap(), vec![cheap]);
    }

    #[test]
    fn test_a_disconnected_graph_yields_a_forest() {
        let mut graph = Graph::<u32, u32, ()>::new(false);
        let nodes: Vec<_> = (0..5).map(|i| graph.add_node(i)).collect();
        graph.add_edge(nodes[0], nodes[1], 1, ()).unwrap();
        graph.add_edge(nodes[2], nodes[3], 1, ()).unwrap();

        // Three components — {0,1}, {2,3}, {4} — so the forest has 5 - 3 edges.
        let components = graph.weakly_connected_components().unwrap().len();
        assert_eq!(components, 3);
        assert_eq!(
            graph.minimum_spanning_forest().unwrap().len(),
            graph.node_count() - components
        );
    }

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

        assert_eq!(graph.minimum_spanning_forest().unwrap(), vec![real]);
    }

    #[test]
    fn test_an_empty_graph_has_no_spanning_weight() {
        let graph = Graph::<u32, u32, ()>::new(false);
        assert!(graph.minimum_spanning_forest().unwrap().is_empty());
        assert_eq!(graph.minimum_spanning_weight().unwrap(), None);
    }

    #[test]
    fn test_float_weights_are_supported() {
        let mut graph = Graph::<f64, u32, ()>::new(false);
        let nodes: Vec<_> = (0..3).map(|i| graph.add_node(i)).collect();
        graph.add_edge(nodes[0], nodes[1], 1.5, ()).unwrap();
        graph.add_edge(nodes[1], nodes[2], 2.5, ()).unwrap();
        graph.add_edge(nodes[0], nodes[2], 9.0, ()).unwrap();

        assert_eq!(graph.minimum_spanning_weight().unwrap(), Some(4.0));
    }

    #[test]
    fn test_disjoint_sets_report_membership() {
        let mut sets = DisjointSets::new();
        let ids: Vec<_> = (0..4).map(NodeId::from_index).collect();
        for &id in &ids {
            sets.insert(id);
        }

        assert!(sets.union(ids[0], ids[1]));
        assert!(sets.union(ids[1], ids[2]));
        // Already joined, so this edge would close a cycle.
        assert!(!sets.union(ids[0], ids[2]));
        assert!(sets.connected(ids[0], ids[2]));
        assert!(!sets.connected(ids[0], ids[3]));
    }
}