ringkernel_graph/models/
node.rs

1//! Node types for graph algorithms.
2//!
3//! This module provides strongly-typed wrappers for graph concepts:
4//! - [`NodeId`]: Unique identifier for graph vertices
5//! - [`Distance`]: BFS distance/level from source
6//! - [`ComponentId`]: Connected component identifier
7
8use bytemuck::{Pod, Zeroable};
9
10/// Node identifier (vertex ID).
11///
12/// Using a newtype prevents mixing up node IDs with other integers.
13#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash, Default, PartialOrd, Ord)]
14#[repr(transparent)]
15pub struct NodeId(pub u32);
16
17impl NodeId {
18    /// Maximum valid node ID.
19    pub const MAX: NodeId = NodeId(u32::MAX - 1);
20
21    /// Invalid/sentinel node ID.
22    pub const INVALID: NodeId = NodeId(u32::MAX);
23
24    /// Create a new node ID.
25    pub const fn new(id: u32) -> Self {
26        NodeId(id)
27    }
28
29    /// Check if this is a valid node ID.
30    pub const fn is_valid(&self) -> bool {
31        self.0 != u32::MAX
32    }
33
34    /// Get the inner value.
35    pub const fn get(&self) -> u32 {
36        self.0
37    }
38}
39
40impl From<u32> for NodeId {
41    fn from(id: u32) -> Self {
42        NodeId(id)
43    }
44}
45
46impl From<usize> for NodeId {
47    fn from(id: usize) -> Self {
48        NodeId(id as u32)
49    }
50}
51
52impl From<NodeId> for usize {
53    fn from(id: NodeId) -> Self {
54        id.0 as usize
55    }
56}
57
58// SAFETY: NodeId is #[repr(transparent)] over u32
59unsafe impl Zeroable for NodeId {}
60unsafe impl Pod for NodeId {}
61
62/// Distance from source in BFS.
63///
64/// Also known as "level" or "hop count".
65#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash, Default, PartialOrd, Ord)]
66#[repr(transparent)]
67pub struct Distance(pub u32);
68
69impl Distance {
70    /// Infinity (unreachable).
71    pub const INFINITY: Distance = Distance(u32::MAX);
72
73    /// Zero distance (source node).
74    pub const ZERO: Distance = Distance(0);
75
76    /// Create a new distance.
77    pub const fn new(d: u32) -> Self {
78        Distance(d)
79    }
80
81    /// Check if node is reachable.
82    pub const fn is_reachable(&self) -> bool {
83        self.0 != u32::MAX
84    }
85
86    /// Get the inner value.
87    pub const fn get(&self) -> u32 {
88        self.0
89    }
90
91    /// Increment distance by 1, saturating at infinity.
92    pub const fn increment(&self) -> Self {
93        if self.0 == u32::MAX {
94            Distance::INFINITY
95        } else {
96            Distance(self.0.saturating_add(1))
97        }
98    }
99}
100
101impl From<u32> for Distance {
102    fn from(d: u32) -> Self {
103        Distance(d)
104    }
105}
106
107// SAFETY: Distance is #[repr(transparent)] over u32
108unsafe impl Zeroable for Distance {}
109unsafe impl Pod for Distance {}
110
111/// Connected component identifier.
112///
113/// Nodes in the same component have the same ComponentId.
114#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash, Default, PartialOrd, Ord)]
115#[repr(transparent)]
116pub struct ComponentId(pub u32);
117
118impl ComponentId {
119    /// Unassigned component.
120    pub const UNASSIGNED: ComponentId = ComponentId(u32::MAX);
121
122    /// Create a new component ID.
123    pub const fn new(id: u32) -> Self {
124        ComponentId(id)
125    }
126
127    /// Check if component is assigned.
128    pub const fn is_assigned(&self) -> bool {
129        self.0 != u32::MAX
130    }
131
132    /// Get the inner value.
133    pub const fn get(&self) -> u32 {
134        self.0
135    }
136}
137
138impl From<u32> for ComponentId {
139    fn from(id: u32) -> Self {
140        ComponentId(id)
141    }
142}
143
144impl From<NodeId> for ComponentId {
145    fn from(id: NodeId) -> Self {
146        ComponentId(id.0)
147    }
148}
149
150// SAFETY: ComponentId is #[repr(transparent)] over u32
151unsafe impl Zeroable for ComponentId {}
152unsafe impl Pod for ComponentId {}
153
154#[cfg(test)]
155mod tests {
156    use super::*;
157
158    #[test]
159    fn test_node_id_basics() {
160        let node = NodeId::new(42);
161        assert_eq!(node.get(), 42);
162        assert!(node.is_valid());
163        assert!(!NodeId::INVALID.is_valid());
164    }
165
166    #[test]
167    fn test_node_id_conversions() {
168        let node: NodeId = 100u32.into();
169        assert_eq!(node.get(), 100);
170
171        let idx: usize = node.into();
172        assert_eq!(idx, 100);
173    }
174
175    #[test]
176    fn test_distance_basics() {
177        let d = Distance::new(5);
178        assert_eq!(d.get(), 5);
179        assert!(d.is_reachable());
180        assert!(!Distance::INFINITY.is_reachable());
181    }
182
183    #[test]
184    fn test_distance_increment() {
185        let d = Distance::new(5);
186        assert_eq!(d.increment().get(), 6);
187
188        // Saturates at infinity
189        assert_eq!(Distance::INFINITY.increment(), Distance::INFINITY);
190    }
191
192    #[test]
193    fn test_component_id_basics() {
194        let c = ComponentId::new(3);
195        assert_eq!(c.get(), 3);
196        assert!(c.is_assigned());
197        assert!(!ComponentId::UNASSIGNED.is_assigned());
198    }
199
200    #[test]
201    fn test_pod_traits() {
202        // Verify types are Pod-compatible
203        let nodes = [NodeId::new(0), NodeId::new(1), NodeId::new(2)];
204        let bytes = bytemuck::bytes_of(&nodes);
205        assert_eq!(bytes.len(), 12); // 3 * 4 bytes
206
207        let distances = [Distance::ZERO, Distance::new(1), Distance::INFINITY];
208        let bytes = bytemuck::bytes_of(&distances);
209        assert_eq!(bytes.len(), 12);
210    }
211}
ringkernel_graph/models/node.rs

ringkernel_graph/models/
node.rs
