xgraph 3.0.0

//! Graph connectivity analysis algorithms
//!
//! This module provides functionality to analyze graph connectivity, including:
//! - Weakly connected components (for undirected graphs or when ignoring direction)
//! - Strongly connected components (for directed graphs using Kosaraju's algorithm)
//! - Overall graph connectivity checks
//!
//! All methods return `Result` types to handle potential errors gracefully instead of panicking.
//! This implementation works with the basic `Graph` type and is independent of specific features.
//!
//! # Features
//! - Weak connectivity analysis via BFS
//! - Strong connectivity analysis via Kosaraju's algorithm
//! - Flexible connectivity checks based on graph directionality
//!
//! # Examples
//!
//! Basic usage with error handling:
//! ```rust
//! use xgraph::graph::graph::Graph;
//! use xgraph::graph::algorithms::connectivity::Connectivity;
//!
//! let mut graph = Graph::<u32, &str, ()>::new(true);
//! let a = graph.add_node("A");
//! let b = graph.add_node("B");
//! graph.add_edge(a, b, 1, ()).unwrap();
//!
//! let scc = graph.find_strongly_connected_components().unwrap();
//! let is_strong = graph.is_strongly_connected().unwrap();
//! ```

use crate::core::algo::traversal::TraversalError;
use crate::core::view::NodeId;
use crate::graph::graph::Graph;
use std::fmt::Debug;
use std::hash::Hash;

/// Error type for connectivity analysis failures.
#[derive(Debug, thiserror::Error)]
pub enum ConnectivityError {
    /// Indicates an invalid node was encountered during computation.
    #[error("Invalid node reference: node ID {0} not found")]
    InvalidNode(NodeId),
    /// Indicates an error during graph transposition.
    #[error("Graph transposition failed: {0}")]
    TransposeError(String),
}

impl From<TraversalError> for ConnectivityError {
    fn from(error: TraversalError) -> Self {
        match error {
            TraversalError::InvalidNode(id) => ConnectivityError::InvalidNode(id),
        }
    }
}

/// Trait for graph connectivity analysis.
///
/// Provides methods to analyze both weak and strong connectivity in directed and undirected graphs
/// with proper error handling.
///
/// # Type Parameters
/// - `W`: The weight type of the graph edges.
/// - `N`: The node data type.
/// - `E`: The edge data type.
///
/// # Examples
///
/// Finding connected components in a social network:
/// ```rust
/// use xgraph::graph::graph::Graph;
/// use xgraph::graph::algorithms::connectivity::Connectivity;
///
/// let mut social_graph = Graph::new(false);
/// let alice = social_graph.add_node("Alice");
/// let bob = social_graph.add_node("Bob");
/// let charlie = social_graph.add_node("Charlie");
///
/// social_graph.add_edge(alice, bob, 1, ()).unwrap();
/// social_graph.add_edge(charlie, bob, 1, ()).unwrap();
///
/// let components = social_graph.find_connected_components().unwrap();
/// assert_eq!(components.len(), 1);
/// ```
#[deprecated(
    since = "3.0.0",
    note = "superseded by `xgraph::core::Connectivity`, which is implemented for every \
            graph view — including filtered ones — and carries no unused type parameters"
)]
pub trait Connectivity<W, N, E> {
    /// Finds weakly connected components using BFS.
    ///
    /// Treats the graph as undirected by considering all edge connections regardless of direction.
    ///
    /// # Returns
    /// - `Ok(Vec<Vec<NodeId>>)`: Vector of vectors containing node IDs for each component.
    /// - `Err(ConnectivityError)`: If computation fails due to invalid nodes.
    fn find_weakly_connected_components(&self) -> Result<Vec<Vec<NodeId>>, ConnectivityError>;

    /// Finds strongly connected components using Kosaraju's algorithm.
    ///
    /// Implements a two-phase algorithm with O(|V| + |E|) complexity:
    /// 1. DFS to determine finish order
    /// 2. DFS on transposed graph in reverse finish order
    ///
    /// # Returns
    /// - `Ok(Vec<Vec<NodeId>>)`: Vector of vectors containing node IDs for each component.
    /// - `Err(ConnectivityError)`: If computation fails due to invalid nodes or transposition errors.
    fn find_strongly_connected_components(&self) -> Result<Vec<Vec<NodeId>>, ConnectivityError>;

    /// Automatically selects appropriate connectivity type based on graph directionality.
    ///
    /// Calls `find_strongly_connected_components` for directed graphs and
    /// `find_weakly_connected_components` for undirected graphs.
    ///
    /// # Returns
    /// - `Ok(Vec<Vec<NodeId>>)`: Vector of vectors containing node IDs for each component.
    /// - `Err(ConnectivityError)`: If computation fails.
    fn find_connected_components(&self) -> Result<Vec<Vec<NodeId>>, ConnectivityError> {
        if self.is_directed().unwrap_or(false) {
            self.find_strongly_connected_components()
        } else {
            self.find_weakly_connected_components()
        }
    }

    /// Checks if the graph is weakly connected using BFS.
    ///
    /// A graph is weakly connected if there’s a path between every pair of nodes when considering
    /// all edges as undirected.
    ///
    /// # Returns
    /// - `Ok(bool)`: True if the graph is weakly connected, false otherwise.
    /// - `Err(ConnectivityError)`: If computation fails.
    fn is_weakly_connected(&self) -> Result<bool, ConnectivityError>;

    /// Checks if the graph is strongly connected using Kosaraju's algorithm.
    ///
    /// A graph is strongly connected if there’s a directed path between every pair of nodes.
    ///
    /// # Returns
    /// - `Ok(bool)`: True if the graph is strongly connected, false otherwise.
    /// - `Err(ConnectivityError)`: If computation fails.
    fn is_strongly_connected(&self) -> Result<bool, ConnectivityError>;

    /// Checks overall connectivity based on graph type.
    ///
    /// Returns strong connectivity for directed graphs and weak connectivity for undirected graphs.
    ///
    /// # Returns
    /// - `Ok(bool)`: True if the graph is connected according to its type, false otherwise.
    /// - `Err(ConnectivityError)`: If computation fails.
    fn is_connected(&self) -> Result<bool, ConnectivityError> {
        if self.is_directed().unwrap_or(false) {
            self.is_strongly_connected()
        } else {
            self.is_weakly_connected()
        }
    }

    /// Determines if the graph is directed.
    ///
    /// # Returns
    /// - `Ok(bool)`: True if the graph is directed, false if undirected.
    /// - `Err(ConnectivityError)`: If the graph state is invalid (currently never returned).
    fn is_directed(&self) -> Result<bool, ConnectivityError>;
}

#[allow(deprecated)]
impl<W, N, E> Connectivity<W, N, E> for Graph<W, N, E>
where
    W: Copy + Default + PartialEq + Debug,
    N: Clone + Eq + Hash + Debug,
    E: Clone + Default + Debug,
{
    fn find_weakly_connected_components(&self) -> Result<Vec<Vec<NodeId>>, ConnectivityError> {
        crate::core::Connectivity::weakly_connected_components(self)
            .map_err(ConnectivityError::from)
    }

    fn find_strongly_connected_components(&self) -> Result<Vec<Vec<NodeId>>, ConnectivityError> {
        crate::core::Connectivity::strongly_connected_components(self)
            .map_err(ConnectivityError::from)
    }

    fn is_weakly_connected(&self) -> Result<bool, ConnectivityError> {
        crate::core::Connectivity::is_weakly_connected(self).map_err(ConnectivityError::from)
    }

    fn is_strongly_connected(&self) -> Result<bool, ConnectivityError> {
        crate::core::Connectivity::is_strongly_connected(self).map_err(ConnectivityError::from)
    }

    fn is_directed(&self) -> Result<bool, ConnectivityError> {
        Ok(crate::core::GraphView::is_directed(self))
    }
}

#[cfg(test)]
#[allow(deprecated)]
mod tests {
    use super::*;

    #[test]
    fn test_strongly_connected() {
        let mut graph = Graph::<u32, (), ()>::new(true);

        let n0 = graph.add_node(());
        let n1 = graph.add_node(());
        let n2 = graph.add_node(());

        graph.add_edge(n0, n1, 1, ()).unwrap();
        graph.add_edge(n1, n2, 1, ()).unwrap();
        graph.add_edge(n2, n0, 1, ()).unwrap();

        assert!(graph.is_strongly_connected().unwrap());
        let scc = graph.find_strongly_connected_components().unwrap();
        assert_eq!(scc.len(), 1);
    }

    #[test]
    fn test_weak_connectivity() {
        let mut graph = Graph::<u32, (), ()>::new(true);

        let n0 = graph.add_node(());
        let n1 = graph.add_node(());
        graph.add_edge(n0, n1, 1, ()).unwrap();

        assert!(!graph.is_strongly_connected().unwrap());
        assert!(graph.is_weakly_connected().unwrap());
    }

    #[test]
    fn test_scc_with_sparse_ids() {
        let mut graph = Graph::<u32, (), ()>::new(true);
        let n0 = graph.add_node(());
        let n1 = graph.add_node(());
        let n2 = graph.add_node(());
        let n3 = graph.add_node(());
        // Remove a node so the surviving IDs are non-contiguous.
        graph.remove_node(n1).unwrap();

        graph.add_edge(n0, n2, 1, ()).unwrap();
        graph.add_edge(n2, n3, 1, ()).unwrap();
        graph.add_edge(n3, n0, 1, ()).unwrap();

        let scc = graph.find_strongly_connected_components().unwrap();
        assert_eq!(scc.len(), 1);
        assert_eq!(scc[0], vec![n0, n2, n3]);
        assert!(graph.is_strongly_connected().unwrap());
    }

    #[test]
    fn test_deep_chain_does_not_overflow_the_stack() {
        let mut graph = Graph::<u32, usize, ()>::new(true);
        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();
        }

        // A directed path has no non-trivial strongly connected component, and Kosaraju
        // walks the whole chain twice to establish that.
        assert_eq!(
            graph.find_strongly_connected_components().unwrap().len(),
            nodes.len()
        );
        assert!(graph.is_weakly_connected().unwrap());
    }
}