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

god_gragh/graph/
impl_.rs
