一、Boost.Graph 的设计理念

Boost.Graph（BGL）不是一个“容器库”，而是：

Graph Concept + 泛型算法 + Traits 解耦设计

核心思想是：

• 图结构 与 图算法 完全解耦
• 算法只依赖 concept（接口），不依赖具体类型
• traits 用来在编译期获取图的“元信息”

这就是为什么在代码中会看到：

boost::graph_traits<G>::vertex_descriptor

而不是 G::vertex_descriptor

---

二、adjacency_list 是什么？

boost::adjacency_list<OutEdgeList, VertexList, Directed, ...>

adjacency_list 是 Boost.Graph 中的“可配置图生成器”
—— 不是一种图，而是一整个 图家族的模板工厂

---

1、设计技术

Boost.Graph 的目标不是：

“给使用者一个最快的图结构”

而是：

“让算法与图完全解耦，通过 traits + property_map 工作”

所以：

• 不绑定存储结构
• 不假设顶点 / 边连续
• 不强制属性存放方式
• 让使用者为 访问模式 做权衡

---

2、模板参数完整结构

template<
    class OutEdgeListS,   // 每个顶点的出边容器
    class VertexListS,    // 顶点容器
    class DirectedS,      // 有向 / 无向
    class VertexProperty, // 顶点属性
    class EdgeProperty,   // 边属性
    class GraphProperty,  // 图级属性
    class EdgeListS       // 全局边列表（很少用）
>
class adjacency_list;

---

3、前三个参数 = 图的“骨架”（95% 场景）

---

3.1 OutEdgeListS —— 出边怎么存？

OutEdgeListS ∈ { vecS, listS, setS, hash_setS }

决定：

一个顶点的邻接表是什么容器

选项	内部结构	特点	适合场景
vecS	std::vector	紧凑、最快遍历	静态图 / SLAM 后端
listS	std::list	插删稳定	动态图
setS	std::set	去重、有序	防止重边
hash_setS	哈希集合	O(1) 查找	大规模稀疏

流算法 / BFS / DFS → 首选 vecS

---

3.2 VertexListS —— 顶点怎么存？

VertexListS ∈ { vecS, listS }

决定：

• 顶点 descriptor 是否是整数
• 是否能用 vertex_index

选项	descriptor	特点
vecS	size_t	连续索引、最快
listS	迭代器	插删稳定但慢

几乎所有算法要求 vertex_index → 用 vecS

---

3.3 DirectedS —— 图的方向性

DirectedS ∈ { directedS, undirectedS, bidirectionalS }

类型	含义
directedS	有向图
undirectedS	无向图
bidirectionalS	有向 + 反向邻接

最大流 / 拓扑排序 / DAG → directedS

---

4、后 4 个参数 = 信息系统（property）

---

4.1 VertexProperty

boost::property<vertex_index_t, long, ...>

本质

给每个顶点绑定一组属性

典型用途：

• index
• color
• distance
• predecessor

算法通过 property_map 访问

---

4.2 EdgeProperty

boost::property<edge_capacity_t, double, ...>

用途

• 权重
• 容量
• 残量
• 反向边

最大流算法完全依赖这里

---

4.3 GraphProperty

boost::property<graph_name_t, std::string>

很少用，但可用于：

• 全局参数
• 元信息
• 统计量

---

4.4 EdgeListS（高级）

EdgeListS = listS

含义

是否维护一个“全局边容器”

几乎不用，除非：

• 你频繁遍历 所有边
• 图结构极端定制

---

5、一个完整例子（把所有参数串起来）

using Traits = boost::adjacency_list_traits<
    boost::vecS,
    boost::vecS,
    boost::directedS
>;

using Graph = boost::adjacency_list<
    boost::vecS,          // OutEdgeList
    boost::vecS,          // VertexList
    boost::directedS,     // Directed
    boost::property<      // VertexProperty
        boost::vertex_index_t, long,
        boost::property<boost::vertex_color_t, boost::default_color_type>
    >,
    boost::property<      // EdgeProperty
        boost::edge_capacity_t, double,
        boost::property<boost::edge_reverse_t, Traits::edge_descriptor>
    >
>;

---

6、adjacency_list 与算法的“契约”

Boost.Graph 算法只要求：

• graph_traits
• property_map
• iterator

它 不关心图内部如何存

这就是能如下操作：

• 把 SLAM 图 / 优化图
• 直接接到 BFS / Dijkstra / MaxFlow

---

7、性能选型速查表

场景	推荐
SLAM 后端因子图	vecS + vecS + directedS
最大流	vecS + vecS + directedS
动态拓扑	listS + listS
防止重边	setS

---

8、总结

adjacency_list 是一个“图结构策略组合器”，不是一个固定容器。

---

三、adjacency_list_traits 是什么？

一句话再强化

adjacency_list_traits 是 adjacency_list 的“类型裁判 + 编译期决策中心”

它不存数据，只负责 “告诉外界：这个图在类型层面长什么样”。

---

1、为什么需要 adjacency_list_traits？

1.1 adjacency_list 是高度模板化的

adjacency_list<
    OutEdgeListS,
    VertexListS,
    DirectedS,
    ...
>

不同组合意味着：

• vertex_descriptor 完全不同
• edge_descriptor 完全不同
• 是否允许并行边不同
• 算法分支不同

不能在 adjacency_list 本体里写死

---

2、adjacency_list_traits 的位置（体系关系）

adjacency_list
        │
        ├── adjacency_list_traits   ← 类型决策
        │
        └── graph_traits             ← 对算法暴露接口

traits 是 adjacency_list 的“前置决策层”

---

3、adjacency_list_traits 的模板定义

template<
    class OutEdgeListS,
    class VertexListS,
    class DirectedS
>
struct adjacency_list_traits;

注意：

• 只和前三个参数有关
• 和 property、GraphProperty 无关

---

4、adjacency_list_traits 决定了什么？

4.1 顶点 descriptor

using vertex_descriptor = ...;

VertexListS	vertex_descriptor
vecS	std::size_t
listS	list_iterator

是否是整数索引，全靠这里

---

4.2 边 descriptor（最关键）

using edge_descriptor = ...;

常见展开（vecS + vecS + directedS）

struct edge_descriptor {
    std::size_t source;
    std::size_t index;
};

实际上是：

(source vertex, index into out_edges[source])

不是指针，不是引用

---

4.3 directed_category

using directed_category =
    std::conditional_t<
        std::is_same_v<DirectedS, directedS>,
        directed_tag,
        ...
    >;

算法会用：

is_same<directed_category, directed_tag>

编译期裁剪代码路径

---

4.4 edge_parallel_category（是否允许重边）

using edge_parallel_category =
    std::conditional_t<
        is_set<OutEdgeListS>,
        disallow_parallel_edge_tag,
        allow_parallel_edge_tag
    >;

OutEdgeListS	结果
vecS	allow
listS	allow
setS	disallow

算法能否假设边唯一

---

4.5 traversal_category（能力标签）

using traversal_category =
    incidence_graph_tag
    | adjacency_graph_tag
    | vertex_list_graph_tag
    | ...

决定算法是否可用：

算法	要求
BFS	IncidenceGraph
Dijkstra	IncidenceGraph + VertexListGraph
Topological	BidirectionalGraph

---

5、adjacency_list_traits 与 graph_traits 的关系（

graph_traits< adjacency_list<...> >

内部直接引用 adjacency_list_traits：

using Traits = adjacency_list_traits<Out, Vert, Dir>;
using vertex_descriptor = Traits::vertex_descriptor;

traits 的 traits

---

6、adjacency_list_traits 在工程中的实际价值

6.1 为什么要显式写 Traits？

using Traits =
    boost::adjacency_list_traits<
        boost::vecS,
        boost::vecS,
        boost::directedS
    >;

因为需要：

• Traits::edge_descriptor
• Traits::vertex_descriptor

尤其在 property 中引用

---

6.2 典型用法（最大流）

boost::property<
    boost::edge_reverse_t,
    Traits::edge_descriptor
>

只有 traits 知道：

edge_descriptor 究竟是什么类型

---

7、adjacency_list_traits vs graph_traits（对照）

	adjacency_list_traits	graph_traits
作用对象	adjacency_list	任意 Graph
决定内容	descriptor 类型	算法接口
使用者	adjacency_list 内部	算法
是否模板	✔	✔

---

8、源码层级定位

boost/graph/adjacency_list.hpp
└── boost/graph/detail/adjacency_list.hpp
    └── adjacency_list_traits

---

9、一个完整的“类型链”示意（极其重要）

OutEdgeListS / VertexListS / DirectedS
            │
            ▼
adjacency_list_traits
            │
            ▼
vertex_descriptor / edge_descriptor
            │
            ▼
graph_traits<Graph>
            │
            ▼
Boost.Graph algorithms

---

终极总结

adjacency_list_traits 是 adjacency_list 在“类型世界”的身份证。

---

四、adjacency_list 的真实结构

以常见配置为例：

using Graph = boost::adjacency_list<
    boost::vecS,        // OutEdgeList
    boost::vecS,        // VertexList
    boost::directedS
>;

内部近似为：

struct Graph {
    std::vector<Vertex> vertices;
};

struct Vertex {
    std::vector<Edge> out_edges;
};

这就是为什么：

• add_edge() 是 O(1)
• add_vertex() 可能 invalidate descriptor（vecS）

---

五、adjacency_list + traits 在算法中的使用方式

5.1 标准算法接口

template<class Graph>
void bfs(const Graph& g) {
    using V = typename boost::graph_traits<Graph>::vertex_descriptor;
    ...
}

算法从不直接使用 adjacency_list

---

六、完整示例

#include <boost/graph/adjacency_list.hpp>

using Graph = boost::adjacency_list<
    boost::vecS,
    boost::vecS,
    boost::undirectedS
>;

int main() {
    Graph g(5);

    auto v0 = vertex(0, g);
    auto v1 = vertex(1, g);

    add_edge(v0, v1, g);
}

---

七、SLAM / 图优化中的最佳配置

推荐配置

using Graph = boost::adjacency_list<
    boost::vecS,      // 出边表
    boost::vecS,      // 顶点表
    boost::undirectedS,
    VertexProperty,
    EdgeProperty
>;

原因：

• vertex_descriptor = size_t
• 快速索引
• 可直接映射到状态向量

---

八、常见坑总结

保存 descriptor 到文件

→ 错误（不可持久）

vecS + 频繁 add/remove vertex

→ descriptor 失效

用 adjacency_list 当“图数据库”

→ 不适合

---

九、adjacency_list_traits vs graph_traits

trait	作用
adjacency_list_traits	adjacency_list 专用
graph_traits	所有 Graph 通用

实际算法中 几乎只用 graph_traits

---

十、总结“本质一句话”

adjacency_list 是实现，adjacency_list_traits 是它在编译期暴露给算法的“身份证”。

---