先说一句标题里的 BOOS 其实是 Boost拼写差了一个字母。网上搜“boost”这个词前几页很容易刷出来一堆 DC-DC 升压电路的文章但如果你已经读到了boost::edge_reverse_t和boost::vertex_color_t这两个名字说明你已经站在 C Boost 库的 Graph 模块门口了。我第一次见到这两个带下划线的类型名是在一份最大流算法代码里。当时代码能跑但我完全不知道它们在干什么到处搜中文资料也搜不到正经解释。翻了几天源码才弄明白这两兄弟其实都只是“属性标签”作用是在编译期告诉 Boost.Graph 某段数据属于顶点还是边。这篇文章就把它们彻底拆开讲清楚它们为什么存在、在哪些算法里出现、怎么避免最常见的坑。适合刚接触 BGL 属性系统的人也适合正在改最大流、搜索算法代码但被编译错误卡住的人。1. 先说清楚edge_reverse_t 和 vertex_color_t 到底是什么1.1 属性标签理解这两个名字的钥匙Boost.Graph 里的“图”不是简单的顶点加边的集合。它允许在顶点上挂名字、颜色、距离、前驱节点在边上挂权重、容量、反向边。为了实现这种“可插拔”的数据携带方式BGL 引入了属性property抽象层。每一个属性都有对应的标签类型tag type标签本身通常是个空结构体里面的kind类型声明它属于顶点属性还是边属性。你在代码里写boost::propertyboost::vertex_color_t, boost::default_color_type的时候实际上就是把vertex_color_t这个标签和具体数据类型绑定在一起告诉adjacency_list请给每个顶点额外存一份default_color_type数据。同理boost::propertyboost::edge_reverse_t, EdgeDescriptor就是告诉图每条边请额外存一个边描述符用来指向它的反向边。你可以把标签理解为储物柜上的编号贴纸。贴纸本身不装任何东西但拿着它你才能找到正确的柜子。vertex_color_t是顶点柜子上的“颜色”贴纸edge_reverse_t是边柜子上的“反向边”贴纸。之所以用类型而不是字符串常量是因为 C 泛型代码需要靠类型来做重载和派发字符串做不到这种编译期匹配。1.2 两个标签的家谱和定义位置vertex_color_t定义在boost/graph/properties.hppedge_reverse_t定义在boost/graph/reverse_graph.hpp但它也属于properties.hpp那套属性体系。它们结构上和下面这段代码等价namespace boost { struct vertex_color_t { typedef vertex_property_tag kind; }; struct edge_reverse_t { typedef edge_property_tag kind; }; }注意这里不是枚举也不是函数。这两个名字是类型。所以你不会直接edge_reverse_t()去调用某个逻辑而是在模板参数里用它们做类型标记。这里的kind非常关键vertex_property_tag会触发get/put的顶点属性映射路径edge_property_tag会触发边的路径。换句话说get(edge_reverse, g)能返回边的属性映射get(vertex_color, g)能返回顶点的属性映射全靠这个 tag 在编译期分派。1.3 先把 get 和 put 跑起来看一个能编译的最小例子把颜色属性挂到一张无向图上然后手动读写顶点颜色#include boost/graph/adjacency_list.hpp #include iostream typedef boost::adjacency_list boost::vecS, boost::vecS, boost::undirectedS, boost::propertyboost::vertex_color_t, boost::default_color_type Graph; int main() { Graph g(3); boost::add_edge(0, 1, g); boost::add_edge(1, 2, g); auto color boost::get(boost::vertex_color, g); boost::put(color, 0, boost::white_color); boost::put(color, 1, boost::gray_color); boost::put(color, 2, boost::black_color); std::cout boost::get(color, 1) \n; // 输出 gray_color 对应的枚举值 return 0; }这里的boost::get(boost::vertex_color, g)返回的是一个属性映射对象property map。它本身不是图不是引用而是一个可以拷贝、可以传递的工具对象。之后put和get都通过它来操作。很多人第一次在这里迷糊以为get(vertex_color, g)直接得到了某个颜色值其实它得到的是“能读写颜色的工具”。default_color_type是 BGL 内置的颜色枚举只有三个值white_color、gray_color、black_color。你完全可以换成自己的类型但那样的话算法内部使用color_traitsColorValue来获取白灰黑状态你就得为自定义类型提供对应的white()、gray()、black()静态方法。一般情况下直接用default_color_type就够了。2. vertex_color_t图算法里无处不在的着色器2.1 白灰黑三种颜色的语义BFS、DFS 这类搜索算法需要区分三种节点状态还没见过、正在处理、处理完了。这就是白灰黑三色。白色表示未被发现灰色表示已经进入搜索栈或队列但还没处理完黑色表示彻底结束。为什么不用简单的bool visited因为在 DFS 里访问到一个灰色顶点意味着存在一条回边这正是判断图中是否有环的关键信息。黑色顶点则表示该顶点的整棵子树已经展开完毕可以安全跳过。布尔值只能表达“去过/没去过”无法表达“正在去/去完了”这第三态。如果你只想写朴素的 BFS那布尔值确实够用一旦涉及环检测、拓扑排序、双连通分量这类算法三色状态就是刚需。生活化类比煮鸡蛋。白色是生鸡蛋灰色是下锅煮了一半黑色是煮好关火。BFS 里灰色对应“已经放进队列但还没出队处理”黑色对应“已经处理完并且出队”。2.2 在 adjacency_list 里怎么正确声明颜色属性最省事的做法是直接写在图类型里using Graph boost::adjacency_list boost::vecS, boost::vecS, boost::directedS, boost::propertyboost::vertex_color_t, boost::default_color_type;如果你用vecS作为顶点容器adjacency_list会自动维护vertex_index_t这个内部索引很多算法都依赖它临时分配数组。但颜色属性不会自动出现。新手最常见的一个编译错误就是在adjacency_listvecS, vecS, directedS这种默认类型上直接调用breadth_first_search(g, s, visitor)结果模板展开到一半就报错因为图里根本没有vertex_color_t对应的属性映射。如果你不想把颜色写进图类型也可以用外部属性映射。典型写法是auto color_map boost::make_vector_property_mapboost::default_color_type( boost::get(boost::vertex_index, g));外部映射的好处是不污染图的持久结构坏处是每次调用算法都要显式传进去漏一个就编译失败。我的建议是快速验证算法用内部属性生产环境里如果图类型已经很复杂把颜色这种算法临时状态放到外部映射里更干净。2.3 动手实验用颜色映射实现 DFS 找环我写一个经典的 DFS 环检测用来展示vertex_color_t三个值的实际用法#include boost/graph/adjacency_list.hpp #include boost/tuple/tuple.hpp #include iostream using Graph boost::adjacency_list boost::vecS, boost::vecS, boost::directedS, boost::propertyboost::vertex_color_t, boost::default_color_type; template typename Graph bool dfs_cycle_visit(typename boost::graph_traitsGraph::vertex_descriptor u, Graph g, typename boost::property_mapGraph, boost::vertex_color_t::type color) { boost::put(color, u, boost::gray_color); typename boost::graph_traitsGraph::adjacency_iterator ai, a_end; for (boost::tie(ai, a_end) boost::adjacent_vertices(u, g); ai ! a_end; ai) { auto v *ai; if (boost::get(color, v) boost::white_color) { if (dfs_cycle_visit(v, g, color)) return true; } else if (boost::get(color, v) boost::gray_color) { return true; // 回边说明有环 } } boost::put(color, u, boost::black_color); return false; } template typename Graph bool has_cycle(Graph g) { auto color boost::get(boost::vertex_color, g); typename boost::graph_traitsGraph::vertex_iterator vi, v_end; for (boost::tie(vi, v_end) boost::vertices(g); vi ! v_end; vi) { if (boost::get(color, *vi) boost::white_color) { if (dfs_cycle_visit(*vi, g, color)) return true; } } return false; } int main() { Graph g(4); boost::add_edge(0, 1, g); boost::add_edge(1, 2, g); boost::add_edge(2, 0, g); // 回边构成环 boost::add_edge(1, 3, g); std::cout (has_cycle(g) ? has cycle : no cycle) \n; return 0; }顶点进入递归时染成灰色如果碰到一个灰色邻居说明它还在当前递归栈里这就是回边图里有环。全部邻居处理完才把当前顶点染成黑色。这个例子里颜色映射就是vertex_color_t背后的数据。如果没有它你只能自己再开一个unordered_map或vectorint效果一样但代码明显更啰嗦而且没法直接复用到 BGL 其他算法里。3. edge_reverse_t最大流算法的隐形半边天3.1 最大流为什么要“反向边”属性先想清楚一个问题在有向图上找最大流时如果某条路径选得不好算法怎么反悔答案是反向边。每次从 u 到 v 流过 f 单位的流量就可以认为从 v 到 u 存在一条容量为 f 的反向边表示这部分流量可以退回去。这样正反成对的边集合构成了残差网络。几乎所有最大流算法都需要从一条边迅速跳到它的反向边。如果不借助 BGL 机制你可能会用std::unordered_mapedge_descriptor, edge_descriptor来存映射每次增广的时候find一次。但 BGL 的算法模板是高度泛化的它不知道你的哈希表放在哪里于是 Boost 干脆把“反向边”定义为边的一个属性edge_reverse_t。算法内部通过get(edge_reverse, g, e)直接拿到反向边不用关心这个属性是存在图内部还是来自外部映射。3.2 edge_reverse_t 的具体含义edge_reverse_t属性的值类型是边描述符edge_descriptor也就是图上真实存在的另一条边。它表示当前这条边的反向搭档。因为在残差网络里每条边都有唯一反向边所以这个映射在设计上是成对对称的如果rev get(edge_reverse, g, e)那么get(edge_reverse, g, rev) e。在最大流问题的典型代码里图类型通常这样定义using Traits boost::adjacency_list_traitsboost::vecS, boost::vecS, boost::directedS; using Graph boost::adjacency_list boost::vecS, boost::vecS, boost::directedS, boost::propertyboost::vertex_color_t, boost::default_color_type, boost::propertyboost::edge_capacity_t, long, boost::propertyboost::edge_residual_capacity_t, long, boost::propertyboost::edge_reverse_t, Traits::edge_descriptor;这个类型看起来层层嵌套其实就是顶点带颜色边带三个属性——容量、剩余容量、反向边。edge_reverse_t是嵌套链的最后一环它的值类型是Traits::edge_descriptor。3.3 添加边的完整操作因为每条边都要有反向搭档我强烈建议封装成函数不要裸写add_edge。我早期在这个地方吃过不少亏漏一次put就会让算法给出错误结果。void add_edge_with_reverse(Graph g, int u, int v, long cap) { auto e boost::add_edge(u, v, g).first; auto rev boost::add_edge(v, u, g).first; boost::put(boost::edge_capacity, g, e, cap); boost::put(boost::edge_capacity, g, rev, 0); boost::put(boost::edge_reverse, g, e, rev); boost::put(boost::edge_reverse, g, rev, e); }注意反向边容量初始化成 0不是和正向边一样大。最大流算法在增广的时候会在正向边扣减容量、在反向边加回容量从而实现“撤销流量”。如果你把反向边容量也顺手设成一个不小的数残差网络就失真了结果往往会偏大。3.4 一次完整的 Edmonds-Karp 调用下面是一段完整的 Edmonds-Karp 最大流调用我选择显式传入全部参数避免依赖太深的默认行为#include boost/graph/adjacency_list.hpp #include boost/graph/edmonds_karp_max_flow.hpp #include iostream #include vector typedef boost::adjacency_list_traitsboost::vecS, boost::vecS, boost::directedS Traits; typedef boost::adjacency_list boost::vecS, boost::vecS, boost::directedS, boost::propertyboost::vertex_color_t, boost::default_color_type, boost::propertyboost::edge_capacity_t, long, boost::propertyboost::edge_residual_capacity_t, long, boost::propertyboost::edge_reverse_t, Traits::edge_descriptor Graph; void add_edge_with_reverse(Graph g, int u, int v, long cap) { auto e boost::add_edge(u, v, g).first; auto rev boost::add_edge(v, u, g).first; boost::put(boost::edge_capacity, g, e, cap); boost::put(boost::edge_capacity, g, rev, 0); boost::put(boost::edge_reverse, g, e, rev); boost::put(boost::edge_reverse, g, rev, e); } int main() { Graph g(4); add_edge_with_reverse(g, 0, 1, 3); add_edge_with_reverse(g, 0, 2, 2); add_edge_with_reverse(g, 1, 2, 1); add_edge_with_reverse(g, 1, 3, 2); add_edge_with_reverse(g, 2, 3, 4); std::vectorTraits::vertex_descriptor predecessor(4); auto pre_map boost::make_iterator_property_map( predecessor.begin(), boost::get(boost::vertex_index, g)); long flow boost::edmonds_karp_max_flow( g, 0, 3, boost::get(boost::edge_capacity, g), boost::get(boost::edge_residual_capacity, g), boost::get(boost::edge_reverse, g), pre_map, boost::get(boost::vertex_color, g)); std::cout max flow flow \n; return 0; }跑这个例子的结果应该是 5。你可以手动改容量验证把 0-2 的容量从 2 改成 20最大流也不会变 20因为瓶颈在 2-3 那条 4 的容量上。把edge_residual_capacity打印出来能很清楚看到每条边的流量分配。这个例子里的edge_reverse_t承担了算法内部的“反向跳转”职责而vertex_color_t则承担了 BFS 搜索增广路径时的访问状态记录。4. 这两个标签的常见误用和调试方法4.1 标签不是函数属性映射才是工具第一个高频误区把vertex_color_t当成一个能直接调用的对象。有人会写auto c boost::vertex_color_t();然后试图c(g)这当然不行。标签是类型属性映射是通过get(vertex_color, g)得到的对象。你可以把标签理解成“钥匙的类型”而get才是开锁动作。真正操作数据时你手里拿的永远是属性映射对象不是标签本身。4.2 属性缺失导致的长篇编译错误第二个高频坑是属性缺失。adjacency_listvecS, vecS, directedS默认只有vertex_index_t这种内部索引能自动得到颜色、容量、反向边这些属性都不会凭空冒出来。直接对这种默认图调用breadth_first_search或edmonds_karp_max_flow的简洁重载模板展开到一半就卡在get(vertex_color, g)或get(edge_reverse, g)上。报错会很长因为模板嵌套太深头部看不到关键信息。但耐心翻到末尾一般能看到类似no matching function for call to get(vertex_color_t, Graph)的提示。处理办法有两种第一种是在图类型上补内部属性第二种是改用外部属性映射并调用带完整参数的算法重载。对快速验证算法内部属性成本最低。4.3 内部属性还是外部属性映射下表是我在实际项目中的选择标准方案优点缺点内部属性写法简单算法默认能找到图类型写起来很长换属性类型要改模板参数外部属性映射不侵入图类型同一张图可绑不同映射每个算法都要显式传映射漏传就编译失败我的建议示例代码和算法实验用内部属性生产环境里如果图类型已经很大很复杂优先用外部映射把颜色、容量这些算法临时数据和业务数据分开。尤其是颜色它只是算法运行时的状态长期占用每个顶点的存储并不划算。4.4 调试 edge_reverse 成对性的小技巧最大流结果不对先别急着怀疑算法先去检查edge_reverse是否成对。一个非常有效的自检代码是遍历所有边for (auto e : boost::make_iterator_range(boost::edges(g))) { auto rev boost::get(boost::edge_reverse, g, e); if (boost::get(boost::edge_reverse, g, rev) ! e) { std::cerr edge_reverse not symmetric for edge e \n; } }如果打印出对称性错误说明建图时把反向关系接错了。还有一种情况是edge_reverse虽然成对但反向边的容量没有初始化为 0导致算法在反向边上“凭空增广”。调试时把每条边的容量、剩余容量和反向边一起打印出来会省下好几个小时。5. 从例子到生产代码我踩过的坑与建议5.1 在 reverse_graph 上读 edge_reverse_t 的正确姿势boost::reverse_graphGraph会把有向图所有边反转常用来把需要反向图的问题统一到正向图接口上。但注意reverse_graph的边描述符并不是你原始图里的 edge_descriptor而是一个包装类型可以理解为“原边 是否反转”的组合。所以get(edge_reverse, rg, e)返回的是 reverse_graph 自己域的边描述符不是原始图的边描述符。如果你想把反向图里的边映射回原图需要先把原始边描述符保存下来不能指望edge_reverse_t帮你跨图域转换。我踩过的坑是在reverse_graph上跑最大流算法误以为拿到的edge_reverse能和原图边直接比较结果类型都对不上编译直接断在operator!。正确做法是能不用reverse_graph就别用需要用的时候明确区分两个图域的描述符。必要时使用boost::graph_traitsreverse_graphGraph::edge_descriptor作为存储类型。5.2 大图上 vecS 和 listS 对这两个标签的影响vecS顶点容器自带连续索引但删除顶点会导致后续顶点索引前移原来按索引映射的颜色、前驱等数据全部错位。edge_reverse_t存的是边描述符如果你频繁增删边vecS的边描述符也可能失效。相比之下listS更稳定但默认没有vertex_index_t很多算法又依赖索引需要你手动用外部属性提供。我的经验是如果图规模固定、只建一次用vecS最舒服如果图会动态增删且要反复计算最大流优先考虑listS加手工维护的vertex_index_t并且不要在算法运行期间删除边。否则edge_reverse_t指向的边描述符可能在你不知道的时候变成悬垂描述符调试起来非常痛苦。5.3 给后来者的三句话经验第一先把图类型的属性集合想清楚再写算法。很多看起来玄学的编译报错根因就是少写了一个vertex_color_t或edge_reverse_t。第二把“加边并接反向边”封装成一个独立函数这是成本最低的防错手段。第三遇到弄不清楚的属性时直接打开boost/graph/properties.hpp和boost/graph/reverse_graph.hpp读定义比在网上翻二手中文资料快得多。最后分享一个我现在的固定习惯任何使用 BGL 最大流算法的新代码我都会先写一个几十行的最小图手动算一遍最大流把结果和手算对上才开始接真实数据。这个习惯救了我很多次。edge_reverse_t和vertex_color_t虽然只是不起眼的小标签但真正理解它们之后你再去看最大流、二分图匹配、连通分量这些算法的源码会发现整体逻辑一下子通透了很多。
先说一句标题里的 BOOS 其实是 Boost拼写差了一个字母。网上搜“boost”这个词前几页很容易刷出来一堆 DC-DC 升压电路的文章但如果你已经读到了boost::edge_reverse_t和boost::vertex_color_t这两个名字说明你已经站在 C Boost 库的 Graph 模块门口了。我第一次见到这两个带下划线的类型名是在一份最大流算法代码里。当时代码能跑但我完全不知道它们在干什么到处搜中文资料也搜不到正经解释。翻了几天源码才弄明白这两兄弟其实都只是“属性标签”作用是在编译期告诉 Boost.Graph 某段数据属于顶点还是边。这篇文章就把它们彻底拆开讲清楚它们为什么存在、在哪些算法里出现、怎么避免最常见的坑。适合刚接触 BGL 属性系统的人也适合正在改最大流、搜索算法代码但被编译错误卡住的人。1. 先说清楚edge_reverse_t 和 vertex_color_t 到底是什么1.1 属性标签理解这两个名字的钥匙Boost.Graph 里的“图”不是简单的顶点加边的集合。它允许在顶点上挂名字、颜色、距离、前驱节点在边上挂权重、容量、反向边。为了实现这种“可插拔”的数据携带方式BGL 引入了属性property抽象层。每一个属性都有对应的标签类型tag type标签本身通常是个空结构体里面的kind类型声明它属于顶点属性还是边属性。你在代码里写boost::propertyboost::vertex_color_t, boost::default_color_type的时候实际上就是把vertex_color_t这个标签和具体数据类型绑定在一起告诉adjacency_list请给每个顶点额外存一份default_color_type数据。同理boost::propertyboost::edge_reverse_t, EdgeDescriptor就是告诉图每条边请额外存一个边描述符用来指向它的反向边。你可以把标签理解为储物柜上的编号贴纸。贴纸本身不装任何东西但拿着它你才能找到正确的柜子。vertex_color_t是顶点柜子上的“颜色”贴纸edge_reverse_t是边柜子上的“反向边”贴纸。之所以用类型而不是字符串常量是因为 C 泛型代码需要靠类型来做重载和派发字符串做不到这种编译期匹配。1.2 两个标签的家谱和定义位置vertex_color_t定义在boost/graph/properties.hppedge_reverse_t定义在boost/graph/reverse_graph.hpp但它也属于properties.hpp那套属性体系。它们结构上和下面这段代码等价namespace boost { struct vertex_color_t { typedef vertex_property_tag kind; }; struct edge_reverse_t { typedef edge_property_tag kind; }; }注意这里不是枚举也不是函数。这两个名字是类型。所以你不会直接edge_reverse_t()去调用某个逻辑而是在模板参数里用它们做类型标记。这里的kind非常关键vertex_property_tag会触发get/put的顶点属性映射路径edge_property_tag会触发边的路径。换句话说get(edge_reverse, g)能返回边的属性映射get(vertex_color, g)能返回顶点的属性映射全靠这个 tag 在编译期分派。1.3 先把 get 和 put 跑起来看一个能编译的最小例子把颜色属性挂到一张无向图上然后手动读写顶点颜色#include boost/graph/adjacency_list.hpp #include iostream typedef boost::adjacency_list boost::vecS, boost::vecS, boost::undirectedS, boost::propertyboost::vertex_color_t, boost::default_color_type Graph; int main() { Graph g(3); boost::add_edge(0, 1, g); boost::add_edge(1, 2, g); auto color boost::get(boost::vertex_color, g); boost::put(color, 0, boost::white_color); boost::put(color, 1, boost::gray_color); boost::put(color, 2, boost::black_color); std::cout boost::get(color, 1) \n; // 输出 gray_color 对应的枚举值 return 0; }这里的boost::get(boost::vertex_color, g)返回的是一个属性映射对象property map。它本身不是图不是引用而是一个可以拷贝、可以传递的工具对象。之后put和get都通过它来操作。很多人第一次在这里迷糊以为get(vertex_color, g)直接得到了某个颜色值其实它得到的是“能读写颜色的工具”。default_color_type是 BGL 内置的颜色枚举只有三个值white_color、gray_color、black_color。你完全可以换成自己的类型但那样的话算法内部使用color_traitsColorValue来获取白灰黑状态你就得为自定义类型提供对应的white()、gray()、black()静态方法。一般情况下直接用default_color_type就够了。2. vertex_color_t图算法里无处不在的着色器2.1 白灰黑三种颜色的语义BFS、DFS 这类搜索算法需要区分三种节点状态还没见过、正在处理、处理完了。这就是白灰黑三色。白色表示未被发现灰色表示已经进入搜索栈或队列但还没处理完黑色表示彻底结束。为什么不用简单的bool visited因为在 DFS 里访问到一个灰色顶点意味着存在一条回边这正是判断图中是否有环的关键信息。黑色顶点则表示该顶点的整棵子树已经展开完毕可以安全跳过。布尔值只能表达“去过/没去过”无法表达“正在去/去完了”这第三态。如果你只想写朴素的 BFS那布尔值确实够用一旦涉及环检测、拓扑排序、双连通分量这类算法三色状态就是刚需。生活化类比煮鸡蛋。白色是生鸡蛋灰色是下锅煮了一半黑色是煮好关火。BFS 里灰色对应“已经放进队列但还没出队处理”黑色对应“已经处理完并且出队”。2.2 在 adjacency_list 里怎么正确声明颜色属性最省事的做法是直接写在图类型里using Graph boost::adjacency_list boost::vecS, boost::vecS, boost::directedS, boost::propertyboost::vertex_color_t, boost::default_color_type;如果你用vecS作为顶点容器adjacency_list会自动维护vertex_index_t这个内部索引很多算法都依赖它临时分配数组。但颜色属性不会自动出现。新手最常见的一个编译错误就是在adjacency_listvecS, vecS, directedS这种默认类型上直接调用breadth_first_search(g, s, visitor)结果模板展开到一半就报错因为图里根本没有vertex_color_t对应的属性映射。如果你不想把颜色写进图类型也可以用外部属性映射。典型写法是auto color_map boost::make_vector_property_mapboost::default_color_type( boost::get(boost::vertex_index, g));外部映射的好处是不污染图的持久结构坏处是每次调用算法都要显式传进去漏一个就编译失败。我的建议是快速验证算法用内部属性生产环境里如果图类型已经很复杂把颜色这种算法临时状态放到外部映射里更干净。2.3 动手实验用颜色映射实现 DFS 找环我写一个经典的 DFS 环检测用来展示vertex_color_t三个值的实际用法#include boost/graph/adjacency_list.hpp #include boost/tuple/tuple.hpp #include iostream using Graph boost::adjacency_list boost::vecS, boost::vecS, boost::directedS, boost::propertyboost::vertex_color_t, boost::default_color_type; template typename Graph bool dfs_cycle_visit(typename boost::graph_traitsGraph::vertex_descriptor u, Graph g, typename boost::property_mapGraph, boost::vertex_color_t::type color) { boost::put(color, u, boost::gray_color); typename boost::graph_traitsGraph::adjacency_iterator ai, a_end; for (boost::tie(ai, a_end) boost::adjacent_vertices(u, g); ai ! a_end; ai) { auto v *ai; if (boost::get(color, v) boost::white_color) { if (dfs_cycle_visit(v, g, color)) return true; } else if (boost::get(color, v) boost::gray_color) { return true; // 回边说明有环 } } boost::put(color, u, boost::black_color); return false; } template typename Graph bool has_cycle(Graph g) { auto color boost::get(boost::vertex_color, g); typename boost::graph_traitsGraph::vertex_iterator vi, v_end; for (boost::tie(vi, v_end) boost::vertices(g); vi ! v_end; vi) { if (boost::get(color, *vi) boost::white_color) { if (dfs_cycle_visit(*vi, g, color)) return true; } } return false; } int main() { Graph g(4); boost::add_edge(0, 1, g); boost::add_edge(1, 2, g); boost::add_edge(2, 0, g); // 回边构成环 boost::add_edge(1, 3, g); std::cout (has_cycle(g) ? has cycle : no cycle) \n; return 0; }顶点进入递归时染成灰色如果碰到一个灰色邻居说明它还在当前递归栈里这就是回边图里有环。全部邻居处理完才把当前顶点染成黑色。这个例子里颜色映射就是vertex_color_t背后的数据。如果没有它你只能自己再开一个unordered_map或vectorint效果一样但代码明显更啰嗦而且没法直接复用到 BGL 其他算法里。3. edge_reverse_t最大流算法的隐形半边天3.1 最大流为什么要“反向边”属性先想清楚一个问题在有向图上找最大流时如果某条路径选得不好算法怎么反悔答案是反向边。每次从 u 到 v 流过 f 单位的流量就可以认为从 v 到 u 存在一条容量为 f 的反向边表示这部分流量可以退回去。这样正反成对的边集合构成了残差网络。几乎所有最大流算法都需要从一条边迅速跳到它的反向边。如果不借助 BGL 机制你可能会用std::unordered_mapedge_descriptor, edge_descriptor来存映射每次增广的时候find一次。但 BGL 的算法模板是高度泛化的它不知道你的哈希表放在哪里于是 Boost 干脆把“反向边”定义为边的一个属性edge_reverse_t。算法内部通过get(edge_reverse, g, e)直接拿到反向边不用关心这个属性是存在图内部还是来自外部映射。3.2 edge_reverse_t 的具体含义edge_reverse_t属性的值类型是边描述符edge_descriptor也就是图上真实存在的另一条边。它表示当前这条边的反向搭档。因为在残差网络里每条边都有唯一反向边所以这个映射在设计上是成对对称的如果rev get(edge_reverse, g, e)那么get(edge_reverse, g, rev) e。在最大流问题的典型代码里图类型通常这样定义using Traits boost::adjacency_list_traitsboost::vecS, boost::vecS, boost::directedS; using Graph boost::adjacency_list boost::vecS, boost::vecS, boost::directedS, boost::propertyboost::vertex_color_t, boost::default_color_type, boost::propertyboost::edge_capacity_t, long, boost::propertyboost::edge_residual_capacity_t, long, boost::propertyboost::edge_reverse_t, Traits::edge_descriptor;这个类型看起来层层嵌套其实就是顶点带颜色边带三个属性——容量、剩余容量、反向边。edge_reverse_t是嵌套链的最后一环它的值类型是Traits::edge_descriptor。3.3 添加边的完整操作因为每条边都要有反向搭档我强烈建议封装成函数不要裸写add_edge。我早期在这个地方吃过不少亏漏一次put就会让算法给出错误结果。void add_edge_with_reverse(Graph g, int u, int v, long cap) { auto e boost::add_edge(u, v, g).first; auto rev boost::add_edge(v, u, g).first; boost::put(boost::edge_capacity, g, e, cap); boost::put(boost::edge_capacity, g, rev, 0); boost::put(boost::edge_reverse, g, e, rev); boost::put(boost::edge_reverse, g, rev, e); }注意反向边容量初始化成 0不是和正向边一样大。最大流算法在增广的时候会在正向边扣减容量、在反向边加回容量从而实现“撤销流量”。如果你把反向边容量也顺手设成一个不小的数残差网络就失真了结果往往会偏大。3.4 一次完整的 Edmonds-Karp 调用下面是一段完整的 Edmonds-Karp 最大流调用我选择显式传入全部参数避免依赖太深的默认行为#include boost/graph/adjacency_list.hpp #include boost/graph/edmonds_karp_max_flow.hpp #include iostream #include vector typedef boost::adjacency_list_traitsboost::vecS, boost::vecS, boost::directedS Traits; typedef boost::adjacency_list boost::vecS, boost::vecS, boost::directedS, boost::propertyboost::vertex_color_t, boost::default_color_type, boost::propertyboost::edge_capacity_t, long, boost::propertyboost::edge_residual_capacity_t, long, boost::propertyboost::edge_reverse_t, Traits::edge_descriptor Graph; void add_edge_with_reverse(Graph g, int u, int v, long cap) { auto e boost::add_edge(u, v, g).first; auto rev boost::add_edge(v, u, g).first; boost::put(boost::edge_capacity, g, e, cap); boost::put(boost::edge_capacity, g, rev, 0); boost::put(boost::edge_reverse, g, e, rev); boost::put(boost::edge_reverse, g, rev, e); } int main() { Graph g(4); add_edge_with_reverse(g, 0, 1, 3); add_edge_with_reverse(g, 0, 2, 2); add_edge_with_reverse(g, 1, 2, 1); add_edge_with_reverse(g, 1, 3, 2); add_edge_with_reverse(g, 2, 3, 4); std::vectorTraits::vertex_descriptor predecessor(4); auto pre_map boost::make_iterator_property_map( predecessor.begin(), boost::get(boost::vertex_index, g)); long flow boost::edmonds_karp_max_flow( g, 0, 3, boost::get(boost::edge_capacity, g), boost::get(boost::edge_residual_capacity, g), boost::get(boost::edge_reverse, g), pre_map, boost::get(boost::vertex_color, g)); std::cout max flow flow \n; return 0; }跑这个例子的结果应该是 5。你可以手动改容量验证把 0-2 的容量从 2 改成 20最大流也不会变 20因为瓶颈在 2-3 那条 4 的容量上。把edge_residual_capacity打印出来能很清楚看到每条边的流量分配。这个例子里的edge_reverse_t承担了算法内部的“反向跳转”职责而vertex_color_t则承担了 BFS 搜索增广路径时的访问状态记录。4. 这两个标签的常见误用和调试方法4.1 标签不是函数属性映射才是工具第一个高频误区把vertex_color_t当成一个能直接调用的对象。有人会写auto c boost::vertex_color_t();然后试图c(g)这当然不行。标签是类型属性映射是通过get(vertex_color, g)得到的对象。你可以把标签理解成“钥匙的类型”而get才是开锁动作。真正操作数据时你手里拿的永远是属性映射对象不是标签本身。4.2 属性缺失导致的长篇编译错误第二个高频坑是属性缺失。adjacency_listvecS, vecS, directedS默认只有vertex_index_t这种内部索引能自动得到颜色、容量、反向边这些属性都不会凭空冒出来。直接对这种默认图调用breadth_first_search或edmonds_karp_max_flow的简洁重载模板展开到一半就卡在get(vertex_color, g)或get(edge_reverse, g)上。报错会很长因为模板嵌套太深头部看不到关键信息。但耐心翻到末尾一般能看到类似no matching function for call to get(vertex_color_t, Graph)的提示。处理办法有两种第一种是在图类型上补内部属性第二种是改用外部属性映射并调用带完整参数的算法重载。对快速验证算法内部属性成本最低。4.3 内部属性还是外部属性映射下表是我在实际项目中的选择标准方案优点缺点内部属性写法简单算法默认能找到图类型写起来很长换属性类型要改模板参数外部属性映射不侵入图类型同一张图可绑不同映射每个算法都要显式传映射漏传就编译失败我的建议示例代码和算法实验用内部属性生产环境里如果图类型已经很大很复杂优先用外部映射把颜色、容量这些算法临时数据和业务数据分开。尤其是颜色它只是算法运行时的状态长期占用每个顶点的存储并不划算。4.4 调试 edge_reverse 成对性的小技巧最大流结果不对先别急着怀疑算法先去检查edge_reverse是否成对。一个非常有效的自检代码是遍历所有边for (auto e : boost::make_iterator_range(boost::edges(g))) { auto rev boost::get(boost::edge_reverse, g, e); if (boost::get(boost::edge_reverse, g, rev) ! e) { std::cerr edge_reverse not symmetric for edge e \n; } }如果打印出对称性错误说明建图时把反向关系接错了。还有一种情况是edge_reverse虽然成对但反向边的容量没有初始化为 0导致算法在反向边上“凭空增广”。调试时把每条边的容量、剩余容量和反向边一起打印出来会省下好几个小时。5. 从例子到生产代码我踩过的坑与建议5.1 在 reverse_graph 上读 edge_reverse_t 的正确姿势boost::reverse_graphGraph会把有向图所有边反转常用来把需要反向图的问题统一到正向图接口上。但注意reverse_graph的边描述符并不是你原始图里的 edge_descriptor而是一个包装类型可以理解为“原边 是否反转”的组合。所以get(edge_reverse, rg, e)返回的是 reverse_graph 自己域的边描述符不是原始图的边描述符。如果你想把反向图里的边映射回原图需要先把原始边描述符保存下来不能指望edge_reverse_t帮你跨图域转换。我踩过的坑是在reverse_graph上跑最大流算法误以为拿到的edge_reverse能和原图边直接比较结果类型都对不上编译直接断在operator!。正确做法是能不用reverse_graph就别用需要用的时候明确区分两个图域的描述符。必要时使用boost::graph_traitsreverse_graphGraph::edge_descriptor作为存储类型。5.2 大图上 vecS 和 listS 对这两个标签的影响vecS顶点容器自带连续索引但删除顶点会导致后续顶点索引前移原来按索引映射的颜色、前驱等数据全部错位。edge_reverse_t存的是边描述符如果你频繁增删边vecS的边描述符也可能失效。相比之下listS更稳定但默认没有vertex_index_t很多算法又依赖索引需要你手动用外部属性提供。我的经验是如果图规模固定、只建一次用vecS最舒服如果图会动态增删且要反复计算最大流优先考虑listS加手工维护的vertex_index_t并且不要在算法运行期间删除边。否则edge_reverse_t指向的边描述符可能在你不知道的时候变成悬垂描述符调试起来非常痛苦。5.3 给后来者的三句话经验第一先把图类型的属性集合想清楚再写算法。很多看起来玄学的编译报错根因就是少写了一个vertex_color_t或edge_reverse_t。第二把“加边并接反向边”封装成一个独立函数这是成本最低的防错手段。第三遇到弄不清楚的属性时直接打开boost/graph/properties.hpp和boost/graph/reverse_graph.hpp读定义比在网上翻二手中文资料快得多。最后分享一个我现在的固定习惯任何使用 BGL 最大流算法的新代码我都会先写一个几十行的最小图手动算一遍最大流把结果和手算对上才开始接真实数据。这个习惯救了我很多次。edge_reverse_t和vertex_color_t虽然只是不起眼的小标签但真正理解它们之后你再去看最大流、二分图匹配、连通分量这些算法的源码会发现整体逻辑一下子通透了很多。
