Skip to main content

Module graph_impl

Module graph_impl 

Source
Expand description

Graph 核心实现

使用桶式邻接表(Bucket Adjacency List)和 Arena 分配器实现高性能图数据结构

§内存布局说明

本实现采用桶式邻接表(Bucket Adjacency List)格式,而非传统 CSR(压缩稀疏行):

特性传统 CSR本实现(桶式邻接表)
结构row_offsets + col_indicesVec<AdjBucket>,每个 bucket 含独立 Vec
增量更新❌ 不支持(需 O(V+E) 重建)✅ O(1) 插入
空间效率✅ 最优(无额外开销)⚠️ 略高(每节点一个 Vec 头)
适用场景静态图动态图(频繁增删边)

历史原因:早期代码使用 CsrStorage 命名,实际实现是桶式邻接表。 为保持 API 稳定性,内部结构仍用此名,但文档已正名为桶式邻接表

Structs§

Graph
图结构主实现 使用缓存行对齐优化,减少 false sharing
IncidentEdgesIter
关联边迭代器(快照语义)
NeighborsIter
邻居迭代器(快照语义)