graphmind_graph_algorithms/
common.rs

1//! Shared utilities for graph algorithms
2//!
3//! Provides a read-only, optimized view of the graph topology for algorithm execution.
4
5use std::collections::HashMap;
6
7/// Node Identifier type (u64)
8pub type NodeId = u64;
9
10/// A dense, integer-indexed view of the graph topology using Compressed Sparse Row (CSR) format.
11pub struct GraphView {
12    /// Number of nodes
13    pub node_count: usize,
14    /// Mapping from dense index (0..N) back to NodeId
15    pub index_to_node: Vec<NodeId>,
16    /// Mapping from NodeId to dense index
17    pub node_to_index: HashMap<NodeId, usize>,
18
19    /// Outgoing edges CSR structure
20    /// Offsets into `out_targets`. Size = node_count + 1
21    pub out_offsets: Vec<usize>,
22    /// Contiguous array of target node indices
23    pub out_targets: Vec<usize>,
24
25    /// Incoming edges CSR structure (Compressed Sparse Column effectively)
26    /// Offsets into `in_sources`. Size = node_count + 1
27    pub in_offsets: Vec<usize>,
28    /// Contiguous array of source node indices
29    pub in_sources: Vec<usize>,
30
31    /// Edge weights: aligned with `out_targets`
32    pub weights: Option<Vec<f64>>,
33}
34
35impl GraphView {
36    /// Get the out-degree of a node (by index)
37    pub fn out_degree(&self, idx: usize) -> usize {
38        self.out_offsets[idx + 1] - self.out_offsets[idx]
39    }
40
41    /// Get the in-degree of a node (by index)
42    pub fn in_degree(&self, idx: usize) -> usize {
43        self.in_offsets[idx + 1] - self.in_offsets[idx]
44    }
45
46    /// Get outgoing neighbors (successors) of a node
47    pub fn successors(&self, idx: usize) -> &[usize] {
48        let start = self.out_offsets[idx];
49        let end = self.out_offsets[idx + 1];
50        &self.out_targets[start..end]
51    }
52
53    /// Get incoming neighbors (predecessors) of a node
54    pub fn predecessors(&self, idx: usize) -> &[usize] {
55        let start = self.in_offsets[idx];
56        let end = self.in_offsets[idx + 1];
57        &self.in_sources[start..end]
58    }
59
60    /// Get weights for outgoing edges of a node
61    pub fn weights(&self, idx: usize) -> Option<&[f64]> {
62        self.weights.as_ref().map(|w| {
63            let start = self.out_offsets[idx];
64            let end = self.out_offsets[idx + 1];
65            &w[start..end]
66        })
67    }
68
69    /// Helper to create GraphView from adjacency lists (legacy/test support)
70    pub fn from_adjacency_list(
71        node_count: usize,
72        index_to_node: Vec<NodeId>,
73        node_to_index: HashMap<NodeId, usize>,
74        outgoing: Vec<Vec<usize>>,
75        incoming: Vec<Vec<usize>>,
76        weights: Option<Vec<Vec<f64>>>,
77    ) -> Self {
78        let mut out_offsets = Vec::with_capacity(node_count + 1);
79        let mut out_targets = Vec::new();
80        let mut in_offsets = Vec::with_capacity(node_count + 1);
81        let mut in_sources = Vec::new();
82        let mut flat_weights = if weights.is_some() {
83            Some(Vec::new())
84        } else {
85            None
86        };
87
88        out_offsets.push(0);
89        for (i, neighbors) in outgoing.into_iter().enumerate() {
90            out_targets.extend(neighbors);
91            out_offsets.push(out_targets.len());
92
93            if let Some(ref mut w_flat) = flat_weights {
94                if let Some(w_row) = weights.as_ref().map(|w| &w[i]) {
95                    w_flat.extend(w_row.iter());
96                }
97            }
98        }
99
100        in_offsets.push(0);
101        for sources in incoming {
102            in_sources.extend(sources);
103            in_offsets.push(in_sources.len());
104        }
105
106        GraphView {
107            node_count,
108            index_to_node,
109            node_to_index,
110            out_offsets,
111            out_targets,
112            in_offsets,
113            in_sources,
114            weights: flat_weights,
115        }
116    }
117}
graphmind_graph_algorithms/common.rs

graphmind_graph_algorithms/
common.rs
