xgraph 3.0.0

//! Bridge detection algorithms for graphs.
//!
//! This module provides functionality to identify bridge edges in a graph using Tarjan's algorithm.
//! A bridge is an edge whose removal increases the number of connected components in the graph.
//! This implementation is independent of the `hgraph` feature and works with the basic `Graph` type.
//!
//! For heterogeneous multigraph support, enable the `hgraph` feature in your `Cargo.toml`:
//! ```toml
//! [dependencies.xgraph]
//! version = "x.y.z"
//! features = ["hgraph"]
//! ```
//! Then use `hgraph::h_bridges::HeteroBridges` instead.
//!
//! # Examples
//!
//! Finding bridges in a simple graph:
//! ```rust
//! use xgraph::graph::graph::Graph;
//! use xgraph::graph::algorithms::bridges::Bridges;
//!
//! let mut graph = Graph::<f64, String, String>::new(false);
//! let n0 = graph.add_node("A".to_string());
//! let n1 = graph.add_node("B".to_string());
//! let n2 = graph.add_node("C".to_string());
//!
//! graph.add_edge(n0, n1, 1.0, "road".to_string()).unwrap();
//! graph.add_edge(n1, n2, 2.0, "bridge".to_string()).unwrap();
//!
//! let bridges = graph.find_bridges().unwrap();
//! assert_eq!(bridges, vec![(n0, n1), (n1, n2)]);
//! ```
//!
//! No bridges in a cycle:
//! ```rust
//! use xgraph::graph::graph::Graph;
//! use xgraph::graph::algorithms::bridges::Bridges;
//!
//! let mut graph = Graph::<f64, String, String>::new(false);
//! let n0 = graph.add_node("A".to_string());
//! let n1 = graph.add_node("B".to_string());
//! let n2 = graph.add_node("C".to_string());
//!
//! graph.add_edge(n0, n1, 1.0, "road".to_string()).unwrap();
//! graph.add_edge(n1, n2, 2.0, "bridge".to_string()).unwrap();
//! graph.add_edge(n2, n0, 3.0, "path".to_string()).unwrap();
//!
//! let bridges = graph.find_bridges().unwrap();
//! assert!(bridges.is_empty());
//! ```

use crate::core::algo::traversal::TraversalError;
use crate::core::view::NodeId;
use crate::graph::graph::Graph;
use std::collections::{HashMap, HashSet};
use std::fmt::Debug;
use std::hash::Hash;

/// Error type for bridge detection failures.
#[derive(Debug, thiserror::Error)]
pub enum BridgeError {
    /// Indicates an invalid node was encountered during bridge detection.
    #[error("Invalid node reference: node ID {0} not found")]
    InvalidNode(NodeId),
}

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

/// Context for Tarjan's bridge-finding algorithm.
///
/// This structure maintains the state during the depth-first search (DFS) process
/// used to identify bridges in a graph.
///
/// # Fields
/// - `visited`: Set of nodes that have been visited during DFS
/// - `disc`: Discovery times for each node
/// - `low`: Lowest reachable vertex times
/// - `parent`: Parent nodes in the DFS tree
/// - `bridges`: Collection of identified bridge edges
/// - `time`: Current time step in the DFS process
#[derive(Debug)]
pub struct BridgeContext {
    visited: HashSet<NodeId>,
    disc: HashMap<NodeId, u32>,
    low: HashMap<NodeId, u32>,
    #[allow(dead_code)]
    parent: HashMap<NodeId, NodeId>,
    bridges: Vec<(NodeId, NodeId)>,
    time: u32,
}

impl BridgeContext {
    /// Creates a new empty context for bridge detection.
    ///
    /// # Returns
    /// A new `BridgeContext` instance with all fields initialized to their default empty states.
    pub fn new() -> Self {
        Self {
            visited: HashSet::new(),
            disc: HashMap::new(),
            low: HashMap::new(),
            parent: HashMap::new(),
            bridges: Vec::new(),
            time: 0,
        }
    }
}

impl Default for BridgeContext {
    fn default() -> Self {
        Self::new()
    }
}

/// Trait defining bridge detection functionality for graphs.
///
/// This trait provides methods to identify bridge edges in undirected graphs
/// using Tarjan's algorithm with O(V + E) time complexity.
///
/// # Requirements
/// Implementing types must support graph operations and maintain node/edge relationships.
#[deprecated(
    since = "3.0.0",
    note = "superseded by `xgraph::core::Bridges`, which is implemented for every graph \
            view and can also report bridges by edge ID via `bridge_edges`"
)]
pub trait Bridges {
    /// Finds all bridge edges in the graph.
    ///
    /// # Returns
    /// A `Result` containing either:
    /// - `Ok(Vec<(NodeId, NodeId)>)`: A sorted vector of tuples representing bridge edges
    /// - `Err(BridgeError)`: An error if the computation fails
    fn find_bridges(&self) -> Result<Vec<(NodeId, NodeId)>, BridgeError>;

    /// Sorts bridge edges for consistent output.
    ///
    /// Normalizes node order (smaller ID first) and sorts lexicographically.
    ///
    /// # Arguments
    /// - `bridges`: Mutable reference to the vector of bridge edges to be sorted
    fn sort_bridges(bridges: &mut Vec<(NodeId, NodeId)>);

    /// Performs depth-first search to detect bridges.
    ///
    /// # Arguments
    /// - `node`: The current node being processed
    /// - `context`: Mutable reference to the bridge detection context
    ///
    /// # Returns
    /// A `Result` indicating success or failure of the DFS operation
    fn bridge_dfs(&self, node: NodeId, context: &mut BridgeContext) -> Result<(), BridgeError>;
}

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

    fn sort_bridges(bridges: &mut Vec<(NodeId, NodeId)>) {
        bridges.iter_mut().for_each(|(u, v)| {
            if u > v {
                std::mem::swap(u, v);
            }
        });
        bridges.sort_unstable();
    }

    fn bridge_dfs(&self, node: NodeId, context: &mut BridgeContext) -> Result<(), BridgeError> {
        let mut state = crate::core::TarjanState::default();
        crate::core::Bridges::tarjan_from(self, node, &mut state).map_err(BridgeError::from)?;

        context.visited.extend(state.discovery.keys().copied());
        // `BridgeContext` counts in `u32`; the shared state counts in `NodeId`.
        context
            .disc
            .extend(state.discovery.iter().map(|(&k, &v)| (k, v as u32)));
        context
            .low
            .extend(state.low.iter().map(|(&k, &v)| (k, v as u32)));
        context.time = state.time as u32;
        for edge in state.bridges {
            if let Some(pair) = crate::core::GraphView::edge_endpoints(self, edge) {
                context.bridges.push(pair);
            }
        }
        Ok(())
    }
}

#[cfg(test)]
#[allow(deprecated)]
mod tests {
    use super::*;
    use crate::core::view::NodeId;
    use crate::graph::graph::Graph;

    #[test]
    fn test_find_bridges_simple() {
        let mut graph = Graph::<f64, String, String>::new(false);
        let n0 = graph.add_node("A".to_string());
        let n1 = graph.add_node("B".to_string());
        let n2 = graph.add_node("C".to_string());

        graph.add_edge(n0, n1, 1.0, "road".to_string()).unwrap();
        graph.add_edge(n1, n2, 2.0, "bridge".to_string()).unwrap();

        let bridges = graph.find_bridges().unwrap();
        assert_eq!(bridges, vec![(n0, n1), (n1, n2)]);
    }

    #[test]
    fn test_find_bridges_cycle() {
        let mut graph = Graph::<f64, String, String>::new(false);
        let n0 = graph.add_node("A".to_string());
        let n1 = graph.add_node("B".to_string());
        let n2 = graph.add_node("C".to_string());

        graph.add_edge(n0, n1, 1.0, "road".to_string()).unwrap();
        graph.add_edge(n1, n2, 2.0, "bridge".to_string()).unwrap();
        graph.add_edge(n2, n0, 3.0, "path".to_string()).unwrap();

        let bridges = graph.find_bridges().unwrap();
        assert!(bridges.is_empty());
    }

    #[test]
    fn test_find_bridges_complex() {
        let matrix = vec![
            vec![0, 1, 1, 0, 0, 0, 0, 0, 0, 0],
            vec![1, 0, 1, 0, 0, 0, 0, 0, 0, 0],
            vec![1, 1, 0, 1, 0, 0, 0, 0, 0, 0],
            vec![0, 0, 1, 0, 1, 1, 0, 0, 0, 0],
            vec![0, 0, 0, 1, 0, 1, 0, 0, 0, 0],
            vec![0, 0, 0, 1, 1, 0, 0, 0, 0, 0],
            vec![0, 0, 0, 0, 0, 0, 0, 1, 1, 0],
            vec![0, 0, 0, 0, 0, 0, 1, 0, 1, 0],
            vec![0, 0, 0, 0, 0, 0, 1, 1, 0, 1],
            vec![0, 0, 0, 0, 0, 0, 0, 0, 1, 0],
        ];

        let graph =
            Graph::from_adjacency_matrix(&matrix, false, "node".to_string(), "edge".to_string())
                .unwrap();
        let bridges = graph.find_bridges().unwrap();
        assert_eq!(
            bridges,
            vec![
                (NodeId::from_index(2), NodeId::from_index(3)),
                (NodeId::from_index(8), NodeId::from_index(9))
            ]
        );
    }

    #[test]
    fn test_find_bridges_empty() {
        let graph = Graph::<f64, String, String>::new(false);
        let bridges = graph.find_bridges().unwrap();
        assert!(bridges.is_empty());
    }

    #[test]
    fn test_find_bridges_single_node() {
        let mut graph = Graph::<f64, String, String>::new(false);
        graph.add_node("A".to_string());
        let bridges = graph.find_bridges().unwrap();
        assert!(bridges.is_empty());
    }

    #[test]
    fn test_find_bridges_with_sparse_ids() {
        // Build five nodes, then remove the first three so the only remaining component
        // lives entirely at IDs that exceed the node count.
        let mut graph = Graph::<f64, (), ()>::new(false);
        let ids: Vec<_> = (0..5).map(|_| graph.add_node(())).collect();
        graph.add_edge(ids[3], ids[4], 1.0, ()).unwrap();
        graph.remove_node(ids[0]).unwrap();
        graph.remove_node(ids[1]).unwrap();
        graph.remove_node(ids[2]).unwrap();

        let bridges = graph.find_bridges().unwrap();
        assert_eq!(bridges, vec![(ids[3], ids[4])]);
    }

    #[test]
    fn test_parallel_edges_are_not_bridges() {
        // Two parallel edges between the same pair form a cycle: removing either one leaves
        // the graph connected, so neither is a bridge.
        let mut graph = Graph::<f64, String, String>::new(false);
        let a = graph.add_node("A".to_string());
        let b = graph.add_node("B".to_string());
        let c = graph.add_node("C".to_string());

        graph.add_edge(a, b, 1.0, "rail".to_string()).unwrap();
        graph.add_edge(a, b, 2.0, "road".to_string()).unwrap();
        graph.add_edge(b, c, 3.0, "ferry".to_string()).unwrap();

        // Only the single edge b-c is a bridge.
        assert_eq!(graph.find_bridges().unwrap(), vec![(b, c)]);
    }

    #[test]
    fn test_deep_chain_does_not_overflow_the_stack() {
        // A recursive traversal blows the thread stack well before this depth.
        let mut graph = Graph::<f64, usize, String>::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.0, String::new())
                .unwrap();
        }

        // Every edge of a path graph is a bridge.
        assert_eq!(graph.find_bridges().unwrap().len(), nodes.len() - 1);
    }
}