xgraph 3.0.0

//! Connectivity analysis, written once against [`GraphView`].
//!
//! Both component algorithms traverse edges backwards at some point. Rather than
//! materialising a transposed graph — which would also have to renumber sparse node IDs —
//! the reverse adjacency is built once as a predecessor map, keeping the work at
//! O(|V| + |E|).

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

/// The reverse adjacency of a graph: for each node, the nodes with an edge into it.
pub type Predecessors = HashMap<NodeId, Vec<NodeId>>;

/// Connectivity algorithms available on every [`GraphView`].
pub trait Connectivity: GraphView {
    /// Builds the reverse adjacency of the graph.
    ///
    /// Every node gets an entry, including isolated ones, so a lookup never has to
    /// distinguish "no predecessors" from "unknown node".
    fn predecessors(&self) -> Predecessors {
        let mut predecessors: Predecessors = HashMap::new();
        for node in self.node_ids() {
            predecessors.entry(node).or_default();
        }
        for node in self.node_ids() {
            for link in self.links(node) {
                predecessors.entry(link.target).or_default().push(node);
            }
        }
        predecessors
    }

    /// Finds the weakly connected components: those of the graph with direction ignored.
    ///
    /// Each component is sorted by node ID, and the components themselves come in ascending
    /// order of their smallest member, so the result is reproducible run to run.
    fn weakly_connected_components(&self) -> Result<Vec<Vec<NodeId>>, TraversalError> {
        // Undirected views already report both endpoints from either side, so the reverse
        // adjacency is only worth building for directed ones.
        let predecessors = if self.is_directed() {
            self.predecessors()
        } else {
            Predecessors::new()
        };

        let mut visited = HashSet::new();
        let mut components = Vec::new();

        for root in self.node_ids() {
            if !visited.insert(root) {
                continue;
            }

            let mut component = vec![root];
            let mut stack = vec![root];
            while let Some(node) = stack.pop() {
                for link in self.links(node) {
                    if visited.insert(link.target) {
                        component.push(link.target);
                        stack.push(link.target);
                    }
                }
                if let Some(preds) = predecessors.get(&node) {
                    for &predecessor in preds {
                        if visited.insert(predecessor) {
                            component.push(predecessor);
                            stack.push(predecessor);
                        }
                    }
                }
            }

            component.sort_unstable();
            components.push(component);
        }
        Ok(components)
    }

    /// Finds the strongly connected components using Kosaraju's algorithm.
    ///
    /// Two nodes share a component when each is reachable from the other along edge
    /// directions. On an undirected graph this coincides with the weakly connected
    /// components.
    fn strongly_connected_components(&self) -> Result<Vec<Vec<NodeId>>, TraversalError> {
        // Phase one: the order in which a depth-first sweep finishes with each node.
        let mut visited = HashSet::new();
        let mut finish_order = Vec::with_capacity(self.node_count());
        for root in self.node_ids() {
            self.dfs_postorder_into(root, &mut visited, &mut finish_order)?;
        }

        // Phase two: the same sweep over reversed edges, in reverse finish order.
        let predecessors = self.predecessors();
        let mut visited = HashSet::new();
        let mut components = Vec::new();

        for &root in finish_order.iter().rev() {
            if !visited.insert(root) {
                continue;
            }

            let mut component = vec![root];
            let mut stack = vec![root];
            while let Some(node) = stack.pop() {
                for &predecessor in predecessors.get(&node).into_iter().flatten() {
                    if visited.insert(predecessor) {
                        component.push(predecessor);
                        stack.push(predecessor);
                    }
                }
            }

            component.sort_unstable();
            components.push(component);
        }
        Ok(components)
    }

    /// Finds the components appropriate to the graph's directionality.
    ///
    /// Strongly connected components for a directed graph, weakly connected ones otherwise.
    fn connected_components(&self) -> Result<Vec<Vec<NodeId>>, TraversalError> {
        if self.is_directed() {
            self.strongly_connected_components()
        } else {
            self.weakly_connected_components()
        }
    }

    /// Whether the graph is in one piece once direction is ignored.
    ///
    /// An empty graph counts as connected.
    fn is_weakly_connected(&self) -> Result<bool, TraversalError> {
        Ok(self.weakly_connected_components()?.len() <= 1)
    }

    /// Whether every node can reach every other node along edge directions.
    ///
    /// An empty graph counts as connected. Rather than enumerating the components, this
    /// checks that one arbitrary node reaches everything and is reached by everything —
    /// two traversals instead of a full Kosaraju sweep.
    fn is_strongly_connected(&self) -> Result<bool, TraversalError> {
        let Some(start) = self.node_ids().next() else {
            return Ok(true);
        };
        let total = self.node_count();

        if self.reachable_from(start)?.len() != total {
            return Ok(false);
        }

        let predecessors = self.predecessors();
        let mut visited = HashSet::new();
        visited.insert(start);
        let mut stack = vec![start];
        while let Some(node) = stack.pop() {
            for &predecessor in predecessors.get(&node).into_iter().flatten() {
                if visited.insert(predecessor) {
                    stack.push(predecessor);
                }
            }
        }
        Ok(visited.len() == total)
    }

    /// Whether the graph is connected in the sense appropriate to its directionality.
    fn is_connected(&self) -> Result<bool, TraversalError> {
        if self.is_directed() {
            self.is_strongly_connected()
        } else {
            self.is_weakly_connected()
        }
    }
}

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

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

    #[test]
    fn test_cycle_is_one_strong_component() {
        let mut graph = Graph::<u32, u32, ()>::new(true);
        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_eq!(graph.strongly_connected_components().unwrap().len(), 1);
        assert!(graph.is_strongly_connected().unwrap());
        assert!(graph.is_connected().unwrap());
    }

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

        assert!(graph.is_weakly_connected().unwrap());
        assert!(!graph.is_strongly_connected().unwrap());
        assert_eq!(graph.strongly_connected_components().unwrap().len(), 2);
    }

    #[test]
    fn test_components_survive_sparse_ids() {
        let mut graph = Graph::<u32, u32, ()>::new(true);
        let a = graph.add_node(0);
        let gap = graph.add_node(1);
        let b = graph.add_node(2);
        let c = graph.add_node(3);
        graph.remove_node(gap).unwrap();

        graph.add_edge(a, b, 1, ()).unwrap();
        graph.add_edge(b, c, 1, ()).unwrap();
        graph.add_edge(c, a, 1, ()).unwrap();

        let scc = graph.strongly_connected_components().unwrap();
        assert_eq!(scc, vec![vec![a, b, c]]);
    }

    #[test]
    fn test_empty_graph_is_connected() {
        let graph = Graph::<u32, u32, ()>::new(true);
        assert!(graph.is_connected().unwrap());
        assert!(graph.connected_components().unwrap().is_empty());
    }

    #[test]
    fn test_connectivity_over_a_filtered_view() {
        let mut graph = Graph::<u32, u32, &str>::new(false);
        let a = graph.add_node(0);
        let b = graph.add_node(1);
        let c = graph.add_node(2);
        let rail = graph.add_edge(a, b, 1, "rail").unwrap();
        graph.add_edge(b, c, 1, "road").unwrap();

        assert!(graph.is_connected().unwrap());
        // Dropping the road splits the graph into {a, b} and {c}.
        let rail_only = EdgeFiltered::new(&graph, |edge| edge == rail);
        assert_eq!(
            rail_only.weakly_connected_components().unwrap(),
            vec![vec![a, b], vec![c]]
        );
        assert!(!rail_only.is_connected().unwrap());
    }
}