god_graph/graph/
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::{Deserialize, Serialize};
23
24use crate::edge::{EdgeIndex, EdgeRef, EdgeStorage};
25use crate::errors::{GraphError, GraphResult};
26use crate::graph::traits::{GraphBase, GraphOps, GraphQuery};
27use crate::node::{NodeIndex, NodeRef, NodeSlot};
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                    // SAFETY: `_mm_prefetch` is a CPU hint instruction that doesn't modify memory.
162                    // Pointers are derived from Vec which guarantees validity.
163                    // Bounds are checked before this block (prefetch_pos < len).
164                    unsafe {
165                        _mm_prefetch(
166                            self.bucket.neighbors.as_ptr().add(prefetch_pos) as *const i8,
167                            _MM_HINT_T0,
168                        );
169                        _mm_prefetch(
170                            self.bucket.edge_indices.as_ptr().add(prefetch_pos) as *const i8,
171                            _MM_HINT_T0,
172                        );
173                    }
174                }
175            }
176
177            let pos = self.pos;
178            self.pos += 1;
179            if !self.bucket.is_deleted(pos) {
180                return Some((self.bucket.neighbors[pos], self.bucket.edge_indices[pos]));
181            }
182        }
183        None
184    }
185}
186
187/// 邻居迭代器（快照语义）
188///
189/// 在创建时捕获目标节点的 generation，迭代期间只返回该快照中的邻居
190pub struct NeighborsIter {
191    /// 原始邻居数据快照（target_idx, generation）
192    snapshot: std::vec::IntoIter<(usize, u32)>,
193}
194
195impl NeighborsIter {
196    pub(crate) fn new(snapshot: Vec<(usize, u32)>) -> Self {
197        Self {
198            snapshot: snapshot.into_iter(),
199        }
200    }
201}
202
203impl Iterator for NeighborsIter {
204    type Item = NodeIndex;
205
206    #[inline]
207    fn next(&mut self) -> Option<Self::Item> {
208        self.snapshot
209            .next()
210            .map(|(idx, generation)| NodeIndex::new(idx, generation))
211    }
212}
213
214/// 关联边迭代器（快照语义）
215///
216/// 在创建时捕获边的 generation，迭代期间只返回该快照中的边
217pub struct IncidentEdgesIter {
218    /// 原始边数据快照（edge_idx, generation）
219    snapshot: std::vec::IntoIter<(usize, u32)>,
220}
221
222impl IncidentEdgesIter {
223    pub(crate) fn new(snapshot: Vec<(usize, u32)>) -> Self {
224        Self {
225            snapshot: snapshot.into_iter(),
226        }
227    }
228}
229
230impl Iterator for IncidentEdgesIter {
231    type Item = EdgeIndex;
232
233    #[inline]
234    fn next(&mut self) -> Option<Self::Item> {
235        self.snapshot
236            .next()
237            .map(|(idx, generation)| EdgeIndex::new(idx, generation))
238    }
239}
240
241/// 邻接桶存储：桶式邻接表格式
242///
243/// ## 命名说明
244///
245/// 历史原因：早期代码使用 `CsrStorage` 命名，但实际实现是**桶式邻接表**（Bucket Adjacency List）。
246/// 传统 CSR（压缩稀疏行）格式使用 `row_offsets + col_indices`，不支持 O(1) 增量更新。
247/// 本实现使用 `Vec<AdjBucket>`，每个 bucket 含独立 `Vec`，支持 O(1) 插入和惰性删除。
248///
249/// 为保持 API 稳定性，保留 `CsrStorage` 别名，但推荐在新代码中使用 `AdjacencyBuckets`。
250#[derive(Clone, Debug)]
251#[cfg_attr(feature = "serde", derive(Serialize, Deserialize))]
252pub(crate) struct AdjacencyBuckets {
253    buckets: Vec<AdjBucket>,
254    reverse_buckets: Vec<AdjBucket>,
255    num_nodes: usize,
256    needs_compact: bool,
257}
258
259/// 向后兼容别名
260///
261/// 历史原因：早期代码使用 `CsrStorage` 命名，但实际实现是桶式邻接表。
262/// 为保持 API 稳定性保留此别名，但推荐在新代码中使用 `AdjacencyBuckets`。
263#[deprecated(
264    since = "0.3.1",
265    note = "使用 AdjacencyBuckets 代替，命名更准确反映实现"
266)]
267#[allow(dead_code)]
268pub(crate) type CsrStorage = AdjacencyBuckets;
269
270impl AdjacencyBuckets {
271    pub(crate) fn new() -> Self {
272        let this = Self {
273            buckets: Vec::new(),
274            reverse_buckets: Vec::new(),
275            num_nodes: 0,
276            needs_compact: false,
277        };
278        // 验证空 Vec 的对齐（空指针 0 % 64 = 0，总是成立，但保留断言用于文档说明）
279        debug_assert_eq!(
280            this.buckets.as_ptr() as usize % 64,
281            0,
282            "buckets 初始对齐失败"
283        );
284        debug_assert_eq!(
285            this.reverse_buckets.as_ptr() as usize % 64,
286            0,
287            "reverse_buckets 初始对齐失败"
288        );
289        this
290    }
291
292    /// 验证 buckets 的 64 字节对齐
293    ///
294    /// 使用运行时断言确保 Vec<AdjBucket> 的指针是 64 字节对齐的。
295    /// AdjBucket 使用 #[repr(align(64))]，但需要验证实际分配的对齐。
296    ///
297    /// ## Panics
298    ///
299    /// 如果对齐不正确会 panic，并输出详细的调试信息。
300    #[inline]
301    pub(crate) fn assert_aligned(&self) {
302        let buckets_ptr = self.buckets.as_ptr() as usize;
303        let reverse_ptr = self.reverse_buckets.as_ptr() as usize;
304        assert_eq!(
305            buckets_ptr % 64,
306            0,
307            "AdjacencyBuckets: buckets 未 64 字节对齐 (ptr={:#x}, mod={})",
308            buckets_ptr,
309            buckets_ptr % 64
310        );
311        assert_eq!(
312            reverse_ptr % 64,
313            0,
314            "AdjacencyBuckets: reverse_buckets 未 64 字节对齐 (ptr={:#x}, mod={})",
315            reverse_ptr,
316            reverse_ptr % 64
317        );
318    }
319
320    pub(crate) fn reserve(&mut self, nodes: usize, _edges: usize) {
321        self.buckets.reserve(nodes);
322        self.reverse_buckets.reserve(nodes);
323        // 验证分配后的对齐
324        self.assert_aligned();
325    }
326
327    fn ensure_capacity(&mut self, node_index: usize) {
328        while self.buckets.len() <= node_index {
329            self.buckets.push(AdjBucket::new());
330        }
331        while self.reverse_buckets.len() <= node_index {
332            self.reverse_buckets.push(AdjBucket::new());
333        }
334        self.num_nodes = self.buckets.len();
335        // 验证扩容后的对齐
336        self.assert_aligned();
337    }
338
339    /// O(1) 添加边
340    pub(crate) fn add_edge(&mut self, node_index: usize, target_index: usize, edge_index: usize) {
341        self.ensure_capacity(node_index.max(target_index));
342        self.buckets[node_index].push(target_index, edge_index);
343        self.reverse_buckets[target_index].push(node_index, edge_index);
344    }
345
346    /// 标记边为已删除
347    pub(crate) fn mark_edge_deleted(&mut self, node_index: usize, target_index: usize) {
348        if let Some(pos) = self.buckets[node_index].find(target_index) {
349            self.buckets[node_index].mark_deleted(pos);
350            self.needs_compact = true;
351        }
352        if let Some(pos) = self.reverse_buckets[target_index].find(node_index) {
353            self.reverse_buckets[target_index].mark_deleted(pos);
354        }
355    }
356
357    pub(crate) fn compact(&mut self) {
358        if !self.needs_compact {
359            return;
360        }
361        for bucket in &mut self.buckets {
362            bucket.compact();
363        }
364        for bucket in &mut self.reverse_buckets {
365            bucket.compact();
366        }
367        self.needs_compact = false;
368    }
369
370    #[allow(dead_code)]
371    pub(crate) fn neighbors_raw(&self, node_index: usize) -> impl Iterator<Item = usize> + '_ {
372        self.buckets
373            .get(node_index)
374            .into_iter()
375            .flat_map(|b| b.iter())
376            .map(move |(target_idx, _)| target_idx)
377    }
378
379    #[allow(dead_code)]
380    pub(crate) fn reverse_neighbors_raw(
381        &self,
382        node_index: usize,
383    ) -> impl Iterator<Item = usize> + '_ {
384        self.reverse_buckets
385            .get(node_index)
386            .into_iter()
387            .flat_map(|b| b.iter())
388            .map(move |(src_idx, _)| src_idx)
389    }
390
391    pub(crate) fn edge_indices_iter(&self, node_index: usize) -> impl Iterator<Item = usize> + '_ {
392        self.buckets
393            .get(node_index)
394            .into_iter()
395            .flat_map(|b| b.iter().map(|(_, ei)| ei))
396    }
397
398    /// 获取边索引的快照（用于快照语义迭代器）
399    pub(crate) fn edge_indices_snapshot(&self, node_index: usize) -> Vec<usize> {
400        self.edge_indices_iter(node_index).collect()
401    }
402
403    /// 获取邻居的快照（用于快照语义迭代器）
404    pub(crate) fn neighbors_snapshot(&self, node_index: usize) -> Vec<(usize, usize)> {
405        self.buckets
406            .get(node_index)
407            .map(|b| b.snapshot())
408            .unwrap_or_default()
409    }
410
411    pub(crate) fn has_edge(&self, node_index: usize, target_index: usize) -> bool {
412        self.buckets
413            .get(node_index)
414            .and_then(|b| b.find(target_index))
415            .is_some()
416    }
417
418    pub(crate) fn degree(&self, node_index: usize) -> usize {
419        self.buckets.get(node_index).map(|b| b.len()).unwrap_or(0)
420    }
421
422    pub(crate) fn in_degree(&self, node_index: usize) -> usize {
423        self.reverse_buckets
424            .get(node_index)
425            .map(|b| b.len())
426            .unwrap_or(0)
427    }
428
429    pub(crate) fn reverse_edge_indices_iter(
430        &self,
431        node_index: usize,
432    ) -> impl Iterator<Item = usize> + '_ {
433        self.reverse_buckets
434            .get(node_index)
435            .into_iter()
436            .flat_map(|b| b.iter().map(|(_, ei)| ei))
437    }
438
439    pub(crate) fn clear(&mut self) {
440        self.buckets.clear();
441        self.reverse_buckets.clear();
442        self.num_nodes = 0;
443        self.needs_compact = false;
444    }
445
446    #[allow(dead_code)]
447    pub(crate) fn num_nodes(&self) -> usize {
448        self.num_nodes
449    }
450}
451
452impl Default for AdjacencyBuckets {
453    fn default() -> Self {
454        Self::new()
455    }
456}
457
458/// 图结构主实现
459/// 使用缓存行对齐优化，减少 false sharing
460#[derive(Clone)]
461#[cfg_attr(feature = "serde", derive(Serialize, Deserialize))]
462#[cfg_attr(
463    feature = "serde",
464    serde(bound(
465        serialize = "T: Serialize, E: Serialize",
466        deserialize = "T: Deserialize<'de>, E: Deserialize<'de>"
467    ))
468)]
469pub struct Graph<T, E> {
470    nodes: Vec<NodeSlot<T>>,
471    edges: Vec<EdgeStorage<E>>,
472    csr: AdjacencyBuckets,
473    node_count: usize,
474    edge_count: usize,
475    free_nodes: Vec<usize>,
476    free_edges: Vec<usize>,
477}
478
479impl<T, E> fmt::Debug for Graph<T, E>
480where
481    T: fmt::Debug,
482    E: fmt::Debug,
483{
484    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
485        f.debug_struct("Graph")
486            .field("node_count", &self.node_count)
487            .field("edge_count", &self.edge_count)
488            .finish()
489    }
490}
491
492impl<T, E> Graph<T, E> {
493    /// 创建新的有向图
494    pub fn directed() -> Self {
495        Self {
496            nodes: Vec::new(),
497            edges: Vec::new(),
498            csr: AdjacencyBuckets::new(),
499            node_count: 0,
500            edge_count: 0,
501            free_nodes: Vec::new(),
502            free_edges: Vec::new(),
503        }
504    }
505
506    /// 创建新的无向图
507    pub fn undirected() -> Self {
508        Self::directed()
509    }
510
511    /// 创建带预分配容量的有向图
512    pub fn with_capacity(nodes: usize, edges: usize) -> Self {
513        let mut graph = Self::directed();
514        graph.reserve(nodes, edges);
515        graph
516    }
517
518    /// 检查图是否为空
519    #[inline]
520    pub fn is_empty(&self) -> bool {
521        self.node_count == 0
522    }
523
524    /// 清空图
525    pub fn clear(&mut self) {
526        self.nodes.clear();
527        self.edges.clear();
528        self.csr.clear();
529        self.node_count = 0;
530        self.edge_count = 0;
531        self.free_nodes.clear();
532        self.free_edges.clear();
533    }
534
535    /// 通过节点索引获取边数据
536    pub fn get_edge_by_nodes(&self, from: NodeIndex, to: NodeIndex) -> GraphResult<&E> {
537        for edge_idx in self.csr.edge_indices_iter(from.index()) {
538            if edge_idx < self.edges.len() {
539                let edge = &self.edges[edge_idx];
540                if edge.is_occupied() && edge.target == to {
541                    return edge
542                        .data()
543                        .ok_or(GraphError::EdgeNotFound { index: edge_idx });
544                }
545            }
546        }
547        Err(GraphError::EdgeNotFound { index: usize::MAX })
548    }
549}
550
551impl<T, E> GraphBase for Graph<T, E> {
552    type NodeData = T;
553    type EdgeData = E;
554
555    #[inline]
556    fn node_count(&self) -> usize {
557        self.node_count
558    }
559
560    #[inline]
561    fn edge_count(&self) -> usize {
562        self.edge_count
563    }
564
565    #[inline]
566    fn contains_node(&self, index: NodeIndex) -> bool {
567        if index.index() >= self.nodes.len() {
568            return false;
569        }
570        let slot = &self.nodes[index.index()];
571        slot.is_occupied() && slot.generation == index.generation()
572    }
573
574    #[inline]
575    fn contains_edge(&self, index: EdgeIndex) -> bool {
576        if index.index() >= self.edges.len() {
577            return false;
578        }
579        let edge = &self.edges[index.index()];
580        edge.is_occupied() && edge.generation == index.generation()
581    }
582}
583
584impl<T, E> GraphQuery for Graph<T, E> {
585    #[inline]
586    fn get_node(&self, index: NodeIndex) -> GraphResult<&T> {
587        if index.index() >= self.nodes.len() {
588            return Err(GraphError::NodeNotFound {
589                index: index.index(),
590            });
591        }
592        let slot = &self.nodes[index.index()];
593        if !slot.is_occupied() {
594            return Err(GraphError::NodeNotFound {
595                index: index.index(),
596            });
597        }
598        if slot.generation != index.generation() {
599            return Err(GraphError::NodeDeleted {
600                index: index.index(),
601                provided: index.generation(),
602                current: slot.generation,
603            });
604        }
605        slot.data().ok_or(GraphError::NodeNotFound {
606            index: index.index(),
607        })
608    }
609
610    #[inline]
611    fn get_edge(&self, index: EdgeIndex) -> GraphResult<&E> {
612        if index.index() >= self.edges.len() {
613            return Err(GraphError::EdgeNotFound {
614                index: index.index(),
615            });
616        }
617        let edge = &self.edges[index.index()];
618        if !edge.is_occupied() {
619            return Err(GraphError::EdgeNotFound {
620                index: index.index(),
621            });
622        }
623        if edge.generation != index.generation() {
624            return Err(GraphError::EdgeDeleted {
625                index: index.index(),
626                provided: index.generation(),
627                current: edge.generation,
628            });
629        }
630        edge.data().ok_or(GraphError::EdgeNotFound {
631            index: index.index(),
632        })
633    }
634
635    #[inline]
636    fn edge_endpoints(&self, index: EdgeIndex) -> GraphResult<(NodeIndex, NodeIndex)> {
637        if index.index() >= self.edges.len() {
638            return Err(GraphError::EdgeNotFound {
639                index: index.index(),
640            });
641        }
642        let edge = &self.edges[index.index()];
643        if !edge.is_occupied() {
644            return Err(GraphError::EdgeNotFound {
645                index: index.index(),
646            });
647        }
648        if edge.generation != index.generation() {
649            return Err(GraphError::EdgeDeleted {
650                index: index.index(),
651                provided: index.generation(),
652                current: edge.generation,
653            });
654        }
655        Ok((edge.source, edge.target))
656    }
657
658    /// 获取节点的邻居迭代器
659    ///
660    /// # 快照语义
661    ///
662    /// 迭代器在**创建时**捕获目标节点的邻居快照：
663    /// - 返回的迭代器包含创建时的所有有效邻居
664    /// - 迭代期间图的修改不会影响迭代器返回的内容
665    /// - 如果邻居节点在迭代期间被删除，该节点会被跳过
666    ///
667    /// # 推荐用法
668    ///
669    /// ```
670    /// # use god_gragh::prelude::*;
671    /// # let mut graph = GraphBuilder::directed()
672    /// #     .with_nodes(vec![1, 2, 3])
673    /// #     .with_edges(vec![(0, 1, 1.0), (0, 2, 1.0)])
674    /// #     .build().unwrap();
675    /// # let node = graph.nodes().next().unwrap().index();
676    /// // 安全：迭代器持有快照，迭代期间可以修改图
677    /// for neighbor in graph.neighbors(node) {
678    ///     println!("{:?}", graph[neighbor]);
679    /// }
680    /// ```
681    #[inline]
682    fn neighbors(&self, node: NodeIndex) -> impl Iterator<Item = NodeIndex> {
683        let node_index = node.index();
684        // 在创建时捕获邻居快照（包含 generation 信息）
685        let snapshot: Vec<(usize, u32)> = self
686            .csr
687            .neighbors_snapshot(node_index)
688            .into_iter()
689            .map(|(target_idx, _edge_idx)| {
690                let generation = self
691                    .nodes
692                    .get(target_idx)
693                    .map(|n| n.generation)
694                    .unwrap_or(0);
695                (target_idx, generation)
696            })
697            .collect();
698        NeighborsIter::new(snapshot)
699    }
700
701    /// 获取节点的关联边迭代器
702    ///
703    /// # 快照语义
704    ///
705    /// 迭代器在**创建时**捕获关联边的快照：
706    /// - 返回的迭代器包含创建时的所有有效边
707    /// - 迭代期间图的修改不会影响迭代器返回的内容
708    /// - 如果边在迭代期间被删除，该边会被跳过
709    ///
710    /// # 推荐用法
711    ///
712    /// ```
713    /// # use god_gragh::prelude::*;
714    /// # let mut graph = GraphBuilder::directed()
715    /// #     .with_nodes(vec![1, 2, 3])
716    /// #     .with_edges(vec![(0, 1, 1.0), (0, 2, 1.0)])
717    /// #     .build().unwrap();
718    /// # let node = graph.nodes().next().unwrap().index();
719    /// // 安全：迭代器持有快照，迭代期间可以修改图
720    /// for edge_idx in graph.incident_edges(node) {
721    ///     println!("{:?}", graph.get_edge(edge_idx).unwrap());
722    /// }
723    /// ```
724    #[inline]
725    fn incident_edges(&self, node: NodeIndex) -> impl Iterator<Item = EdgeIndex> {
726        let node_index = node.index();
727        // 在创建时捕获边索引快照（包含 generation 信息）
728        let snapshot: Vec<(usize, u32)> = self
729            .csr
730            .edge_indices_snapshot(node_index)
731            .into_iter()
732            .map(|edge_idx| {
733                let generation = self.edges.get(edge_idx).map(|e| e.generation).unwrap_or(0);
734                (edge_idx, generation)
735            })
736            .collect();
737        IncidentEdgesIter::new(snapshot)
738    }
739
740    #[inline]
741    fn has_edge(&self, from: NodeIndex, to: NodeIndex) -> bool {
742        self.csr.has_edge(from.index(), to.index())
743    }
744
745    #[inline]
746    fn out_degree(&self, node: NodeIndex) -> GraphResult<usize> {
747        if !self.contains_node(node) {
748            return Err(GraphError::NodeNotFound {
749                index: node.index(),
750            });
751        }
752        Ok(self.csr.degree(node.index()))
753    }
754
755    #[inline]
756    fn in_degree(&self, node: NodeIndex) -> GraphResult<usize> {
757        if !self.contains_node(node) {
758            return Err(GraphError::NodeNotFound {
759                index: node.index(),
760            });
761        }
762        Ok(self.csr.in_degree(node.index()))
763    }
764
765    #[inline]
766    fn degree(&self, node: NodeIndex) -> GraphResult<usize> {
767        let out_deg = self.out_degree(node)?;
768        let in_deg = self.in_degree(node)?;
769        Ok(out_deg + in_deg)
770    }
771
772    #[inline]
773    fn nodes(&self) -> impl Iterator<Item = NodeRef<'_, T>> {
774        self.nodes.iter().enumerate().filter_map(|(idx, slot)| {
775            if slot.is_occupied() {
776                Some(NodeRef::new(
777                    NodeIndex::new(idx, slot.generation),
778                    slot.data()?,
779                ))
780            } else {
781                None
782            }
783        })
784    }
785
786    #[inline]
787    fn edges(&self) -> impl Iterator<Item = EdgeRef<'_, E>> {
788        self.edges.iter().enumerate().filter_map(|(idx, edge)| {
789            if edge.is_occupied() {
790                Some(EdgeRef::new(
791                    EdgeIndex::new(idx, edge.generation),
792                    edge.source,
793                    edge.target,
794                    edge.data()?,
795                ))
796            } else {
797                None
798            }
799        })
800    }
801}
802
803impl<T, E> GraphOps for Graph<T, E> {
804    #[inline]
805    fn add_node(&mut self, data: T) -> GraphResult<NodeIndex> {
806        let (index, generation) = if let Some(free_idx) = self.free_nodes.pop() {
807            let slot = &mut self.nodes[free_idx];
808            let new_generation = slot.generation.wrapping_add(1);
809            *slot = NodeSlot::new(new_generation, data);
810            (free_idx, new_generation)
811        } else {
812            let index = self.nodes.len();
813            let generation = 1u32;
814            self.nodes.push(NodeSlot::new(generation, data));
815            (index, generation)
816        };
817
818        self.node_count += 1;
819        self.csr.ensure_capacity(index);
820        Ok(NodeIndex::new(index, generation))
821    }
822
823    #[inline]
824    fn remove_node(&mut self, index: NodeIndex) -> GraphResult<T> {
825        if index.index() >= self.nodes.len() {
826            return Err(GraphError::NodeNotFound {
827                index: index.index(),
828            });
829        }
830
831        let slot = &mut self.nodes[index.index()];
832        if !slot.is_occupied() {
833            return Err(GraphError::NodeNotFound {
834                index: index.index(),
835            });
836        }
837        if slot.generation != index.generation() {
838            return Err(GraphError::NodeDeleted {
839                index: index.index(),
840                provided: index.generation(),
841                current: slot.generation,
842            });
843        }
844
845        // 删除出边
846        let edge_indices: Vec<usize> = self.csr.edge_indices_iter(index.index()).collect();
847        for edge_idx in edge_indices {
848            if edge_idx < self.edges.len() {
849                let edge = &self.edges[edge_idx];
850                if edge.is_occupied() {
851                    self.csr
852                        .mark_edge_deleted(index.index(), edge.target.index());
853                    let edge_slot = &mut self.edges[edge_idx];
854                    edge_slot.data = None;
855                    self.edge_count -= 1;
856                    self.free_edges.push(edge_idx);
857                }
858            }
859        }
860
861        // 删除入边
862        let incoming: Vec<usize> = self.csr.reverse_edge_indices_iter(index.index()).collect();
863        for edge_idx in incoming {
864            if edge_idx < self.edges.len() {
865                let edge = &self.edges[edge_idx];
866                if edge.is_occupied() {
867                    self.csr
868                        .mark_edge_deleted(edge.source.index(), index.index());
869                    let edge_slot = &mut self.edges[edge_idx];
870                    edge_slot.data = None;
871                    self.edge_count -= 1;
872                    self.free_edges.push(edge_idx);
873                }
874            }
875        }
876
877        self.csr.compact();
878
879        let data = slot.data.take().ok_or(GraphError::NodeNotFound {
880            index: index.index(),
881        })?;
882        self.node_count -= 1;
883        self.free_nodes.push(index.index());
884
885        Ok(data)
886    }
887
888    #[inline]
889    fn add_edge(&mut self, from: NodeIndex, to: NodeIndex, data: E) -> GraphResult<EdgeIndex> {
890        if !self.contains_node(from) {
891            return Err(GraphError::NodeNotFound {
892                index: from.index(),
893            });
894        }
895        if !self.contains_node(to) {
896            return Err(GraphError::NodeNotFound { index: to.index() });
897        }
898
899        let (index, generation) = if let Some(free_idx) = self.free_edges.pop() {
900            let edge = &mut self.edges[free_idx];
901            let new_generation = edge.generation.wrapping_add(1);
902            *edge = EdgeStorage::new(from, to, data, new_generation);
903            (free_idx, new_generation)
904        } else {
905            let index = self.edges.len();
906            let generation = 1u32;
907            self.edges
908                .push(EdgeStorage::new(from, to, data, generation));
909            (index, generation)
910        };
911
912        self.edge_count += 1;
913        self.csr.add_edge(from.index(), to.index(), index);
914        Ok(EdgeIndex::new(index, generation))
915    }
916
917    #[inline]
918    fn remove_edge(&mut self, index: EdgeIndex) -> GraphResult<E> {
919        if index.index() >= self.edges.len() {
920            return Err(GraphError::EdgeNotFound {
921                index: index.index(),
922            });
923        }
924
925        let edge = &mut self.edges[index.index()];
926        if !edge.is_occupied() {
927            return Err(GraphError::EdgeNotFound {
928                index: index.index(),
929            });
930        }
931        if edge.generation != index.generation() {
932            return Err(GraphError::EdgeDeleted {
933                index: index.index(),
934                provided: index.generation(),
935                current: edge.generation,
936            });
937        }
938
939        let source_index = edge.source.index();
940        let target_index = edge.target.index();
941        self.csr.mark_edge_deleted(source_index, target_index);
942
943        let data = edge.data.take().ok_or(GraphError::EdgeNotFound {
944            index: index.index(),
945        })?;
946        self.edge_count -= 1;
947        self.free_edges.push(index.index());
948        self.csr.compact();
949
950        Ok(data)
951    }
952
953    #[inline]
954    fn update_node(&mut self, index: NodeIndex, data: T) -> GraphResult<T> {
955        if index.index() >= self.nodes.len() {
956            return Err(GraphError::NodeNotFound {
957                index: index.index(),
958            });
959        }
960
961        let slot = &mut self.nodes[index.index()];
962        if !slot.is_occupied() {
963            return Err(GraphError::NodeNotFound {
964                index: index.index(),
965            });
966        }
967        if slot.generation != index.generation() {
968            return Err(GraphError::NodeDeleted {
969                index: index.index(),
970                provided: index.generation(),
971                current: slot.generation,
972            });
973        }
974
975        let old_data = slot.data.replace(data);
976        old_data.ok_or(GraphError::NodeNotFound {
977            index: index.index(),
978        })
979    }
980
981    #[inline]
982    fn update_edge(&mut self, index: EdgeIndex, data: E) -> GraphResult<E> {
983        if index.index() >= self.edges.len() {
984            return Err(GraphError::EdgeNotFound {
985                index: index.index(),
986            });
987        }
988
989        let edge = &mut self.edges[index.index()];
990        if !edge.is_occupied() {
991            return Err(GraphError::EdgeNotFound {
992                index: index.index(),
993            });
994        }
995        if edge.generation != index.generation() {
996            return Err(GraphError::EdgeDeleted {
997                index: index.index(),
998                provided: index.generation(),
999                current: edge.generation,
1000            });
1001        }
1002
1003        let old_data = edge.data.replace(data);
1004        old_data.ok_or(GraphError::EdgeNotFound {
1005            index: index.index(),
1006        })
1007    }
1008
1009    #[inline]
1010    fn reserve(&mut self, additional_nodes: usize, additional_edges: usize) {
1011        self.nodes.reserve(additional_nodes);
1012        self.edges.reserve(additional_edges);
1013        self.csr.reserve(additional_nodes, additional_edges);
1014    }
1015
1016    #[inline]
1017    fn clear(&mut self) {
1018        Graph::clear(self);
1019    }
1020}
1021
1022impl<T, E> core::ops::Index<NodeIndex> for Graph<T, E> {
1023    type Output = T;
1024
1025    #[inline]
1026    fn index(&self, index: NodeIndex) -> &Self::Output {
1027        self.get_node(index).expect("节点索引无效")
1028    }
1029}
1030
1031/// # Safety
1032///
1033/// 此实现使用 `panic!` 而非 `Result`，因为 `IndexMut` trait 不允许返回 `Result`。
1034/// 对于需要安全访问的场景，请使用 `get_node_mut()` 方法。
1035///
1036/// # Panics
1037///
1038/// Panics if:
1039/// - 节点索引超出范围 (`index.index() >= self.nodes.len()`)
1040/// - 节点已被删除 (`slot.is_occupied() == false`)
1041/// - Generation 不匹配，索引已失效
1042///
1043/// # 示例
1044///
1045/// ```rust,should_panic
1046/// use god_gragh::graph::{Graph, traits::GraphOps};
1047///
1048/// let mut graph = Graph::<i32, f64>::directed();
1049/// let node = graph.add_node(42).unwrap();
1050/// graph.remove_node(node).unwrap();
1051///
1052/// // 这将 panic，因为节点已被删除
1053/// graph[node] = 100;
1054/// ```
1055impl<T, E> core::ops::IndexMut<NodeIndex> for Graph<T, E> {
1056    #[inline]
1057    fn index_mut(&mut self, index: NodeIndex) -> &mut Self::Output {
1058        if index.index() >= self.nodes.len() {
1059            panic!("节点索引无效：index={}", index.index());
1060        }
1061        let slot = &mut self.nodes[index.index()];
1062        if !slot.is_occupied() {
1063            panic!("节点索引无效：节点不存在");
1064        }
1065        if slot.generation != index.generation() {
1066            panic!("节点索引已失效：generation 不匹配");
1067        }
1068        slot.data.as_mut().expect("节点数据为空")
1069    }
1070}
1071
1072impl<T, E> core::ops::Index<EdgeIndex> for Graph<T, E> {
1073    type Output = E;
1074
1075    #[inline]
1076    fn index(&self, index: EdgeIndex) -> &Self::Output {
1077        self.get_edge(index).expect("边索引无效")
1078    }
1079}
1080
1081/// # Safety
1082///
1083/// 此实现使用 `panic!` 而非 `Result`，因为 `IndexMut` trait 不允许返回 `Result`。
1084/// 对于需要安全访问的场景，请使用边数据可变访问方法。
1085///
1086/// # Panics
1087///
1088/// Panics if:
1089/// - 边索引超出范围 (`index.index() >= self.edges.len()`)
1090/// - 边已被删除 (`edge.is_occupied() == false`)
1091/// - Generation 不匹配，索引已失效
1092///
1093/// # 示例
1094///
1095/// ```
1096/// use god_gragh::graph::Graph;
1097/// use god_gragh::graph::traits::GraphOps;
1098///
1099/// let mut graph = Graph::directed();
1100/// let a = graph.add_node(1).unwrap();
1101/// let b = graph.add_node(2).unwrap();
1102/// let edge = graph.add_edge(a, b, 42.0).unwrap();
1103///
1104/// // 使用 IndexMut 修改边数据
1105/// graph[edge] = 100.0;
1106/// assert_eq!(graph[edge], 100.0);
1107/// ```
1108impl<T, E> core::ops::IndexMut<EdgeIndex> for Graph<T, E> {
1109    #[inline]
1110    fn index_mut(&mut self, index: EdgeIndex) -> &mut Self::Output {
1111        if index.index() >= self.edges.len() {
1112            panic!("边索引无效：index={}", index.index());
1113        }
1114        let edge = &mut self.edges[index.index()];
1115        if !edge.is_occupied() {
1116            panic!("边索引无效：边不存在");
1117        }
1118        if edge.generation != index.generation() {
1119            panic!("边索引已失效：generation 不匹配");
1120        }
1121        edge.data.as_mut().expect("边数据为空")
1122    }
1123}
1124
1125#[cfg(test)]
1126mod tests {
1127    use super::*;
1128
1129    #[test]
1130    fn test_graph_creation() {
1131        let graph = Graph::<i32, f64>::directed();
1132        assert_eq!(graph.node_count(), 0);
1133        assert_eq!(graph.edge_count(), 0);
1134        assert!(graph.is_empty());
1135    }
1136
1137    #[test]
1138    fn test_add_node() {
1139        let mut graph = Graph::<String, f64>::directed();
1140        let idx = graph.add_node("test".to_string()).unwrap();
1141        assert_eq!(graph.node_count(), 1);
1142        assert!(graph.contains_node(idx));
1143        assert_eq!(graph[idx], "test");
1144    }
1145
1146    #[test]
1147    fn test_index_mut() {
1148        let mut graph = Graph::<String, f64>::directed();
1149        let idx = graph.add_node("initial".to_string()).unwrap();
1150
1151        // 使用 IndexMut 修改节点数据
1152        graph[idx] = "modified".to_string();
1153        assert_eq!(graph[idx], "modified");
1154
1155        // 修改多个节点
1156        let idx2 = graph.add_node("second".to_string()).unwrap();
1157        graph[idx2] = "second_modified".to_string();
1158        assert_eq!(graph[idx2], "second_modified");
1159    }
1160
1161    #[test]
1162    fn test_remove_node() {
1163        let mut graph = Graph::<i32, f64>::directed();
1164        let idx = graph.add_node(42).unwrap();
1165        assert!(graph.contains_node(idx));
1166
1167        let data = graph.remove_node(idx).unwrap();
1168        assert_eq!(data, 42);
1169        assert_eq!(graph.node_count(), 0);
1170        assert!(!graph.contains_node(idx));
1171    }
1172
1173    #[test]
1174    fn test_add_edge() {
1175        let mut graph = Graph::<i32, f64>::directed();
1176        let a = graph.add_node(1).unwrap();
1177        let b = graph.add_node(2).unwrap();
1178        let edge = graph.add_edge(a, b, std::f64::consts::PI).unwrap();
1179
1180        assert_eq!(graph.edge_count(), 1);
1181        assert!(graph.contains_edge(edge));
1182        assert_eq!(*graph.get_edge(edge).unwrap(), std::f64::consts::PI);
1183    }
1184
1185    #[test]
1186    fn test_node_reuse() {
1187        let mut graph = Graph::<i32, f64>::directed();
1188        let idx1 = graph.add_node(1).unwrap();
1189        let _ = graph.remove_node(idx1).unwrap();
1190        let idx2 = graph.add_node(2).unwrap();
1191
1192        assert_eq!(idx2.index(), idx1.index());
1193        assert!(idx2.generation() > idx1.generation());
1194    }
1195
1196    #[test]
1197    fn test_neighbors() {
1198        let mut graph = Graph::<i32, f64>::directed();
1199        let a = graph.add_node(1).unwrap();
1200        let b = graph.add_node(2).unwrap();
1201        let c = graph.add_node(3).unwrap();
1202        graph.add_edge(a, b, 1.0).unwrap();
1203        graph.add_edge(a, c, 2.0).unwrap();
1204
1205        let neighbors: Vec<_> = graph.neighbors(a).collect();
1206        assert_eq!(neighbors.len(), 2);
1207    }
1208
1209    #[test]
1210    fn test_has_edge() {
1211        let mut graph = Graph::<i32, f64>::directed();
1212        let a = graph.add_node(1).unwrap();
1213        let b = graph.add_node(2).unwrap();
1214        graph.add_edge(a, b, 1.0).unwrap();
1215
1216        assert!(graph.has_edge(a, b));
1217        assert!(!graph.has_edge(b, a));
1218    }
1219}
god_graph/graph/graph_impl.rs

god_graph/graph/
graph_impl.rs
