aprender-core 0.29.1

Next-generation machine learning library in pure Rust
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77

//! Graph construction and analysis with cache-optimized CSR representation.
//!
//! This module provides high-performance graph algorithms built on top of
//! Compressed Sparse Row (CSR) format for maximum cache locality. Key features:
//!
//! - CSR representation (50-70% memory reduction vs `HashMap`)
//! - Centrality measures (degree, betweenness, `PageRank`)
//! - Parallel algorithms using Rayon
//! - Numerical stability (Kahan summation in `PageRank`)
//!
//! # Examples
//!
//! ```
//! use aprender::graph::{Graph, GraphCentrality};
//!
//! let g = Graph::from_edges(&[(0, 1), (1, 2), (2, 0)], false);
//!
//! let dc = g.degree_centrality();
//! assert_eq!(dc.len(), 3);
//! ```

use std::collections::{HashMap, VecDeque};

pub mod centrality;

pub use centrality::GraphCentrality;

/// Graph node identifier (contiguous integers for cache efficiency).
pub type NodeId = usize;

/// Graph edge with optional weight.
#[derive(Debug, Clone, PartialEq)]
pub struct Edge {
    pub source: NodeId,
    pub target: NodeId,
    pub weight: Option<f64>,
}

/// Graph structure using CSR (Compressed Sparse Row) for cache efficiency.
///
/// Memory layout inspired by Combinatorial BLAS (Buluc et al. 2009):
/// - Adjacency stored as two flat vectors (CSR format)
/// - Node labels stored separately (accessed rarely)
/// - String→NodeId mapping via `HashMap` (build-time only)
///
/// # Performance
/// - Memory: 50-70% reduction vs `HashMap` (no pointer overhead)
/// - Cache misses: 3-5x fewer (sequential access pattern)
/// - SIMD-friendly: Neighbor iteration can use vectorization
#[derive(Debug)]
pub struct Graph {
    // CSR adjacency representation (cache-friendly)
    row_ptr: Vec<usize>,      // Offset into col_indices (length = n_nodes + 1)
    col_indices: Vec<NodeId>, // Flattened neighbor lists (length = n_edges)
    edge_weights: Vec<f64>,   // Parallel to col_indices (empty if unweighted)

    // Metadata (accessed less frequently)
    #[allow(dead_code)]
    node_labels: Vec<Option<String>>, // Indexed by NodeId
    #[allow(dead_code)]
    label_to_id: HashMap<String, NodeId>, // For label lookups

    is_directed: bool,
    n_nodes: usize,
    n_edges: usize,
}

include!("algorithms.rs");
include!("test_module.rs");

#[cfg(test)]
#[path = "tests_dijkstra_contract.rs"]
mod tests_dijkstra_contract;

#[cfg(test)]
#[path = "tests_community_contract.rs"]
mod tests_community_contract;