god_gragh/graph/
impl_.rs

1//! Graph 核心实现
2//!
3//! 使用桶式邻接表（Bucket Adjacency List）和 Arena 分配器实现高性能图数据结构
4//!
5//! ## 内存布局说明
6//!
7//! 本实现采用**桶式邻接表**（Bucket Adjacency List）格式，而非传统 CSR（压缩稀疏行）：
8//!
9//! | 特性 | 传统 CSR | 本实现（桶式邻接表） |
10//! |------|----------|---------------------|
11//! | 结构 | row_offsets + col_indices | `Vec<AdjBucket>`，每个 bucket 含独立 Vec |
12//! | 增量更新 | ❌ 不支持（需 O(V+E) 重建） | ✅ O(1) 插入 |
13//! | 空间效率 | ✅ 最优（无额外开销） | ⚠️ 略高（每节点一个 Vec 头） |
14//! | 适用场景 | 静态图 | 动态图（频繁增删边） |
15//!
16//! 历史原因：早期代码使用 `CsrStorage` 命名，实际实现是桶式邻接表。
17//! 为保持 API 稳定性，内部结构仍用此名，但文档已正名为**桶式邻接表**。
18
19use core::fmt;
20
21#[cfg(feature = "serde")]
22use serde::{Serialize, Deserialize};
23
24use crate::edge::{EdgeIndex, EdgeRef, EdgeStorage};
25use crate::errors::{GraphError, GraphResult};
26use crate::node::{NodeIndex, NodeRef, NodeSlot};
27use crate::graph::traits::{GraphBase, GraphOps, GraphQuery};
28
29/// 单个邻接桶，用于 O(1) 增量边插入
30/// 使用 64 字节缓存行对齐，避免 false sharing
31#[derive(Clone, Debug)]
32#[repr(align(64))]
33#[cfg_attr(feature = "serde", derive(Serialize, Deserialize))]
34pub(crate) struct AdjBucket {
35    neighbors: Vec<usize>,
36    edge_indices: Vec<usize>,
37    deleted_mask: Vec<u64>,
38    deleted_count: usize,
39    _padding: [u8; 8], // 确保 64 字节对齐
40}
41
42impl AdjBucket {
43    fn new() -> Self {
44        Self {
45            neighbors: Vec::new(),
46            edge_indices: Vec::new(),
47            deleted_mask: Vec::new(),
48            deleted_count: 0,
49            _padding: [0; 8],
50        }
51    }
52
53    #[inline]
54    fn push(&mut self, target: usize, edge_idx: usize) {
55        self.neighbors.push(target);
56        self.edge_indices.push(edge_idx);
57        let bit_idx = self.neighbors.len() - 1;
58        let word_idx = bit_idx / 64;
59        while self.deleted_mask.len() <= word_idx {
60            self.deleted_mask.push(0);
61        }
62    }
63
64    #[inline]
65    fn mark_deleted(&mut self, pos: usize) {
66        let word_idx = pos / 64;
67        let bit = pos % 64;
68        if word_idx < self.deleted_mask.len() {
69            let mask = 1u64 << bit;
70            if self.deleted_mask[word_idx] & mask == 0 {
71                self.deleted_mask[word_idx] |= mask;
72                self.deleted_count += 1;
73            }
74        }
75    }
76
77    #[inline]
78    fn is_deleted(&self, pos: usize) -> bool {
79        let word_idx = pos / 64;
80        let bit = pos % 64;
81        if word_idx >= self.deleted_mask.len() {
82            return false;
83        }
84        self.deleted_mask[word_idx] & (1u64 << bit) != 0
85    }
86
87    #[inline]
88    fn compact(&mut self) {
89        if self.deleted_count == 0 {
90            return;
91        }
92        let mut write_pos = 0;
93        for read_pos in 0..self.neighbors.len() {
94            if !self.is_deleted(read_pos) {
95                if write_pos != read_pos {
96                    self.neighbors[write_pos] = self.neighbors[read_pos];
97                    self.edge_indices[write_pos] = self.edge_indices[read_pos];
98                }
99                write_pos += 1;
100            }
101        }
102        self.neighbors.truncate(write_pos);
103        self.edge_indices.truncate(write_pos);
104        let words_needed = write_pos.div_ceil(64);
105        self.deleted_mask.truncate(words_needed);
106        for w in self.deleted_mask.iter_mut() {
107            *w = 0;
108        }
109        self.deleted_count = 0;
110    }
111
112    #[inline]
113    fn find(&self, target: usize) -> Option<usize> {
114        self.neighbors
115            .iter()
116            .position(|&n| n == target)
117            .filter(|&pos| !self.is_deleted(pos))
118    }
119
120    #[inline]
121    fn len(&self) -> usize {
122        self.neighbors.len() - self.deleted_count
123    }
124
125    #[inline]
126    fn iter(&self) -> AdjBucketIter<'_> {
127        AdjBucketIter {
128            bucket: self,
129            pos: 0,
130        }
131    }
132
133    /// 获取有效邻居的快照（用于快照语义迭代器）
134    #[inline]
135    fn snapshot(&self) -> Vec<(usize, usize)> {
136        self.iter().collect()
137    }
138}
139
140/// 邻接桶迭代器
141pub(crate) struct AdjBucketIter<'a> {
142    bucket: &'a AdjBucket,
143    pos: usize,
144}
145
146impl<'a> Iterator for AdjBucketIter<'a> {
147    type Item = (usize, usize); // (target, edge_index)
148
149    #[inline]
150    fn next(&mut self) -> Option<Self::Item> {
151        while self.pos < self.bucket.neighbors.len() {
152            // 软件预取：预取下一批数据到 CPU 缓存（需要 nightly 特性）
153            // 在稳定版 Rust 上使用 std::hint 或条件编译
154            #[cfg(all(feature = "unstable", target_feature = "sse"))]
155            {
156                use core::arch::x86_64::_mm_prefetch;
157                use core::arch::x86_64::_MM_HINT_T0;
158
159                let prefetch_pos = self.pos + 4;
160                if prefetch_pos < self.bucket.neighbors.len() {
161                    unsafe {
162                        _mm_prefetch(
163                            self.bucket.neighbors.as_ptr().add(prefetch_pos) as *const i8,
164                            _MM_HINT_T0,
165                        );
166                        _mm_prefetch(
167                            self.bucket.edge_indices.as_ptr().add(prefetch_pos) as *const i8,
168                            _MM_HINT_T0,
169                        );
170                    }
171                }
172            }
173
174            let pos = self.pos;
175            self.pos += 1;
176            if !self.bucket.is_deleted(pos) {
177                return Some((self.bucket.neighbors[pos], self.bucket.edge_indices[pos]));
178            }
179        }
180        None
181    }
182}
183
184/// 邻居迭代器（快照语义）
185///
186/// 在创建时捕获目标节点的 generation，迭代期间只返回该快照中的邻居
187pub struct NeighborsIter {
188    /// 原始邻居数据快照（target_idx, generation）
189    snapshot: std::vec::IntoIter<(usize, u32)>,
190}
191
192impl NeighborsIter {
193    pub(crate) fn new(snapshot: Vec<(usize, u32)>) -> Self {
194        Self {
195            snapshot: snapshot.into_iter(),
196        }
197    }
198}
199
200impl Iterator for NeighborsIter {
201    type Item = NodeIndex;
202
203    #[inline]
204    fn next(&mut self) -> Option<Self::Item> {
205        self.snapshot.next().map(|(idx, generation)| NodeIndex::new(idx, generation))
206    }
207}
208
209/// 关联边迭代器（快照语义）
210///
211/// 在创建时捕获边的 generation，迭代期间只返回该快照中的边
212pub struct IncidentEdgesIter {
213    /// 原始边数据快照（edge_idx, generation）
214    snapshot: std::vec::IntoIter<(usize, u32)>,
215}
216
217impl IncidentEdgesIter {
218    pub(crate) fn new(snapshot: Vec<(usize, u32)>) -> Self {
219        Self {
220            snapshot: snapshot.into_iter(),
221        }
222    }
223}
224
225impl Iterator for IncidentEdgesIter {
226    type Item = EdgeIndex;
227
228    #[inline]
229    fn next(&mut self) -> Option<Self::Item> {
230        self.snapshot.next().map(|(idx, generation)| EdgeIndex::new(idx, generation))
231    }
232}
233
234/// 邻接桶存储：桶式邻接表格式
235///
236/// ## 命名说明
237///
238/// 历史原因：早期代码使用 `CsrStorage` 命名，但实际实现是**桶式邻接表**（Bucket Adjacency List）。
239/// 传统 CSR（压缩稀疏行）格式使用 `row_offsets + col_indices`，不支持 O(1) 增量更新。
240/// 本实现使用 `Vec<AdjBucket>`，每个 bucket 含独立 `Vec`，支持 O(1) 插入和惰性删除。
241///
242/// 为保持 API 稳定性，保留 `CsrStorage` 别名，但推荐在新代码中使用 `AdjacencyBuckets`。
243#[derive(Clone, Debug)]
244#[cfg_attr(feature = "serde", derive(Serialize, Deserialize))]
245pub(crate) struct AdjacencyBuckets {
246    buckets: Vec<AdjBucket>,
247    reverse_buckets: Vec<AdjBucket>,
248    num_nodes: usize,
249    needs_compact: bool,
250}
251
252/// 向后兼容别名
253///
254/// 历史原因：早期代码使用 `CsrStorage` 命名，但实际实现是桶式邻接表。
255/// 为保持 API 稳定性保留此别名，但推荐在新代码中使用 `AdjacencyBuckets`。
256#[deprecated(since = "0.3.1", note = "使用 AdjacencyBuckets 代替，命名更准确反映实现")]
257#[allow(dead_code)]
258pub(crate) type CsrStorage = AdjacencyBuckets;
259
260impl AdjacencyBuckets {
261    pub(crate) fn new() -> Self {
262        let this = Self {
263            buckets: Vec::new(),
264            reverse_buckets: Vec::new(),
265            num_nodes: 0,
266            needs_compact: false,
267        };
268        // 验证空 Vec 的对齐（空指针 0 % 64 = 0，总是成立，但保留断言用于文档说明）
269        debug_assert_eq!(this.buckets.as_ptr() as usize % 64, 0, "buckets 初始对齐失败");
270        debug_assert_eq!(this.reverse_buckets.as_ptr() as usize % 64, 0, "reverse_buckets 初始对齐失败");
271        this
272    }
273
274    /// 验证 buckets 的 64 字节对齐
275    ///
276    /// 使用运行时断言确保 Vec<AdjBucket> 的指针是 64 字节对齐的。
277    /// AdjBucket 使用 #[repr(align(64))]，但需要验证实际分配的对齐。
278    ///
279    /// ## Panics
280    ///
281    /// 如果对齐不正确会 panic，并输出详细的调试信息。
282    #[inline]
283    pub(crate) fn assert_aligned(&self) {
284        let buckets_ptr = self.buckets.as_ptr() as usize;
285        let reverse_ptr = self.reverse_buckets.as_ptr() as usize;
286        assert_eq!(
287            buckets_ptr % 64, 0,
288            "AdjacencyBuckets: buckets 未 64 字节对齐 (ptr={:#x}, mod={})",
289            buckets_ptr, buckets_ptr % 64
290        );
291        assert_eq!(
292            reverse_ptr % 64, 0,
293            "AdjacencyBuckets: reverse_buckets 未 64 字节对齐 (ptr={:#x}, mod={})",
294            reverse_ptr, reverse_ptr % 64
295        );
296    }
297
298    pub(crate) fn reserve(&mut self, nodes: usize, _edges: usize) {
299        self.buckets.reserve(nodes);
300        self.reverse_buckets.reserve(nodes);
301        // 验证分配后的对齐
302        self.assert_aligned();
303    }
304
305    fn ensure_capacity(&mut self, node_index: usize) {
306        while self.buckets.len() <= node_index {
307            self.buckets.push(AdjBucket::new());
308        }
309        while self.reverse_buckets.len() <= node_index {
310            self.reverse_buckets.push(AdjBucket::new());
311        }
312        self.num_nodes = self.buckets.len();
313        // 验证扩容后的对齐
314        self.assert_aligned();
315    }
316
317    /// O(1) 添加边
318    pub(crate) fn add_edge(&mut self, node_index: usize, target_index: usize, edge_index: usize) {
319        self.ensure_capacity(node_index.max(target_index));
320        self.buckets[node_index].push(target_index, edge_index);
321        self.reverse_buckets[target_index].push(node_index, edge_index);
322    }
323
324    /// 标记边为已删除
325    pub(crate) fn mark_edge_deleted(&mut self, node_index: usize, target_index: usize) {
326        if let Some(pos) = self.buckets[node_index].find(target_index) {
327            self.buckets[node_index].mark_deleted(pos);
328            self.needs_compact = true;
329        }
330        if let Some(pos) = self.reverse_buckets[target_index].find(node_index) {
331            self.reverse_buckets[target_index].mark_deleted(pos);
332        }
333    }
334
335    pub(crate) fn compact(&mut self) {
336        if !self.needs_compact {
337            return;
338        }
339        for bucket in &mut self.buckets {
340            bucket.compact();
341        }
342        for bucket in &mut self.reverse_buckets {
343            bucket.compact();
344        }
345        self.needs_compact = false;
346    }
347
348    #[allow(dead_code)]
349    pub(crate) fn neighbors_raw(&self, node_index: usize) -> impl Iterator<Item = usize> + '_ {
350        self.buckets
351            .get(node_index)
352            .into_iter()
353            .flat_map(|b| b.iter())
354            .map(move |(target_idx, _)| target_idx)
355    }
356
357    #[allow(dead_code)]
358    pub(crate) fn reverse_neighbors_raw(&self, node_index: usize) -> impl Iterator<Item = usize> + '_ {
359        self.reverse_buckets
360            .get(node_index)
361            .into_iter()
362            .flat_map(|b| b.iter())
363            .map(move |(src_idx, _)| src_idx)
364    }
365
366    pub(crate) fn edge_indices_iter(
367        &self,
368        node_index: usize,
369    ) -> impl Iterator<Item = usize> + '_ {
370        self.buckets
371            .get(node_index)
372            .into_iter()
373            .flat_map(|b| b.iter().map(|(_, ei)| ei))
374    }
375
376    /// 获取边索引的快照（用于快照语义迭代器）
377    pub(crate) fn edge_indices_snapshot(&self, node_index: usize) -> Vec<usize> {
378        self.edge_indices_iter(node_index).collect()
379    }
380
381    /// 获取邻居的快照（用于快照语义迭代器）
382    pub(crate) fn neighbors_snapshot(&self, node_index: usize) -> Vec<(usize, usize)> {
383        self.buckets
384            .get(node_index)
385            .map(|b| b.snapshot())
386            .unwrap_or_default()
387    }
388
389    pub(crate) fn has_edge(&self, node_index: usize, target_index: usize) -> bool {
390        self.buckets
391            .get(node_index)
392            .and_then(|b| b.find(target_index))
393            .is_some()
394    }
395
396    pub(crate) fn degree(&self, node_index: usize) -> usize {
397        self.buckets.get(node_index).map(|b| b.len()).unwrap_or(0)
398    }
399
400    pub(crate) fn in_degree(&self, node_index: usize) -> usize {
401        self.reverse_buckets
402            .get(node_index)
403            .map(|b| b.len())
404            .unwrap_or(0)
405    }
406
407    pub(crate) fn reverse_edge_indices_iter(
408        &self,
409        node_index: usize,
410    ) -> impl Iterator<Item = usize> + '_ {
411        self.reverse_buckets
412            .get(node_index)
413            .into_iter()
414            .flat_map(|b| b.iter().map(|(_, ei)| ei))
415    }
416
417    pub(crate) fn clear(&mut self) {
418        self.buckets.clear();
419        self.reverse_buckets.clear();
420        self.num_nodes = 0;
421        self.needs_compact = false;
422    }
423
424    #[allow(dead_code)]
425    pub(crate) fn num_nodes(&self) -> usize {
426        self.num_nodes
427    }
428}
429
430impl Default for AdjacencyBuckets {
431    fn default() -> Self {
432        Self::new()
433    }
434}
435
436/// 图结构主实现
437/// 使用缓存行对齐优化，减少 false sharing
438#[derive(Clone)]
439#[cfg_attr(feature = "serde", derive(Serialize, Deserialize))]
440#[cfg_attr(feature = "serde", serde(bound(
441    serialize = "T: Serialize, E: Serialize",
442    deserialize = "T: Deserialize<'de>, E: Deserialize<'de>"
443)))]
444pub struct Graph<T, E> {
445    nodes: Vec<NodeSlot<T>>,
446    edges: Vec<EdgeStorage<E>>,
447    csr: AdjacencyBuckets,
448    node_count: usize,
449    edge_count: usize,
450    free_nodes: Vec<usize>,
451    free_edges: Vec<usize>,
452}
453
454impl<T, E> fmt::Debug for Graph<T, E>
455where
456    T: fmt::Debug,
457    E: fmt::Debug,
458{
459    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
460        f.debug_struct("Graph")
461            .field("node_count", &self.node_count)
462            .field("edge_count", &self.edge_count)
463            .finish()
464    }
465}
466
467impl<T, E> Graph<T, E> {
468    /// 创建新的有向图
469    pub fn directed() -> Self {
470        Self {
471            nodes: Vec::new(),
472            edges: Vec::new(),
473            csr: AdjacencyBuckets::new(),
474            node_count: 0,
475            edge_count: 0,
476            free_nodes: Vec::new(),
477            free_edges: Vec::new(),
478        }
479    }
480
481    /// 创建新的无向图
482    pub fn undirected() -> Self {
483        Self::directed()
484    }
485
486    /// 创建带预分配容量的有向图
487    pub fn with_capacity(nodes: usize, edges: usize) -> Self {
488        let mut graph = Self::directed();
489        graph.reserve(nodes, edges);
490        graph
491    }
492
493    /// 检查图是否为空
494    #[inline]
495    pub fn is_empty(&self) -> bool {
496        self.node_count == 0
497    }
498
499    /// 清空图
500    pub fn clear(&mut self) {
501        self.nodes.clear();
502        self.edges.clear();
503        self.csr.clear();
504        self.node_count = 0;
505        self.edge_count = 0;
506        self.free_nodes.clear();
507        self.free_edges.clear();
508    }
509
510    /// 通过节点索引获取边数据
511    pub fn get_edge_by_nodes(&self, from: NodeIndex, to: NodeIndex) -> GraphResult<&E> {
512        for edge_idx in self.csr.edge_indices_iter(from.index()) {
513            if edge_idx < self.edges.len() {
514                let edge = &self.edges[edge_idx];
515                if edge.is_occupied() && edge.target == to {
516                    return edge.data().ok_or(GraphError::EdgeNotFound { index: edge_idx });
517                }
518            }
519        }
520        Err(GraphError::EdgeNotFound { index: usize::MAX })
521    }
522}
523
524impl<T, E> GraphBase for Graph<T, E> {
525    type NodeData = T;
526    type EdgeData = E;
527
528    #[inline]
529    fn node_count(&self) -> usize {
530        self.node_count
531    }
532
533    #[inline]
534    fn edge_count(&self) -> usize {
535        self.edge_count
536    }
537
538    #[inline]
539    fn contains_node(&self, index: NodeIndex) -> bool {
540        if index.index() >= self.nodes.len() {
541            return false;
542        }
543        let slot = &self.nodes[index.index()];
544        slot.is_occupied() && slot.generation == index.generation()
545    }
546
547    #[inline]
548    fn contains_edge(&self, index: EdgeIndex) -> bool {
549        if index.index() >= self.edges.len() {
550            return false;
551        }
552        let edge = &self.edges[index.index()];
553        edge.is_occupied() && edge.generation == index.generation()
554    }
555}
556
557impl<T, E> GraphQuery for Graph<T, E> {
558    #[inline]
559    fn get_node(&self, index: NodeIndex) -> GraphResult<&T> {
560        if index.index() >= self.nodes.len() {
561            return Err(GraphError::NodeNotFound { index: index.index() });
562        }
563        let slot = &self.nodes[index.index()];
564        if !slot.is_occupied() {
565            return Err(GraphError::NodeNotFound { index: index.index() });
566        }
567        if slot.generation != index.generation() {
568            return Err(GraphError::NodeDeleted {
569                index: index.index(),
570                provided: index.generation(),
571                current: slot.generation,
572            });
573        }
574        slot.data().ok_or(GraphError::NodeNotFound { index: index.index() })
575    }
576
577    #[inline]
578    fn get_edge(&self, index: EdgeIndex) -> GraphResult<&E> {
579        if index.index() >= self.edges.len() {
580            return Err(GraphError::EdgeNotFound { index: index.index() });
581        }
582        let edge = &self.edges[index.index()];
583        if !edge.is_occupied() {
584            return Err(GraphError::EdgeNotFound { index: index.index() });
585        }
586        if edge.generation != index.generation() {
587            return Err(GraphError::EdgeDeleted {
588                index: index.index(),
589                provided: index.generation(),
590                current: edge.generation,
591            });
592        }
593        edge.data().ok_or(GraphError::EdgeNotFound { index: index.index() })
594    }
595
596    #[inline]
597    fn edge_endpoints(&self, index: EdgeIndex) -> GraphResult<(NodeIndex, NodeIndex)> {
598        if index.index() >= self.edges.len() {
599            return Err(GraphError::EdgeNotFound { index: index.index() });
600        }
601        let edge = &self.edges[index.index()];
602        if !edge.is_occupied() {
603            return Err(GraphError::EdgeNotFound { index: index.index() });
604        }
605        if edge.generation != index.generation() {
606            return Err(GraphError::EdgeDeleted {
607                index: index.index(),
608                provided: index.generation(),
609                current: edge.generation,
610            });
611        }
612        Ok((edge.source, edge.target))
613    }
614
615    /// 获取节点的邻居迭代器
616    ///
617    /// # 快照语义
618    ///
619    /// 迭代器在**创建时**捕获目标节点的邻居快照：
620    /// - 返回的迭代器包含创建时的所有有效邻居
621    /// - 迭代期间图的修改不会影响迭代器返回的内容
622    /// - 如果邻居节点在迭代期间被删除，该节点会被跳过
623    ///
624    /// # 推荐用法
625    ///
626    /// ```
627    /// # use god_gragh::prelude::*;
628    /// # let mut graph = GraphBuilder::directed()
629    /// #     .with_nodes(vec![1, 2, 3])
630    /// #     .with_edges(vec![(0, 1, 1.0), (0, 2, 1.0)])
631    /// #     .build().unwrap();
632    /// # let node = graph.nodes().next().unwrap().index();
633    /// // 安全：迭代器持有快照，迭代期间可以修改图
634    /// for neighbor in graph.neighbors(node) {
635    ///     println!("{:?}", graph[neighbor]);
636    /// }
637    /// ```
638    #[inline]
639    fn neighbors(&self, node: NodeIndex) -> impl Iterator<Item = NodeIndex> {
640        let node_index = node.index();
641        // 在创建时捕获邻居快照（包含 generation 信息）
642        let snapshot: Vec<(usize, u32)> = self.csr
643            .neighbors_snapshot(node_index)
644            .into_iter()
645            .map(|(target_idx, _edge_idx)| {
646                let generation = self.nodes.get(target_idx).map(|n| n.generation).unwrap_or(0);
647                (target_idx, generation)
648            })
649            .collect();
650        NeighborsIter::new(snapshot)
651    }
652
653    /// 获取节点的关联边迭代器
654    ///
655    /// # 快照语义
656    ///
657    /// 迭代器在**创建时**捕获关联边的快照：
658    /// - 返回的迭代器包含创建时的所有有效边
659    /// - 迭代期间图的修改不会影响迭代器返回的内容
660    /// - 如果边在迭代期间被删除，该边会被跳过
661    ///
662    /// # 推荐用法
663    ///
664    /// ```
665    /// # use god_gragh::prelude::*;
666    /// # let mut graph = GraphBuilder::directed()
667    /// #     .with_nodes(vec![1, 2, 3])
668    /// #     .with_edges(vec![(0, 1, 1.0), (0, 2, 1.0)])
669    /// #     .build().unwrap();
670    /// # let node = graph.nodes().next().unwrap().index();
671    /// // 安全：迭代器持有快照，迭代期间可以修改图
672    /// for edge_idx in graph.incident_edges(node) {
673    ///     println!("{:?}", graph.get_edge(edge_idx).unwrap());
674    /// }
675    /// ```
676    #[inline]
677    fn incident_edges(&self, node: NodeIndex) -> impl Iterator<Item = EdgeIndex> {
678        let node_index = node.index();
679        // 在创建时捕获边索引快照（包含 generation 信息）
680        let snapshot: Vec<(usize, u32)> = self.csr
681            .edge_indices_snapshot(node_index)
682            .into_iter()
683            .map(|edge_idx| {
684                let generation = self.edges.get(edge_idx).map(|e| e.generation).unwrap_or(0);
685                (edge_idx, generation)
686            })
687            .collect();
688        IncidentEdgesIter::new(snapshot)
689    }
690
691    #[inline]
692    fn has_edge(&self, from: NodeIndex, to: NodeIndex) -> bool {
693        self.csr.has_edge(from.index(), to.index())
694    }
695
696    #[inline]
697    fn out_degree(&self, node: NodeIndex) -> GraphResult<usize> {
698        if !self.contains_node(node) {
699            return Err(GraphError::NodeNotFound { index: node.index() });
700        }
701        Ok(self.csr.degree(node.index()))
702    }
703
704    #[inline]
705    fn in_degree(&self, node: NodeIndex) -> GraphResult<usize> {
706        if !self.contains_node(node) {
707            return Err(GraphError::NodeNotFound { index: node.index() });
708        }
709        Ok(self.csr.in_degree(node.index()))
710    }
711
712    #[inline]
713    fn degree(&self, node: NodeIndex) -> GraphResult<usize> {
714        let out_deg = self.out_degree(node)?;
715        let in_deg = self.in_degree(node)?;
716        Ok(out_deg + in_deg)
717    }
718
719    #[inline]
720    fn nodes(&self) -> impl Iterator<Item = NodeRef<'_, T>> {
721        self.nodes
722            .iter()
723            .enumerate()
724            .filter_map(|(idx, slot)| {
725                if slot.is_occupied() {
726                    Some(NodeRef::new(
727                        NodeIndex::new(idx, slot.generation),
728                        slot.data()?,
729                    ))
730                } else {
731                    None
732                }
733            })
734    }
735
736    #[inline]
737    fn edges(&self) -> impl Iterator<Item = EdgeRef<'_, E>> {
738        self.edges
739            .iter()
740            .enumerate()
741            .filter_map(|(idx, edge)| {
742                if edge.is_occupied() {
743                    Some(EdgeRef::new(
744                        EdgeIndex::new(idx, edge.generation),
745                        edge.source,
746                        edge.target,
747                        edge.data()?,
748                    ))
749                } else {
750                    None
751                }
752            })
753    }
754}
755
756impl<T, E> GraphOps for Graph<T, E> {
757    #[inline]
758    fn add_node(&mut self, data: T) -> GraphResult<NodeIndex> {
759        let (index, generation) = if let Some(free_idx) = self.free_nodes.pop() {
760            let slot = &mut self.nodes[free_idx];
761            let new_generation = slot.generation.wrapping_add(1);
762            *slot = NodeSlot::new(new_generation, data);
763            (free_idx, new_generation)
764        } else {
765            let index = self.nodes.len();
766            let generation = 1u32;
767            self.nodes.push(NodeSlot::new(generation, data));
768            (index, generation)
769        };
770
771        self.node_count += 1;
772        self.csr.ensure_capacity(index);
773        Ok(NodeIndex::new(index, generation))
774    }
775
776    #[inline]
777    fn remove_node(&mut self, index: NodeIndex) -> GraphResult<T> {
778        if index.index() >= self.nodes.len() {
779            return Err(GraphError::NodeNotFound { index: index.index() });
780        }
781
782        let slot = &mut self.nodes[index.index()];
783        if !slot.is_occupied() {
784            return Err(GraphError::NodeNotFound { index: index.index() });
785        }
786        if slot.generation != index.generation() {
787            return Err(GraphError::NodeDeleted {
788                index: index.index(),
789                provided: index.generation(),
790                current: slot.generation,
791            });
792        }
793
794        // 删除出边
795        let edge_indices: Vec<usize> = self.csr.edge_indices_iter(index.index()).collect();
796        for edge_idx in edge_indices {
797            if edge_idx < self.edges.len() {
798                let edge = &self.edges[edge_idx];
799                if edge.is_occupied() {
800                    self.csr.mark_edge_deleted(index.index(), edge.target.index());
801                    let edge_slot = &mut self.edges[edge_idx];
802                    edge_slot.data = None;
803                    self.edge_count -= 1;
804                    self.free_edges.push(edge_idx);
805                }
806            }
807        }
808
809        // 删除入边
810        let incoming: Vec<usize> = self.csr.reverse_edge_indices_iter(index.index()).collect();
811        for edge_idx in incoming {
812            if edge_idx < self.edges.len() {
813                let edge = &self.edges[edge_idx];
814                if edge.is_occupied() {
815                    self.csr.mark_edge_deleted(edge.source.index(), index.index());
816                    let edge_slot = &mut self.edges[edge_idx];
817                    edge_slot.data = None;
818                    self.edge_count -= 1;
819                    self.free_edges.push(edge_idx);
820                }
821            }
822        }
823
824        self.csr.compact();
825
826        let data = slot.data.take().ok_or(GraphError::NodeNotFound { index: index.index() })?;
827        self.node_count -= 1;
828        self.free_nodes.push(index.index());
829
830        Ok(data)
831    }
832
833    #[inline]
834    fn add_edge(&mut self, from: NodeIndex, to: NodeIndex, data: E) -> GraphResult<EdgeIndex> {
835        if !self.contains_node(from) {
836            return Err(GraphError::NodeNotFound { index: from.index() });
837        }
838        if !self.contains_node(to) {
839            return Err(GraphError::NodeNotFound { index: to.index() });
840        }
841
842        let (index, generation) = if let Some(free_idx) = self.free_edges.pop() {
843            let edge = &mut self.edges[free_idx];
844            let new_generation = edge.generation.wrapping_add(1);
845            *edge = EdgeStorage::new(from, to, data, new_generation);
846            (free_idx, new_generation)
847        } else {
848            let index = self.edges.len();
849            let generation = 1u32;
850            self.edges.push(EdgeStorage::new(from, to, data, generation));
851            (index, generation)
852        };
853
854        self.edge_count += 1;
855        self.csr.add_edge(from.index(), to.index(), index);
856        Ok(EdgeIndex::new(index, generation))
857    }
858
859    #[inline]
860    fn remove_edge(&mut self, index: EdgeIndex) -> GraphResult<E> {
861        if index.index() >= self.edges.len() {
862            return Err(GraphError::EdgeNotFound { index: index.index() });
863        }
864
865        let edge = &mut self.edges[index.index()];
866        if !edge.is_occupied() {
867            return Err(GraphError::EdgeNotFound { index: index.index() });
868        }
869        if edge.generation != index.generation() {
870            return Err(GraphError::EdgeDeleted {
871                index: index.index(),
872                provided: index.generation(),
873                current: edge.generation,
874            });
875        }
876
877        let source_index = edge.source.index();
878        let target_index = edge.target.index();
879        self.csr.mark_edge_deleted(source_index, target_index);
880
881        let data = edge.data.take().ok_or(GraphError::EdgeNotFound { index: index.index() })?;
882        self.edge_count -= 1;
883        self.free_edges.push(index.index());
884        self.csr.compact();
885
886        Ok(data)
887    }
888
889    #[inline]
890    fn update_node(&mut self, index: NodeIndex, data: T) -> GraphResult<T> {
891        if index.index() >= self.nodes.len() {
892            return Err(GraphError::NodeNotFound { index: index.index() });
893        }
894
895        let slot = &mut self.nodes[index.index()];
896        if !slot.is_occupied() {
897            return Err(GraphError::NodeNotFound { index: index.index() });
898        }
899        if slot.generation != index.generation() {
900            return Err(GraphError::NodeDeleted {
901                index: index.index(),
902                provided: index.generation(),
903                current: slot.generation,
904            });
905        }
906
907        let old_data = slot.data.replace(data);
908        old_data.ok_or(GraphError::NodeNotFound { index: index.index() })
909    }
910
911    #[inline]
912    fn update_edge(&mut self, index: EdgeIndex, data: E) -> GraphResult<E> {
913        if index.index() >= self.edges.len() {
914            return Err(GraphError::EdgeNotFound { index: index.index() });
915        }
916
917        let edge = &mut self.edges[index.index()];
918        if !edge.is_occupied() {
919            return Err(GraphError::EdgeNotFound { index: index.index() });
920        }
921        if edge.generation != index.generation() {
922            return Err(GraphError::EdgeDeleted {
923                index: index.index(),
924                provided: index.generation(),
925                current: edge.generation,
926            });
927        }
928
929        let old_data = edge.data.replace(data);
930        old_data.ok_or(GraphError::EdgeNotFound { index: index.index() })
931    }
932
933    #[inline]
934    fn reserve(&mut self, additional_nodes: usize, additional_edges: usize) {
935        self.nodes.reserve(additional_nodes);
936        self.edges.reserve(additional_edges);
937        self.csr.reserve(additional_nodes, additional_edges);
938    }
939
940    #[inline]
941    fn clear(&mut self) {
942        Graph::clear(self);
943    }
944}
945
946impl<T, E> core::ops::Index<NodeIndex> for Graph<T, E> {
947    type Output = T;
948
949    #[inline]
950    fn index(&self, index: NodeIndex) -> &Self::Output {
951        self.get_node(index).expect("节点索引无效")
952    }
953}
954
955/// # Safety
956///
957/// 此实现使用 `panic!` 而非 `Result`，因为 `IndexMut` trait 不允许返回 `Result`。
958/// 对于需要安全访问的场景，请使用 `get_node_mut()` 方法。
959///
960/// # Panics
961///
962/// Panics if:
963/// - 节点索引超出范围 (`index.index() >= self.nodes.len()`)
964/// - 节点已被删除 (`slot.is_occupied() == false`)
965/// - Generation 不匹配，索引已失效
966///
967/// # 示例
968///
969/// ```rust,should_panic
970/// use god_gragh::graph::{Graph, traits::GraphOps};
971///
972/// let mut graph = Graph::<i32, f64>::directed();
973/// let node = graph.add_node(42).unwrap();
974/// graph.remove_node(node).unwrap();
975///
976/// // 这将 panic，因为节点已被删除
977/// graph[node] = 100;
978/// ```
979impl<T, E> core::ops::IndexMut<NodeIndex> for Graph<T, E> {
980    #[inline]
981    fn index_mut(&mut self, index: NodeIndex) -> &mut Self::Output {
982        if index.index() >= self.nodes.len() {
983            panic!("节点索引无效：index={}", index.index());
984        }
985        let slot = &mut self.nodes[index.index()];
986        if !slot.is_occupied() {
987            panic!("节点索引无效：节点不存在");
988        }
989        if slot.generation != index.generation() {
990            panic!("节点索引已失效：generation 不匹配");
991        }
992        slot.data.as_mut().expect("节点数据为空")
993    }
994}
995
996#[cfg(test)]
997mod tests {
998    use super::*;
999
1000    #[test]
1001    fn test_graph_creation() {
1002        let graph = Graph::<i32, f64>::directed();
1003        assert_eq!(graph.node_count(), 0);
1004        assert_eq!(graph.edge_count(), 0);
1005        assert!(graph.is_empty());
1006    }
1007
1008    #[test]
1009    fn test_add_node() {
1010        let mut graph = Graph::<String, f64>::directed();
1011        let idx = graph.add_node("test".to_string()).unwrap();
1012        assert_eq!(graph.node_count(), 1);
1013        assert!(graph.contains_node(idx));
1014        assert_eq!(graph[idx], "test");
1015    }
1016
1017    #[test]
1018    fn test_index_mut() {
1019        let mut graph = Graph::<String, f64>::directed();
1020        let idx = graph.add_node("initial".to_string()).unwrap();
1021        
1022        // 使用 IndexMut 修改节点数据
1023        graph[idx] = "modified".to_string();
1024        assert_eq!(graph[idx], "modified");
1025        
1026        // 修改多个节点
1027        let idx2 = graph.add_node("second".to_string()).unwrap();
1028        graph[idx2] = "second_modified".to_string();
1029        assert_eq!(graph[idx2], "second_modified");
1030    }
1031
1032    #[test]
1033    fn test_remove_node() {
1034        let mut graph = Graph::<i32, f64>::directed();
1035        let idx = graph.add_node(42).unwrap();
1036        assert!(graph.contains_node(idx));
1037
1038        let data = graph.remove_node(idx).unwrap();
1039        assert_eq!(data, 42);
1040        assert_eq!(graph.node_count(), 0);
1041        assert!(!graph.contains_node(idx));
1042    }
1043
1044    #[test]
1045    fn test_add_edge() {
1046        let mut graph = Graph::<i32, f64>::directed();
1047        let a = graph.add_node(1).unwrap();
1048        let b = graph.add_node(2).unwrap();
1049        let edge = graph.add_edge(a, b, std::f64::consts::PI).unwrap();
1050
1051        assert_eq!(graph.edge_count(), 1);
1052        assert!(graph.contains_edge(edge));
1053        assert_eq!(*graph.get_edge(edge).unwrap(), std::f64::consts::PI);
1054    }
1055
1056    #[test]
1057    fn test_node_reuse() {
1058        let mut graph = Graph::<i32, f64>::directed();
1059        let idx1 = graph.add_node(1).unwrap();
1060        let _ = graph.remove_node(idx1).unwrap();
1061        let idx2 = graph.add_node(2).unwrap();
1062
1063        assert_eq!(idx2.index(), idx1.index());
1064        assert!(idx2.generation() > idx1.generation());
1065    }
1066
1067    #[test]
1068    fn test_neighbors() {
1069        let mut graph = Graph::<i32, f64>::directed();
1070        let a = graph.add_node(1).unwrap();
1071        let b = graph.add_node(2).unwrap();
1072        let c = graph.add_node(3).unwrap();
1073        graph.add_edge(a, b, 1.0).unwrap();
1074        graph.add_edge(a, c, 2.0).unwrap();
1075
1076        let neighbors: Vec<_> = graph.neighbors(a).collect();
1077        assert_eq!(neighbors.len(), 2);
1078    }
1079
1080    #[test]
1081    fn test_has_edge() {
1082        let mut graph = Graph::<i32, f64>::directed();
1083        let a = graph.add_node(1).unwrap();
1084        let b = graph.add_node(2).unwrap();
1085        graph.add_edge(a, b, 1.0).unwrap();
1086
1087        assert!(graph.has_edge(a, b));
1088        assert!(!graph.has_edge(b, a));
1089    }
1090}
god_gragh/graph/impl_.rs

god_gragh/graph/
impl_.rs
