xgraph 3.0.0

//! Bridge detection, written once against [`GraphView`].
//!
//! A bridge is an edge whose removal raises the number of connected components. Tarjan's
//! algorithm finds them all in O(|V| + |E|).
//!
//! Two details decide whether the answer is right on a multigraph, and the previous
//! per-graph implementations got them wrong in opposite ways. The search must exclude the
//! specific edge it arrived on rather than every edge back to the parent node — otherwise
//! each of a pair of parallel edges is reported as a bridge, when in truth removing either
//! leaves the two nodes joined by the other. And the result is naturally keyed by edge, not
//! by node pair.

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

/// Bridge and articulation-point detection, available on every [`GraphView`].
pub trait Bridges: GraphView {
    /// Finds every articulation point: a node whose removal splits a component.
    ///
    /// The dual notion to a bridge, and found by the same sweep. A network's articulation
    /// points are its single points of failure, so a library that reports critical edges
    /// and not critical nodes is telling only half the story.
    ///
    /// Results come in ascending node order.
    fn articulation_points(&self) -> Result<Vec<NodeId>, TraversalError> {
        let mut found = HashSet::new();
        let mut state = TarjanState::default();

        for root in self.node_ids() {
            if state.discovery.contains_key(&root) {
                continue;
            }
            let before = state.discovery.len();
            self.tarjan_from(root, &mut state)?;

            // The root of a search tree is an articulation point exactly when it has more
            // than one child in that tree — the general rule below never applies to it,
            // because it has no parent whose subtree could reach past it.
            let children = state
                .parent_edge
                .iter()
                .filter(|(node, _)| state.tree_parent.get(node) == Some(&root) && **node != root)
                .count();
            if children > 1 {
                found.insert(root);
            }
            debug_assert!(state.discovery.len() >= before);
        }

        found.extend(state.articulation_points.iter().copied());
        let mut points: Vec<NodeId> = found.into_iter().collect();
        points.sort_unstable();
        Ok(points)
    }

    /// Finds every bridge, identified by edge.
    ///
    /// Results come in ascending edge-ID order.
    fn bridge_edges(&self) -> Result<Vec<EdgeId>, TraversalError> {
        let mut state = TarjanState::default();

        for root in self.node_ids() {
            if state.discovery.contains_key(&root) {
                continue;
            }
            self.tarjan_from(root, &mut state)?;
        }

        state.bridges.sort_unstable();
        Ok(state.bridges)
    }

    /// Finds every bridge, identified by its endpoints.
    ///
    /// Each pair is normalized so the smaller node ID comes first, and the pairs are
    /// sorted, so the output is reproducible run to run.
    fn bridges(&self) -> Result<Vec<(NodeId, NodeId)>, TraversalError> {
        let mut pairs: Vec<(NodeId, NodeId)> = self
            .bridge_edges()?
            .into_iter()
            .filter_map(|edge| self.edge_endpoints(edge))
            .map(|(from, to)| if from <= to { (from, to) } else { (to, from) })
            .collect();
        pairs.sort_unstable();
        Ok(pairs)
    }

    /// Runs Tarjan's depth-first sweep over the component containing `root`.
    fn tarjan_from(&self, root: NodeId, state: &mut TarjanState) -> Result<(), TraversalError> {
        if !self.contains_node(root) {
            return Err(TraversalError::InvalidNode(root));
        }
        if state.discovery.contains_key(&root) {
            return Ok(());
        }

        state.time += 1;
        state.discovery.insert(root, state.time);
        state.low.insert(root, state.time);

        // Frames hold the node, its live link iterator, and the edge the search arrived on.
        let mut stack: Vec<(NodeId, Self::Links<'_>, Option<EdgeId>)> =
            vec![(root, self.links(root), None)];

        while let Some(frame) = stack.last_mut() {
            let node = frame.0;
            let arrival_edge = frame.2;
            let next = frame.1.next();

            match next {
                Some(link) => {
                    // Exclude only the edge traversed to get here. Excluding the parent
                    // node instead would hide the second of a pair of parallel edges.
                    if Some(link.edge) == arrival_edge {
                        continue;
                    }
                    if !self.contains_node(link.target) {
                        return Err(TraversalError::InvalidNode(link.target));
                    }

                    match state.discovery.get(&link.target) {
                        Some(&target_discovery) => {
                            // A link to an already-discovered node bounds how far back this
                            // subtree can reach without using the tree edge above it.
                            let low = state
                                .low
                                .get_mut(&node)
                                .expect("low is recorded when a node is discovered");
                            *low = (*low).min(target_discovery);
                        }
                        None => {
                            state.time += 1;
                            state.discovery.insert(link.target, state.time);
                            state.low.insert(link.target, state.time);
                            state.parent_edge.insert(link.target, link.edge);
                            state.tree_parent.insert(link.target, node);
                            stack.push((link.target, self.links(link.target), Some(link.edge)));
                        }
                    }
                }
                None => {
                    stack.pop();
                    if let Some(&(parent, _, _)) = stack.last() {
                        let node_low = state.low[&node];
                        let parent_discovery = state.discovery[&parent];
                        let low = state
                            .low
                            .get_mut(&parent)
                            .expect("low is recorded when a node is discovered");
                        *low = (*low).min(node_low);

                        // Nothing in this subtree reaches past its own entry point, so the
                        // edge above it is the component's only link to it.
                        if node_low > parent_discovery {
                            if let Some(&edge) = state.parent_edge.get(&node) {
                                state.bridges.push(edge);
                            }
                        }
                        // A weaker condition makes the parent an articulation point: the
                        // subtree cannot reach *above* the parent, so removing the parent
                        // strands it. Whether the root itself qualifies is decided
                        // separately, since it has no parent to be cut off from.
                        if node_low >= parent_discovery && stack.len() > 1 {
                            state.articulation_points.insert(parent);
                        }
                    }
                }
            }
        }
        Ok(())
    }
}

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

/// Bookkeeping for Tarjan's bridge-finding sweep.
///
/// Exposed so that a caller can drive the sweep component by component through
/// [`Bridges::tarjan_from`] and inspect the discovery and low-link numbers.
#[derive(Debug, Default)]
pub struct TarjanState {
    /// The order in which each node was first reached.
    pub discovery: HashMap<NodeId, usize>,
    /// The earliest discovery number reachable from each node's subtree.
    pub low: HashMap<NodeId, usize>,
    /// The tree edge each node was reached through.
    pub parent_edge: HashMap<NodeId, EdgeId>,
    /// The node each node was reached from.
    pub tree_parent: HashMap<NodeId, NodeId>,
    /// The articulation points found so far, excluding search-tree roots.
    pub articulation_points: HashSet<NodeId>,
    /// The bridges found so far.
    pub bridges: Vec<EdgeId>,
    /// The discovery counter.
    pub time: usize,
}

impl TarjanState {
    /// The nodes reached so far.
    pub fn visited(&self) -> HashSet<NodeId> {
        self.discovery.keys().copied().collect()
    }
}

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

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

        assert_eq!(
            graph.bridges().unwrap(),
            vec![
                (nodes[0], nodes[1]),
                (nodes[1], nodes[2]),
                (nodes[2], nodes[3])
            ]
        );
    }

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

        assert!(graph.bridges().unwrap().is_empty());
    }

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

        // Either of the parallel edges can go without disconnecting anything.
        assert_eq!(graph.bridge_edges().unwrap(), vec![single]);
        assert_eq!(graph.bridges().unwrap(), vec![(b, c)]);
    }

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

        assert_eq!(graph.bridges().unwrap(), vec![(a, b), (c, d)]);
    }

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

        assert_eq!(graph.bridge_edges().unwrap().len(), nodes.len() - 1);
    }

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

        assert_eq!(graph.articulation_points().unwrap(), vec![nodes[1]]);
    }

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

        assert!(graph.articulation_points().unwrap().is_empty());
    }

    /// The hub of a star is the one node every path between spokes must pass through.
    #[test]
    fn test_the_hub_of_a_star_is_an_articulation_point() {
        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();
        }

        assert_eq!(graph.articulation_points().unwrap(), vec![hub]);
    }

    /// Checked against the definition: a node is an articulation point exactly when taking
    /// it out leaves more components behind.
    #[test]
    fn test_articulation_points_match_the_definition() {
        use crate::core::{Connectivity, NodeFiltered};

        let mut graph = Graph::<u32, u32, ()>::new(false);
        let nodes: Vec<_> = (0..7).map(|i| graph.add_node(i)).collect();
        for &(a, b) in &[
            (0, 1),
            (1, 2),
            (2, 0),
            (2, 3),
            (3, 4),
            (4, 5),
            (5, 3),
            (3, 6),
        ] {
            graph.add_edge(nodes[a], nodes[b], 1, ()).unwrap();
        }

        let reported: HashSet<NodeId> = graph.articulation_points().unwrap().into_iter().collect();
        let before = graph.weakly_connected_components().unwrap().len();

        for node in graph.node_ids() {
            let without = NodeFiltered::new(&graph, move |other| other != node);
            let after = without.weakly_connected_components().unwrap().len();
            // Removing a node always removes it from its own component, so the comparison
            // accounts for the node itself disappearing.
            let splits = after > before;
            assert_eq!(
                reported.contains(&node),
                splits,
                "node {:?}: reported {}, components {} -> {}",
                node,
                reported.contains(&node),
                before,
                after
            );
        }
    }

    #[test]
    fn test_two_parallel_edges_leave_no_articulation_point() {
        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, 1, ()).unwrap();
        graph.add_edge(a, b, 2, ()).unwrap();

        // Neither endpoint can be an articulation point: removing one leaves a single node.
        assert!(graph.articulation_points().unwrap().is_empty());
    }
}