god_gragh/edge/
mod.rs

1//! 边索引和边引用模块
2//!
3//! 提供稳定的边索引机制，使用 generation 计数防止 ABA 问题
4
5use core::fmt;
6use core::hash::{Hash, Hasher};
7
8use crate::node::NodeIndex;
9
10#[cfg(feature = "serde")]
11use serde::{Deserialize, Serialize};
12
13/// 边索引：稳定引用边的句柄
14///
15/// 包含槽位索引和 generation 计数，确保删除后不会错误访问新边
16#[derive(Copy, Clone, PartialEq, Eq, PartialOrd, Ord)]
17#[cfg_attr(feature = "serde", derive(Serialize, Deserialize))]
18pub struct EdgeIndex {
19    /// 在边存储中的索引
20    pub(crate) index: usize,
21    /// Generation 计数器，防止 ABA 问题
22    pub(crate) generation: u32,
23}
24
25impl EdgeIndex {
26    /// 创建新的 EdgeIndex（内部使用）
27    #[inline]
28    pub(crate) fn new(index: usize, generation: u32) -> Self {
29        Self { index, generation }
30    }
31
32    /// 获取索引
33    #[inline]
34    pub fn index(&self) -> usize {
35        self.index
36    }
37
38    /// 获取 generation 计数
39    #[inline]
40    pub fn generation(&self) -> u32 {
41        self.generation
42    }
43
44    /// 检查索引是否有效
45    #[inline]
46    #[allow(dead_code)]
47    pub(crate) fn is_valid(&self) -> bool {
48        self.index != usize::MAX
49    }
50
51    /// 创建无效索引
52    #[inline]
53    #[allow(dead_code)]
54    pub(crate) fn invalid() -> Self {
55        Self {
56            index: usize::MAX,
57            generation: 0,
58        }
59    }
60}
61
62impl fmt::Debug for EdgeIndex {
63    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
64        write!(f, "EdgeIndex({}, {})", self.index, self.generation)
65    }
66}
67
68impl Hash for EdgeIndex {
69    fn hash<H: Hasher>(&self, state: &mut H) {
70        self.index.hash(state);
71        self.generation.hash(state);
72    }
73}
74
75/// 边引用：对图中边的借用引用
76///
77/// 包含边索引、端点和数据引用，生命周期与图绑定
78pub struct EdgeRef<'a, E> {
79    /// 边索引
80    pub index: EdgeIndex,
81    /// 源节点索引
82    pub source: NodeIndex,
83    /// 目标节点索引
84    pub target: NodeIndex,
85    /// 边数据引用
86    pub data: &'a E,
87}
88
89impl<'a, E> EdgeRef<'a, E> {
90    /// 创建新的 EdgeRef
91    #[inline]
92    pub fn new(index: EdgeIndex, source: NodeIndex, target: NodeIndex, data: &'a E) -> Self {
93        Self {
94            index,
95            source,
96            target,
97            data,
98        }
99    }
100
101    /// 获取边索引
102    #[inline]
103    pub fn index(&self) -> EdgeIndex {
104        self.index
105    }
106
107    /// 获取源节点索引
108    #[inline]
109    pub fn source(&self) -> NodeIndex {
110        self.source
111    }
112
113    /// 获取目标节点索引
114    #[inline]
115    pub fn target(&self) -> NodeIndex {
116        self.target
117    }
118
119    /// 获取边数据引用
120    #[inline]
121    pub fn data(&self) -> &'a E {
122        self.data
123    }
124
125    /// 获取端点对
126    #[inline]
127    pub fn endpoints(&self) -> (NodeIndex, NodeIndex) {
128        (self.source, self.target)
129    }
130}
131
132impl<'a, E> Clone for EdgeRef<'a, E> {
133    fn clone(&self) -> Self {
134        *self
135    }
136}
137
138impl<'a, E> Copy for EdgeRef<'a, E> {}
139
140impl<'a, E> fmt::Debug for EdgeRef<'a, E>
141where
142    E: fmt::Debug,
143{
144    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
145        f.debug_struct("EdgeRef")
146            .field("index", &self.index)
147            .field("source", &self.source)
148            .field("target", &self.target)
149            .field("data", self.data)
150            .finish()
151    }
152}
153
154/// 边存储结构
155///
156/// 包含源节点、目标节点和边数据
157/// 使用 64 字节对齐，避免 false sharing
158#[derive(Debug)]
159#[cfg_attr(feature = "serde", derive(Serialize, Deserialize))]
160#[cfg_attr(
161    feature = "serde",
162    serde(bound(serialize = "E: Serialize", deserialize = "E: Deserialize<'de>"))
163)]
164#[repr(align(64))]
165pub(crate) struct EdgeStorage<E> {
166    /// 源节点索引
167    pub source: NodeIndex,
168    /// 目标节点索引
169    pub target: NodeIndex,
170    /// 边数据
171    pub data: Option<E>,
172    /// Generation 计数器
173    pub generation: u32,
174}
175
176impl<E> Clone for EdgeStorage<E> {
177    fn clone(&self) -> Self {
178        Self {
179            source: self.source,
180            target: self.target,
181            data: None, // 不克隆数据
182            generation: self.generation,
183        }
184    }
185}
186
187impl<E> EdgeStorage<E> {
188    /// 创建新的边存储
189    #[inline]
190    pub(crate) fn new(source: NodeIndex, target: NodeIndex, data: E, generation: u32) -> Self {
191        Self {
192            source,
193            target,
194            data: Some(data),
195            generation,
196        }
197    }
198
199    /// 创建已删除的边存储
200    #[inline]
201    #[allow(dead_code)]
202    pub(crate) fn deleted(source: NodeIndex, target: NodeIndex, generation: u32) -> Self {
203        Self {
204            source,
205            target,
206            data: None,
207            generation,
208        }
209    }
210
211    /// 检查边是否被占用
212    #[inline]
213    pub(crate) fn is_occupied(&self) -> bool {
214        self.data.is_some()
215    }
216
217    /// 获取数据引用
218    #[inline]
219    pub(crate) fn data(&self) -> Option<&E> {
220        self.data.as_ref()
221    }
222
223    /// 获取数据可变引用
224    #[inline]
225    #[allow(dead_code)]
226    pub(crate) fn data_mut(&mut self) -> Option<&mut E> {
227        self.data.as_mut()
228    }
229
230    /// 获取端点对
231    #[inline]
232    #[allow(dead_code)]
233    pub(crate) fn endpoints(&self) -> (NodeIndex, NodeIndex) {
234        (self.source, self.target)
235    }
236}
237
238#[cfg(test)]
239mod tests {
240    use super::*;
241
242    #[test]
243    fn test_edge_index_creation() {
244        let idx = EdgeIndex::new(42, 1);
245        assert_eq!(idx.index(), 42);
246        assert_eq!(idx.generation(), 1);
247        assert!(idx.is_valid());
248    }
249
250    #[test]
251    fn test_edge_index_invalid() {
252        let idx = EdgeIndex::invalid();
253        assert!(!idx.is_valid());
254        assert_eq!(idx.index(), usize::MAX);
255    }
256
257    #[test]
258    fn test_edge_ref() {
259        let source = NodeIndex::new(0, 1);
260        let target = NodeIndex::new(1, 1);
261        let edge_idx = EdgeIndex::new(0, 1);
262
263        let edge_ref = EdgeRef::new(edge_idx, source, target, &42.0);
264
265        assert_eq!(edge_ref.index(), edge_idx);
266        assert_eq!(edge_ref.source(), source);
267        assert_eq!(edge_ref.target(), target);
268        assert_eq!(*edge_ref.data(), 42.0);
269        assert_eq!(edge_ref.endpoints(), (source, target));
270    }
271
272    #[test]
273    fn test_edge_storage() {
274        let source = NodeIndex::new(0, 1);
275        let target = NodeIndex::new(1, 1);
276
277        let edge = EdgeStorage::new(source, target, 42.0, 1);
278        assert!(edge.is_occupied());
279        assert_eq!(edge.data(), Some(&42.0));
280
281        let deleted: EdgeStorage<f64> = EdgeStorage::deleted(source, target, 1);
282        assert!(!deleted.is_occupied());
283        assert_eq!(deleted.data(), None);
284    }
285}
god_gragh/edge/mod.rs

god_gragh/edge/
mod.rs
