xgraph 3.0.0

//! Connectivity analysis algorithms for heterogeneous multigraphs.
//!
//! This module provides implementations of connectivity-related algorithms tailored for heterogeneous
//! multigraphs, where nodes and edges can have distinct types. It includes methods to identify weakly
//! and strongly connected components, check overall connectivity, and perform these analyses either
//! across all edges or filtered by specific edge types.

#[cfg(feature = "hgraph")]
use crate::core::view::NodeId;
#[cfg(feature = "hgraph")]
use crate::hgraph::h_graph::HeterogeneousGraph;
#[cfg(feature = "hgraph")]
use std::fmt::Debug;
#[cfg(feature = "hgraph")]
use std::hash::Hash;

// Error handling additions

/// Error type for connectivity computation failures.
///
/// Represents errors that may occur during connectivity analysis, such as referencing non-existent nodes.
#[derive(Debug, thiserror::Error)]
pub enum ConnectivityError {
    /// Indicates a node referenced in the graph does not exist.
    #[error("Invalid node reference: node ID {0} not found")]
    InvalidNodeReference(NodeId),
}

#[cfg(feature = "hgraph")]
impl From<crate::core::TraversalError> for ConnectivityError {
    fn from(error: crate::core::TraversalError) -> Self {
        match error {
            crate::core::TraversalError::InvalidNode(id) => {
                ConnectivityError::InvalidNodeReference(id)
            }
        }
    }
}

/// Result type alias for connectivity computations.
///
/// Wraps the result of connectivity calculations, allowing for error handling.
pub type Result<T> = std::result::Result<T, ConnectivityError>;

// Enhanced trait with documentation and error handling

/// Trait defining connectivity measures for heterogeneous graphs.
///
/// Provides methods to analyze connectivity in a `HeterogeneousGraph`, including finding connected
/// components and checking connectivity properties. Each method is available in two variants: one
/// considering all edges and another filtered by edge types. All methods return a `Result` to handle
/// potential errors gracefully instead of panicking.
#[cfg(feature = "hgraph")]
#[deprecated(
    since = "3.0.0",
    note = "superseded by `xgraph::core::Connectivity`; the `*_by_types` variants become \
            `graph.of_edge_data(&[..])` followed by the ordinary method"
)]
pub trait HeteroConnectivity<W, N, E> {
    /// Finds weakly connected components in the graph.
    ///
    /// Weakly connected components are sets of nodes where there is an undirected path between every
    /// pair of nodes, ignoring edge direction in directed graphs.
    ///
    /// # Returns
    /// A `Result` containing a vector of vectors, where each inner vector represents a weakly connected component.
    fn find_weakly_connected_components(&self) -> Result<Vec<Vec<NodeId>>>;

    /// Finds strongly connected components in the graph.
    ///
    /// Strongly connected components are sets of nodes where there is a directed path from every node
    /// to every other node, applicable only in directed graphs.
    ///
    /// # Returns
    /// A `Result` containing a vector of vectors, where each inner vector represents a strongly connected component.
    fn find_strongly_connected_components(&self) -> Result<Vec<Vec<NodeId>>>;

    /// Finds connected components based on graph directionality.
    ///
    /// For undirected graphs, this returns weakly connected components. For directed graphs, it returns
    /// strongly connected components.
    ///
    /// # Returns
    /// A `Result` containing a vector of vectors, where each inner vector represents a connected component.
    fn find_connected_components(&self) -> Result<Vec<Vec<NodeId>>> {
        if self.is_directed() {
            self.find_strongly_connected_components()
        } else {
            self.find_weakly_connected_components()
        }
    }

    /// Checks if the graph is weakly connected.
    ///
    /// A graph is weakly connected if there is an undirected path between every pair of nodes,
    /// ignoring edge direction in directed graphs.
    ///
    /// # Returns
    /// A `Result` containing `true` if the graph is weakly connected, `false` otherwise.
    fn is_weakly_connected(&self) -> Result<bool>;

    /// Checks if the graph is strongly connected.
    ///
    /// A graph is strongly connected if there is a directed path from every node to every other node,
    /// applicable only in directed graphs.
    ///
    /// # Returns
    /// A `Result` containing `true` if the graph is strongly connected, `false` otherwise.
    fn is_strongly_connected(&self) -> Result<bool>;

    /// Checks if the graph is connected based on its directionality.
    ///
    /// For undirected graphs, this checks weak connectivity. For directed graphs, it checks strong connectivity.
    ///
    /// # Returns
    /// A `Result` containing `true` if the graph is connected, `false` otherwise.
    fn is_connected(&self) -> Result<bool> {
        if self.is_directed() {
            self.is_strongly_connected()
        } else {
            self.is_weakly_connected()
        }
    }

    /// Finds weakly connected components considering only specified edge types.
    ///
    /// # Arguments
    /// * `allowed_edge_types` - A slice of edge types to filter edges by. If empty, all edges are considered.
    ///
    /// # Returns
    /// A `Result` containing a vector of vectors, where each inner vector represents a weakly connected component.
    fn find_weakly_connected_components_by_types(
        &self,
        allowed_edge_types: &[E],
    ) -> Result<Vec<Vec<NodeId>>>;

    /// Finds strongly connected components considering only specified edge types.
    ///
    /// # Arguments
    /// * `allowed_edge_types` - A slice of edge types to filter edges by. If empty, all edges are considered.
    ///
    /// # Returns
    /// A `Result` containing a vector of vectors, where each inner vector represents a strongly connected component.
    fn find_strongly_connected_components_by_types(
        &self,
        allowed_edge_types: &[E],
    ) -> Result<Vec<Vec<NodeId>>>;

    /// Finds connected components based on graph directionality, considering only specified edge types.
    ///
    /// For undirected graphs, this returns weakly connected components. For directed graphs, it returns
    /// strongly connected components.
    ///
    /// # Arguments
    /// * `allowed_edge_types` - A slice of edge types to filter edges by. If empty, all edges are considered.
    ///
    /// # Returns
    /// A `Result` containing a vector of vectors, where each inner vector represents a connected component.
    fn find_connected_components_by_types(
        &self,
        allowed_edge_types: &[E],
    ) -> Result<Vec<Vec<NodeId>>> {
        if self.is_directed() {
            self.find_strongly_connected_components_by_types(allowed_edge_types)
        } else {
            self.find_weakly_connected_components_by_types(allowed_edge_types)
        }
    }

    /// Checks if the graph is weakly connected considering only specified edge types.
    ///
    /// # Arguments
    /// * `allowed_edge_types` - A slice of edge types to filter edges by. If empty, all edges are considered.
    ///
    /// # Returns
    /// A `Result` containing `true` if the graph is weakly connected, `false` otherwise.
    fn is_weakly_connected_by_types(&self, allowed_edge_types: &[E]) -> Result<bool>;

    /// Checks if the graph is strongly connected considering only specified edge types.
    ///
    /// # Arguments
    /// * `allowed_edge_types` - A slice of edge types to filter edges by. If empty, all edges are considered.
    ///
    /// # Returns
    /// A `Result` containing `true` if the graph is strongly connected, `false` otherwise.
    fn is_strongly_connected_by_types(&self, allowed_edge_types: &[E]) -> Result<bool>;

    /// Checks if the graph is connected based on its directionality, considering only specified edge types.
    ///
    /// For undirected graphs, this checks weak connectivity. For directed graphs, it checks strong connectivity.
    ///
    /// # Arguments
    /// * `allowed_edge_types` - A slice of edge types to filter edges by. If empty, all edges are considered.
    ///
    /// # Returns
    /// A `Result` containing `true` if the graph is connected, `false` otherwise.
    fn is_connected_by_types(&self, allowed_edge_types: &[E]) -> Result<bool> {
        if self.is_directed() {
            self.is_strongly_connected_by_types(allowed_edge_types)
        } else {
            self.is_weakly_connected_by_types(allowed_edge_types)
        }
    }

    /// Determines if the graph is directed.
    ///
    /// # Returns
    /// `true` if the graph is directed, `false` if undirected.
    fn is_directed(&self) -> bool;
}

#[cfg(feature = "hgraph")]
#[cfg(feature = "hgraph")]
#[allow(deprecated)]
impl<W, N, E> HeteroConnectivity<W, N, E> for HeterogeneousGraph<W, N, E>
where
    W: Copy + Default + PartialEq + Debug,
    N: Clone + Eq + Hash + Debug + crate::hgraph::h_node::NodeType,
    E: Clone + Default + Debug + PartialEq + crate::hgraph::h_edge::EdgeType,
{
    fn find_weakly_connected_components(&self) -> Result<Vec<Vec<NodeId>>> {
        crate::core::Connectivity::weakly_connected_components(self)
            .map_err(ConnectivityError::from)
    }

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

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

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

    fn find_weakly_connected_components_by_types(
        &self,
        allowed_edge_types: &[E],
    ) -> Result<Vec<Vec<NodeId>>> {
        crate::core::Connectivity::weakly_connected_components(
            &self.of_edge_data(allowed_edge_types),
        )
        .map_err(ConnectivityError::from)
    }

    fn find_strongly_connected_components_by_types(
        &self,
        allowed_edge_types: &[E],
    ) -> Result<Vec<Vec<NodeId>>> {
        crate::core::Connectivity::strongly_connected_components(
            &self.of_edge_data(allowed_edge_types),
        )
        .map_err(ConnectivityError::from)
    }

    fn is_weakly_connected_by_types(&self, allowed_edge_types: &[E]) -> Result<bool> {
        crate::core::Connectivity::is_weakly_connected(&self.of_edge_data(allowed_edge_types))
            .map_err(ConnectivityError::from)
    }

    fn is_strongly_connected_by_types(&self, allowed_edge_types: &[E]) -> Result<bool> {
        crate::core::Connectivity::is_strongly_connected(&self.of_edge_data(allowed_edge_types))
            .map_err(ConnectivityError::from)
    }

    fn is_directed(&self) -> bool {
        crate::core::GraphView::is_directed(self)
    }
}

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

    use crate::hgraph::h_edge::EdgeType;
    use crate::hgraph::h_node::NodeType;

    #[derive(Clone, Eq, PartialEq, Hash, Debug)]
    struct TestNode(String);
    impl NodeType for TestNode {
        fn as_string(&self) -> String {
            self.0.clone()
        }
    }

    #[derive(Clone, Debug, Default, PartialEq)]
    struct TestEdge(String);
    impl EdgeType for TestEdge {
        fn as_string(&self) -> String {
            self.0.clone()
        }
    }

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

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

        let wcc = graph.find_weakly_connected_components().unwrap();
        assert_eq!(wcc.len(), 1);
        assert_eq!(wcc[0], vec![n0, n1, n2]);
    }

    #[test]
    fn test_strongly_connected_components() {
        let mut graph = HeterogeneousGraph::<f64, TestNode, TestEdge>::new(true);
        let n0 = graph.add_node(TestNode("A".to_string()));
        let n1 = graph.add_node(TestNode("B".to_string()));
        let n2 = graph.add_node(TestNode("C".to_string()));

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

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

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

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

        let allowed_edge_types = vec![TestEdge("road".to_string())];
        let wcc = graph
            .find_weakly_connected_components_by_types(&allowed_edge_types)
            .unwrap();
        assert_eq!(wcc.len(), 2);
        assert_eq!(wcc[0], vec![n0, n1]);
        assert_eq!(wcc[1], vec![n2]);
    }

    #[test]
    fn test_strongly_connected_components_by_types() {
        let mut graph = HeterogeneousGraph::<f64, TestNode, TestEdge>::new(true);
        let n0 = graph.add_node(TestNode("A".to_string()));
        let n1 = graph.add_node(TestNode("B".to_string()));
        let n2 = graph.add_node(TestNode("C".to_string()));

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

        let allowed_edge_types = vec![TestEdge("road".to_string()), TestEdge("path".to_string())];
        let scc = graph
            .find_strongly_connected_components_by_types(&allowed_edge_types)
            .unwrap();

        assert_eq!(scc.len(), 1);
        assert_eq!(scc[0], vec![n0, n1, n2]);
    }

    #[test]
    fn test_is_weakly_connected() {
        let mut graph = HeterogeneousGraph::<f64, TestNode, TestEdge>::new(false);
        let n0 = graph.add_node(TestNode("A".to_string()));
        let n1 = graph.add_node(TestNode("B".to_string()));

        graph
            .add_edge(n0, n1, 1.0, TestEdge("road".to_string()))
            .unwrap();

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

    #[test]
    fn test_is_strongly_connected() {
        let mut graph = HeterogeneousGraph::<f64, TestNode, TestEdge>::new(true);
        let n0 = graph.add_node(TestNode("A".to_string()));
        let n1 = graph.add_node(TestNode("B".to_string()));
        let n2 = graph.add_node(TestNode("C".to_string()));

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

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