Boost中Graph模块中boost::edge_capacity和boost::edge_capacity_t

boost::edge_capacity

一、boost::edge_capacity是什么

定义

boost::edge_capacity是一个edge property tag，用于标识“边的最大可通过量（capacity）”。

它本身不存数据，只用于：

• 在类型系统中标记一种语义
• 让算法通过property_map找到对应的数据

数学语义（流网络）

对一条边 (e=(u→v)e = (u \rightarrow v)e=(u→v))：

c(e)≥0 c(e) \ge 0c(e)≥0

表示：

这条边最多允许通过的流量上限

二、boost::edge_capacity在类型系统中的角色

2.1 它是一个Tag

structedge_capacity_t{};

Boost 使用tag dispatch：

boost::edge_capacity_t

只是一个“名字”，不是变量。

2.2 为什么不用字符串 / enum？

因为 Boost.Graph 的设计目标是：

• 编译期绑定
• 零运行时开销
• 支持 ADL + traits

三、edge_capacity如何真正“连到数据”？

3.1 在adjacency_list中的定义方式

usingGraph=boost::adjacency_list<boost::vecS,boost::vecS,boost::directedS,boost::no_property,boost::property<boost::edge_capacity_t,double>>;

含义

给每一条边绑定一个double capacity

3.2 多重 property 的嵌套结构（非常重要）

boost::property<edge_capacity_t,double,boost::property<edge_residual_capacity_t,double,boost::property<edge_reverse_t,Traits::edge_descriptor>>>

本质是一个编译期链表：

edge_property ├── capacity ├── residual_capacity └── reverse_edge

四、property_map：edge_capacity 的访问方式

4.1 获取 capacity map

autocapacity=get(boost::edge_capacity,g);

类型是：

boost::property_map<Graph,boost::edge_capacity_t>::type

4.2 使用方式（像数组一样）

capacity[e]=10.0;doublec=capacity[e];

其中：

e : edge_descriptor

4.3 本质展开（非常关键）

capacity[e]

实际上等价于：

g.vertices[u].out_edges[k].property.capacity

零额外开销，完全 inline

五、edge_capacity在算法中的真实作用

5.1 最大流算法的“契约”

Boost 的最大流算法（如push_relabel_max_flow）要求：

edge_capacity是“原始上界”

5.2 流算法如何使用它？

伪代码层面：

for each edge e: residual[e] = capacity[e]

之后：

• capacity：只读
• residual：动态修改

5.3 capacity vs residual（必须区分）

改错一个，算法直接错

六、edge_capacity与 reverse edge 的关系

6.1 为什么需要 reverse？

残量网络中：

cr(erev)=f(e) c_r(e^{rev}) = f(e)cr​(erev)=f(e)

如果没有reverse：

• 无法回退流量
• 算法无法收敛

6.2 adjacency_list 的设计选择

edge_descriptor = (source, index)

无法自动推导反向边

所以：

edge_reverse_t → edge_descriptor

七、源码级追踪

7.1 property tag 定义

boost/graph/properties.hpp

BOOST_INSTALL_PROPERTY(edge,capacity);

7.2 property_map 特化

boost/graph/detail/adjacency_list.hpp

内部：

get(edge_capacity,graph)

返回：

adj_list_edge_property_map<...>

八、实践示例：如何正确使用 edge_capacity

8.1 正确添加一条边（最大流）

voidadd_edge(intu,intv,doublecap,Graph&g,EdgeCapacityMap&capacity,EdgeReverseMap&rev){autoe1=add_edge(u,v,g).first;autoe2=add_edge(v,u,g).first;capacity[e1]=cap;capacity[e2]=0.0;rev[e1]=e2;rev[e2]=e1;}

capacity 只给正向边

8.2 常见致命错误

忘记设置 capacity
反向边 capacity ≠ 0
residual / capacity 类型不一致
使用无符号类型（flow 可能为负）

九、在 SLAM / 优化中的类比理解

本质都是“约束传播 + 回退”

十、什么时候不该用 edge_capacity

总结

boost::edge_capacity不是一个变量，而是 Boost.Graph 中“流语义”的入口标签。
它通过 property_map，把数学上的容量概念，零开销地注入到泛型算法中。

boost::edge_capacity_t

一、boost::edge_capacity_t是什么

定义

boost::edge_capacity_t是一个Edge Property Tag，用于在编译期标识“边容量（capacity）这一语义”。

重点：

• 它不是变量
• 不保存数据
• 不参与运行时逻辑
• 只存在于类型系统 + 模板分发中

二、edge_capacity_t在 Boost.Graph 中的身份层级

edge_capacity_t │ ├── property tag（语义标签） │ ├── 用于 property<..., T> │ ├── 用于 property_map<Graph, Tag> │ └── 被最大流算法作为“编译期契约”检查

它是“算法与图之间的语义约定”。

三、edge_capacity_t的真实定义

在：

boost/graph/properties.hpp

会看到类似：

BOOST_INSTALL_PROPERTY(edge,capacity);

宏展开后等价于：

structedge_capacity_t{typedefedge_property_tag kind;};

这里的关键点

算法靠kind区分 vertex / edge / graph 属性

四、edge_capacity_t本身不存数据，数据在哪里？

答案：在property<edge_capacity_t, T>

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

含义是：

“给每条边关联一个 double 类型的数据，其语义标签是 edge_capacity”

4.1 property 是一个类型链表（非常重要）

boost::property<edge_capacity_t,double,boost::property<edge_residual_capacity_t,double,boost::property<edge_reverse_t,edge_descriptor>>>

在类型系统中等价于：

(edge_capacity → double) ↓ (edge_residual_capacity → double) ↓ (edge_reverse → edge_descriptor)

这不是运行时结构，而是编译期结构

五、edge_capacity_t如何被“取出来”——property_map

5.1 property_map 的类型推导

boost::property_map<Graph,boost::edge_capacity_t>::type

含义是：

“在 Graph 中，查找 edge_capacity_t 对应的 map 类型”

5.2 get() 是如何工作的？

autocap=get(boost::edge_capacity,g);

这里发生了三步编译期决策：

1. 根据Graph→ 找到 graph_traits
2. 根据edge_capacity_t→ 找到 edge_property
3. 生成一个零开销访问器

5.3 使用方式

cap[e]=10.0;doublec=cap[e];

这里的[]不是数组，而是：

operator[](edge_descriptor)

完全 inline，无虚函数

六、edge_capacity_t 在算法中的“契约角色”

6.1 最大流算法的编译期要求

以push_relabel_max_flow为例，它静态要求：

Graph 必须提供： - edge_capacity_t - edge_residual_capacity_t - edge_reverse_t - vertex_index_t

否则：

编译失败（不是运行时错误）

6.2 在算法中的语义分工

capacity 是“物理上限”，不是状态变量

七、为什么 capacity 和 residual 必须分开？

数学原因

在残量网络中：

cr(e)=c(e)−f(e) c_r(e) = c(e) - f(e)cr​(e)=c(e)−f(e)

如果混用：

• 无法回退流
• 无法判断饱和
• 算法不收敛

所以 Boost 强制你提供两个不同 tag

八、为什么edge_capacity_t是 tag，而不是字段名

如果是字段名，会发生什么？

structEdge{doublecapacity;};

算法与结构强耦合
无法外置属性
无法做 external property_map

使用 tag 的好处

九、external property_map 中的 edge_capacity_t

你甚至可以不把 capacity 存在 Graph 里：

std::vector<double>cap_storage(num_edges);autocap=boost::make_iterator_property_map(cap_storage.begin(),edge_index_map);

算法只认：

edge_capacity_t

不关心数据在哪里

十、adjacency_list 为什么不“内建 capacity”？

因为 Boost 的哲学是：

图结构 ≠ 图语义

edge_capacity_t是语义，不是结构。

十一、工程中常见误区

把 capacity 当 residual 改
反向边 capacity ≠ 0
capacity 用unsigned
忘了提供 edge_capacity_t，却调用 max-flow

总结

boost::edge_capacity_t是 Boost.Graph 中“流语义”的类型级入口。
它通过 property_tag + property_map，把数学中的容量概念，以零运行时成本注入到泛型算法中。