我一直在努力弄清楚如何做到这一点.我对快速找到图形的割集很感兴趣.我知道 BGL 支持通过迭代来查找割集,例如 edmonds_karp_max_flow 支持的 colorMap 参数.Gomory Hu 算法需要多次调用最小割算法.
我希望得到的结果是一个多图,其中包含:(颜色,顶点)
以下代码尝试重写 Boost Graph 库中的示例,以将多重映射用于 associative_property_map.可以通过以下方式编译代码:铛 -lboost_graph -o edmonds_karp edmonds_karp.cpp或 g++ 而不是 clang.我不明白由此产生的错误.
#include #include #include <字符串>#include #include #include <boost/graph/edmonds_karp_max_flow.hpp>#include #include #include #include #include int main(){使用命名空间提升;typedef adjacency_list_traits <vecS, vecS, 定向 >性状;typedef adjacency_list <列表、向量、定向、财产vertex_name_t, std::string >,财产edge_capacity_t,长,财产edge_residual_capacity_t,长,财产edge_reverse_t, Traits::edge_descriptor >>>>图形;图g;property_map <图,edge_capacity_t >::type容量 = 获取(边缘容量,g);property_map <图,edge_reverse_t >::type rev = get(edge_reverse, g);property_map <图,edge_residual_capacity_t >::type剩余容量 = 获取(边缘剩余容量,g);std::multimap颜色图;boost::associative_property_map<std::map>颜色图(颜色图);特性::vertex_descriptor s, t;read_dimacs_max_flow(g, 容量, rev, s, t);std::vectorpred(num_vertices(g));长流 = edmonds_karp_max_flow(g,s,t,容量,residual_capacity,rev,make_iterator_property_map(color_map.begin()),&pred[0]);std::cout <<"c 总流量:" <<std::endl;std::cout <<s"<<流量<<std::endl <<std::endl;std::cout <<c流量值:"<<std::endl;graph_traits <图 >::vertex_iterator u_iter, u_end;graph_traits <图 >::out_edge_iterator ei, e_end;for (boost::tie(u_iter, u_end) = vertices(g); u_iter != u_end; ++u_iter)for (boost::tie(ei, e_end) = out_edges(*u_iter, g); ei != e_end; ++ei)如果(容量[*ei] > 0)std::cout <<f"<<*u_iter<<" " <<目标(*ei,g)<<""<<(容量[*ei] - 残差容量[*ei])<