xgraph 3.0.0

//! Centrality measure algorithms for graph analysis
//!
//! Provides implementations for three key centrality measures:
//! - Degree Centrality: Measures node connectivity through edge count
//! - Betweenness Centrality: Quantifies a node's role as a network bridge
//! - Closeness Centrality: Assesses average distance to other nodes
//!
//! All methods return `Result` types to handle potential errors gracefully instead of panicking.
//!
//! # Examples
//!
//! Basic usage with error handling:
//! ```rust
//! use xgraph::graph::graph::Graph;
//! use xgraph::graph::algorithms::centrality::Centrality;
//!
//! let matrix = vec![
//!     vec![0, 1, 1],
//!     vec![1, 0, 1],
//!     vec![1, 1, 0]
//! ];
//! let graph = Graph::from_adjacency_matrix(&matrix, false, 0, 0).unwrap();
//!
//! let degree = graph.degree_centrality().unwrap();
//! let betweenness = graph.betweenness_centrality().unwrap();
//! let closeness = graph.closeness_centrality().unwrap();
//! ```

use crate::core::view::NodeId;
use crate::core::CentralityError as CoreCentralityError;
use crate::graph::graph::Graph;
use std::collections::HashMap;
use std::fmt::Debug;
use std::hash::Hash;

/// Error type for centrality computation failures.
#[derive(Debug, thiserror::Error)]
pub enum CentralityError {
    /// Indicates an invalid node was encountered during computation.
    #[error("Invalid node reference: node ID {0} not found")]
    InvalidNode(NodeId),
    /// Indicates an overflow occurred during distance calculation.
    #[error("Distance calculation overflowed")]
    DistanceOverflow,
}

impl From<CoreCentralityError> for CentralityError {
    fn from(error: CoreCentralityError) -> Self {
        match error {
            CoreCentralityError::InvalidNode(id) => CentralityError::InvalidNode(id),
            // The homogeneous trait exposes no parameterised measure, so this arm is only
            // reachable if one is added to it later.
            CoreCentralityError::InvalidParameter { .. } => CentralityError::DistanceOverflow,
        }
    }
}

/// Trait for calculating centrality measures in graphs
///
/// Provides methods to compute various centrality metrics with proper error handling.
///
/// # Examples
///
/// Analyzing social network influence:
/// ```rust
/// use xgraph::graph::graph::Graph;
/// use xgraph::graph::algorithms::centrality::Centrality;
///
/// 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(bob, charlie, 1, ()).unwrap();
///
/// let betweenness = social_graph.betweenness_centrality().unwrap();
/// assert!(betweenness[&bob] > 0.9);
/// ```
#[deprecated(
    since = "3.0.0",
    note = "superseded by `xgraph::core::Centrality`, which is implemented for every graph \
            view and adds eigenvector centrality, PageRank and Katz centrality"
)]
pub trait Centrality<W, N, E> {
    /// Calculates degree centrality for all nodes
    ///
    /// Degree centrality is defined as the number of edges incident to a node.
    /// Higher values indicate more connected nodes.
    ///
    /// # Returns
    /// - `Ok(HashMap<NodeId, usize>)`: Mapping of node IDs to their degree centrality scores
    /// - `Err(CentralityError)`: If computation fails due to invalid nodes
    fn degree_centrality(&self) -> Result<HashMap<NodeId, usize>, CentralityError>;

    /// Calculates betweenness centrality for all nodes
    ///
    /// Betweenness centrality measures how often a node appears on shortest paths
    /// between other nodes using Brandes' algorithm (O(nm) time complexity).
    /// Scores are normalized to the range [0, 1].
    ///
    /// # Returns
    /// - `Ok(HashMap<NodeId, f64>)`: Mapping of node IDs to their normalized betweenness scores
    /// - `Err(CentralityError)`: If computation fails
    fn betweenness_centrality(&self) -> Result<HashMap<NodeId, f64>, CentralityError>;

    /// Calculates closeness centrality for all nodes
    ///
    /// Closeness centrality is the reciprocal of the average shortest path distance
    /// to all other nodes. Higher values indicate more central positions.
    ///
    /// # Returns
    /// - `Ok(HashMap<NodeId, f64>)`: Mapping of node IDs to their closeness scores
    /// - `Err(CentralityError)`: If computation fails due to overflow or invalid nodes
    fn closeness_centrality(&self) -> Result<HashMap<NodeId, f64>, CentralityError>;
}

#[allow(deprecated)]
impl<W, N, E> Centrality<W, N, E> for Graph<W, N, E>
where
    W: Copy + Default + PartialEq,
    N: Clone + Eq + Hash + Debug,
    E: Clone + Default + Debug,
{
    fn degree_centrality(&self) -> Result<HashMap<NodeId, usize>, CentralityError> {
        Ok(crate::core::Centrality::degree_centrality(self))
    }

    fn betweenness_centrality(&self) -> Result<HashMap<NodeId, f64>, CentralityError> {
        crate::core::Centrality::betweenness_centrality(self).map_err(CentralityError::from)
    }

    fn closeness_centrality(&self) -> Result<HashMap<NodeId, f64>, CentralityError> {
        crate::core::Centrality::closeness_centrality(self).map_err(CentralityError::from)
    }
}

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

    const TOLERANCE: f64 = 1e-5;

    fn assert_approx_eq(a: f64, b: f64) {
        assert!(approx_eq!(f64, a, b, epsilon = TOLERANCE), "{} ≈ {}", a, b);
    }

    #[test]
    fn test_degree_centrality() {
        let matrix = vec![vec![0, 1, 0], vec![1, 0, 1], vec![0, 1, 0]];
        let graph = Graph::from_adjacency_matrix(&matrix, false, (), ()).unwrap();
        let centrality = graph.degree_centrality().unwrap();
        assert_eq!(centrality[&NodeId::from_index(0)], 1);
        assert_eq!(centrality[&NodeId::from_index(1)], 2);
        assert_eq!(centrality[&NodeId::from_index(2)], 1);
    }

    #[test]
    fn test_betweenness_centrality() {
        let matrix = vec![
            vec![0, 1, 0, 0],
            vec![1, 0, 1, 1],
            vec![0, 1, 0, 0],
            vec![0, 1, 0, 0],
        ];
        let graph = Graph::from_adjacency_matrix(&matrix, false, (), ()).unwrap();
        let betweenness = graph.betweenness_centrality().unwrap();
        assert_approx_eq(betweenness[&NodeId::from_index(1)], 1.0);
    }

    #[test]
    fn test_closeness_centrality() {
        let matrix = vec![vec![0, 1, 1], vec![1, 0, 1], vec![1, 1, 0]];
        let graph = Graph::from_adjacency_matrix(&matrix, false, (), ()).unwrap();
        let closeness = graph.closeness_centrality().unwrap();
        assert_approx_eq(closeness[&NodeId::from_index(0)], 1.0);
    }

    #[test]
    fn test_empty_graph() {
        let graph = Graph::<u32, (), ()>::new(false);
        assert!(graph.degree_centrality().unwrap().is_empty());
        assert!(graph.betweenness_centrality().unwrap().is_empty());
        assert!(graph.closeness_centrality().unwrap().is_empty());
    }

    #[test]
    fn test_betweenness_with_sparse_ids() {
        // After removing a node the highest ID exceeds the node count, which previously
        // caused an out-of-bounds panic in the per-source bookkeeping arrays.
        let mut graph = Graph::<u32, (), ()>::new(false);
        let ids: Vec<_> = (0..4).map(|_| graph.add_node(())).collect();
        graph.add_edge(ids[1], ids[2], 1, ()).unwrap();
        graph.add_edge(ids[2], ids[3], 1, ()).unwrap();
        graph.remove_node(ids[0]).unwrap();

        let betweenness = graph.betweenness_centrality().unwrap();
        // The middle node of the path is the only one lying on a shortest path.
        assert!(betweenness.get(&ids[2]).copied().unwrap_or(0.0) > 0.0);
        assert_eq!(betweenness.get(&ids[1]).copied().unwrap_or(0.0), 0.0);
    }
}