Expand description
Graph 核心实现
使用桶式邻接表(Bucket Adjacency List)和 Arena 分配器实现高性能图数据结构
§内存布局说明
本实现采用桶式邻接表(Bucket Adjacency List)格式,而非传统 CSR(压缩稀疏行):
| 特性 | 传统 CSR | 本实现(桶式邻接表) |
|---|---|---|
| 结构 | row_offsets + col_indices | Vec<AdjBucket>,每个 bucket 含独立 Vec |
| 增量更新 | ❌ 不支持(需 O(V+E) 重建) | ✅ O(1) 插入 |
| 空间效率 | ✅ 最优(无额外开销) | ⚠️ 略高(每节点一个 Vec 头) |
| 适用场景 | 静态图 | 动态图(频繁增删边) |
历史原因:早期代码使用 CsrStorage 命名,实际实现是桶式邻接表。
为保持 API 稳定性,内部结构仍用此名,但文档已正名为桶式邻接表。
Structs§
- Graph
- 图结构主实现 使用缓存行对齐优化,减少 false sharing
- Incident
Edges Iter - 关联边迭代器(快照语义)
- Neighbors
Iter - 邻居迭代器(快照语义)