基于C++ Boost库计算含平行/反平行弧的图的最小s-t割问题咨询

先纠正：Boost库本身支持这类图，问题大概率出在图构造 #

你测试的Boost最大流算法（push_relabel_max_flow、boykov_kolmogorov_max_flow等）原生支持平行弧和反平行弧，无法处理的原因通常是图的构造方式错误：

• 若使用boost::adjacency_list时，边容器选择了setS（默认去重），会自动合并平行弧，导致算法无法识别多条边；
• 未正确使用支持多重边的容器配置。

正确的Boost图构造示例 #

使用支持多重边的边容器（如vecS），多次调用add_edge添加平行弧，反平行弧直接添加双向边即可：

#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/push_relabel_max_flow.hpp>

// 定义支持残差网络的有向图，允许多重边
typedef boost::adjacency_list<
    boost::vecS,                // 边容器：允许多重边
    boost::vecS,                // 顶点容器
    boost::directedS,           // 有向图
    boost::no_property,         // 顶点属性
    boost::property<            // 边属性：容量 + 反向边
        boost::edge_capacity_t, int,
        boost::property<boost::edge_reverse_t, boost::graph_traits<boost::adjacency_list<boost::vecS, boost::vecS, boost::directedS>>::edge_descriptor>
    >
> Graph;
typedef boost::graph_traits<Graph>::edge_descriptor Edge;

int main() {
    Graph g(4); // 初始化4个顶点
    auto capacity_map = boost::get(boost::edge_capacity, g);
    auto reverse_edge_map = boost::get(boost::edge_reverse, g);

    // 添加平行弧：顶点0→1，两条容量分别为3、5的边
    Edge e; bool success;
    boost::tie(e, success) = boost::add_edge(0, 1, g);
    capacity_map[e] = 3;
    boost::tie(e, success) = boost::add_edge(0, 1, g);
    capacity_map[e] = 5;

    // 添加反平行弧：顶点0→2（容量4）和顶点2→0（容量2）
    boost::tie(e, success) = boost::add_edge(0, 2, g);
    capacity_map[e] = 4;
    boost::tie(e, success) = boost::add_edge(2, 0, g);
    capacity_map[e] = 2;

    // 计算s=0到t=3的最大流（等于最小割容量）
    int max_flow = boost::push_relabel_max_flow(g, 0, 3);
    // 后续可通过残差容量划分s-t割集
    return 0;
}

替代库推荐 #

如果确实需要更换库，以下选项原生支持平行/反平行弧的最大流计算：

• LEMON库：C++图算法专用库，API简洁，内置Dinic、Edmonds-Karp等多种最大流算法，对多重边和任意有向边结构支持完善；
• NetworkX（Python）：适合快速原型验证，nx.max_flow函数（基于Edmonds-Karp或Dinic）直接支持平行弧，只需多次调用add_edge添加同起点终点的边；
• 自行实现Dinic算法：Dinic的核心逻辑不限制平行/反平行弧，只需在邻接表中为每个节点存储所有出边（包括多条同方向边和反向边），实现难度低，可控性强。

内容的提问来源于stack exchange，提问作者CookieMonster98