Boost Graph 最大流算法找出最小 S/T 切割上的弧
Boost Graph max-flow algorithm to find out the arcs on the minimal S/T cut
我有一个应用程序，其中对于给定的固定数量的顶点，需要求解从给定的固定源 (S) 到给定的固定汇 (T) 的大量不同的最大流算法。每个最大流问题的不同之处在于，有向弧本身会随着容量的变化而变化。例如，见下文。
顶点数保持不变，但实际弧及其容量因问题而异。
我有以下代码，因此使用 boost 迭代地解决了上图中图 1 和图 2 的最大流量问题（对文字墙表示歉意，我已尝试使其尽可能小。下面的代码在我的 linux box 上完全可以在 g++ 上编译，但我无法在 wandbox 等在线编译器上正确编译）：
#include <boost/config.hpp>
#include <iostream>
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/boykov_kolmogorov_max_flow.hpp>
using namespace boost;
typedef adjacency_list_traits<vecS, vecS, directedS> Traits;
typedef adjacency_list<
vecS, vecS, directedS,
property<
vertex_name_t, std::string,
property<vertex_index_t, int,
property<vertex_color_t, boost::default_color_type,
property<vertex_distance_t, double,
property<vertex_predecessor_t, Traits::edge_descriptor>
> > > >,
property<
edge_index_t, int,
property<edge_capacity_t, double,
property<edge_weight_t, double,
property<edge_residual_capacity_t, double,
property<edge_reverse_t, Traits::edge_descriptor>
> > > > >
Graph;
Graph g;
property_map<Graph, edge_index_t>::type e;
property_map<Graph, edge_capacity_t>::type cap;
property_map<Graph, edge_weight_t>::type cost;
property_map<Graph, edge_residual_capacity_t>::type rescap;
property_map<Graph, edge_reverse_t>::type rev;
property_map<Graph, vertex_color_t>::type colors;
void initialize(int nnodes) {
e = get(edge_index, g);
cap = get(edge_capacity, g);
cost = get(edge_weight, g);
rescap = get(edge_residual_capacity, g);
rev = get(edge_reverse, g);
colors = get(vertex_color, g);
for(int i = 0; i < nnodes; i++)
add_vertex(g);
}
void clearedges() {
Graph::vertex_iterator v, vend;
for (boost::tie(v, vend) = vertices(g); v != vend; ++v)
boost::clear_out_edges(*v, g);
}
void createedges(std::vector<std::pair<int, int>>& arcs, std::vector<double>& capacity) {
Traits::edge_descriptor edf, edr;//forward and reverse
for (int eindex = 0, sz = static_cast<int>(arcs.size()); eindex < sz; eindex++) {
int fr, to;
fr = arcs[eindex].first;
to = arcs[eindex].second;
edf = add_edge(fr, to, g).first;
edr = add_edge(to, fr, g).first;
e[edf] = 2 * eindex;
e[edr] = e[edf] + 1;
cap[edf] = capacity[eindex];
cap[edr] = capacity[eindex];
rev[edf] = edr;
rev[edr] = edf;
}
}
double solve_max_flow(int s, int t) {
double retval = boykov_kolmogorov_max_flow(g, s, t);
return retval;
}
bool is_part_of_source(int i) {
if (colors[i] == boost::black_color)
return true;
return false;
}
int main() {
initialize(6);
std::vector<std::pair<int, int>> arcs1 = { std::make_pair<int,int>(0,1),
std::make_pair<int,int>(0,2),
std::make_pair<int,int>(1,2),
std::make_pair<int,int>(1,3),
std::make_pair<int,int>(1,4),
std::make_pair<int,int>(2,4),
std::make_pair<int,int>(3,4),
std::make_pair<int,int>(3,5),
std::make_pair<int,int>(4,5)
};
std::vector<double> capacities1 = { 10, 10, 10, 10, 1, 4, 3, 2, 10 };
clearedges();
createedges(arcs1, capacities1);
double maxflow = solve_max_flow(0, 5);
printf("max flow is %f\n", maxflow);
for (int i = 0; i < 6; i++)
if (is_part_of_source(i))
printf("Node %d belongs to subset source is in\n", i);
Graph::edge_iterator e_, eend_;
int Eindex = 0;
for (boost::tie(e_, eend_) = edges(g); e_ != eend_; ++e_) {
int fr = source(*e_, g);
int to = target(*e_, g);
printf("(%d) Edge %d: (%d -> %d), capacity %f\n", Eindex, e[*e_], fr, to, cap[*e_]);
Eindex++;
if (is_part_of_source(fr) && is_part_of_source(to) == false)
printf("----is part of ST Cut-----\n");
else
printf("x\n");
}
std::vector<std::pair<int, int>> arcs2 = { std::make_pair<int,int>(0,1),
std::make_pair<int,int>(0,2),
std::make_pair<int,int>(1,3),
std::make_pair<int,int>(2,4),
std::make_pair<int,int>(3,5),
std::make_pair<int,int>(4,5)
};
std::vector<double> capacities2 = { 10, 10, 10, 4, 2, 0 };
clearedges();
createedges(arcs2, capacities2);
maxflow = solve_max_flow(0, 5);
printf("max flow is %f\n", maxflow);
for (int i = 0; i < 6; i++)
if (is_part_of_source(i))
printf("Node %d belongs to subset source is in\n", i);
Eindex = 0;
for (boost::tie(e_, eend_) = edges(g); e_ != eend_; ++e_) {
int fr = source(*e_, g);
int to = target(*e_, g);
printf("(%d) Edge %d: (%d -> %d), capacity %f\n", Eindex, e[*e_], fr, to, cap[*e_]);
Eindex++;
if (is_part_of_source(fr) && is_part_of_source(to) == false)
printf("----is part of ST Cut-----\n");
else
printf("x\n");
}
getchar();
}
我有以下问题。
(a) 如果底层顶点保持固定，但只有弧和它们的容量在迭代之间发生变化，有什么比使用 clear_out_edges 清除弧然后使用 [=14= 更快的方法吗？ ] 添加具有新容量的新弧线？此外，clear_out_edges 是否也正确地清除了 属性 可能具有刚刚删除的边描述符作为键的映射条目？
(b) Boost max-flow 算法似乎想要显式添加反向弧。截至目前，在函数 createedges 中，我通过前向边缘描述符 (edf) 和反向边缘描述符 (edr) 明确地执行此操作。这是否有任何性能损失，尤其是当需要解决的最大流量问题数量在 1000 多个时？还有比这更高效的吗？
(c) 我能够通过以下代码部分正确枚举最小 S/T 切割的弧线：
int Eindex = 0;
for (boost::tie(e_, eend_) = edges(g); e_ != eend_; ++e_) {
int fr = source(*e_, g);
int to = target(*e_, g);
printf("(%d) Edge %d: (%d -> %d), capacity %f\n", Eindex, e[*e_], fr, to, cap[*e_]);
Eindex++;
if (is_part_of_source(fr) && is_part_of_source(to) == false)
printf("----is part of ST Cut-----\n");
else
printf("x\n");
}
有没有比上面更有效的方法或枚举S/T切割的弧线？
有很多问题。如果您使用现代 C++ 和编译器警告，您可以减少代码并发现打印顶点描述符中的错误（printf 不安全；使用诊断程序！）。
这是我的评论。
显着变化：
捆绑属性而不是单独的内部属性
这意味着传递命名参数（但请参阅 ）
没有更多的全局变量，如果简单的构造函数就足够了，就没有更多的循环初始化
不再有重复代码（没有什么比 capacity1 和 capacity2 随处可见更容易引起错误的了）
使用 clear_vertex 而不是 clear_out_edges - 这可能没有什么不同 (?) 但似乎表达意图更好一些
不再有 printf（我将使用 libfmt，它也在 c++23 中），所以例如
fmt::print("Max flow {}\nNodes {} are in source subset\n", maxflow,
vertices(_g) | filtered(is_source));
打印
Max flow 10
Nodes {0, 1, 2, 3} are in source subset
一气呵成
打印您认为正在打印的内容。特别是，如果可以的话，使用库支持打印边缘
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/boykov_kolmogorov_max_flow.hpp>
#include <boost/range/adaptors.hpp>
#include <fmt/ostream.h>
#include <fmt/ranges.h>
using boost::adaptors::filtered;
using Traits = boost::adjacency_list_traits<boost::vecS, boost::vecS, boost::directedS>;
using V = Traits::vertex_descriptor;
using E = Traits::edge_descriptor;
using Capacity = double;
using Color = boost::default_color_type;
struct VertexProps {
// std::string name;
Color color;
Capacity distance;
E predecessor;
};
struct EdgeProps {
int id;
Capacity weight, residual;
E reverse;
};
using Graph = boost::adjacency_list<
boost::vecS, boost::vecS, boost::directedS,
VertexProps,
// see :(
boost::property<boost::edge_capacity_t, Capacity, EdgeProps>>;
struct MyGraph {
MyGraph(size_t nnodes) : _g(nnodes) {}
void runSimulation(auto const& arcs, auto const& capacities)
{
reconfigure(arcs, capacities);
Capacity maxflow = solve_max_flow(0, 5);
auto cap = get(boost::edge_capacity, _g);
auto is_source = [this](V v) { return _g[v].color == Color::black_color; };
fmt::print("Max flow {}\nNodes {} are in source subset\n", maxflow,
vertices(_g) | filtered(is_source));
for (E e : boost::make_iterator_range(edges(_g))) {
bool st_cut =
is_source(source(e, _g)) and
not is_source(target(e, _g));
fmt::print("Edge {} (id #{:2}), capacity {:3} {}\n", e, _g[e].id,
cap[e], st_cut ? "(ST Cut)" : "");
}
}
private:
Graph _g;
void reconfigure(auto const& arcs, auto const& capacities)
{
assert(arcs.size() == capacities.size());
for (auto v : boost::make_iterator_range(vertices(_g))) {
// boost::clear_out_edges(v, g);
boost::clear_vertex(v, _g);
}
auto cap = get(boost::edge_capacity, _g);
auto eidx = get(&EdgeProps::id, _g);
auto rev = get(&EdgeProps::reverse, _g);
auto eindex = 0;
for (auto [fr, to] : arcs) {
auto edf = add_edge(fr, to, _g).first;
auto edr = add_edge(to, fr, _g).first;
eidx[edf] = 2 * eindex;
eidx[edr] = eidx[edf] + 1;
cap[edf] = cap[edr] = capacities[eindex];
rev[edf] = edr;
rev[edr] = edf;
++eindex;
}
}
Capacity solve_max_flow(V src, V sink)
{
return boykov_kolmogorov_max_flow(
_g, src, sink,
// named arguments
boost::reverse_edge_map(get(&EdgeProps::reverse, _g))
.residual_capacity_map(get(&EdgeProps::residual, _g))
.vertex_color_map(get(&VertexProps::color, _g))
.predecessor_map(get(&VertexProps::predecessor, _g))
.distance_map(get(&VertexProps::distance, _g))
// end named arguments
);
}
};
int main() {
MyGraph g{6};
using namespace std;
for (auto&& [arcs, capacities] : { tuple
// 1
{vector{pair{0, 1}, {0, 2}, {1, 2}, {1, 3}, {1, 4},
{2, 4}, {3, 4}, {3, 5}, {4, 5}},
vector{10, 10, 10, 10, 1, 4, 3, 2, 10}},
// 2
{vector{pair{0, 1}, {0, 2}, {1, 3}, {2, 4}, {3, 5}, {4, 5}},
vector{10, 10, 10, 4, 2, 0}},
})
{
g.runSimulation(arcs, capacities);
}
}
版画
Max flow 10
Nodes {0, 1, 2, 3} are in source subset
Edge (0,1) (id # 0), capacity 10
Edge (0,2) (id # 2), capacity 10
Edge (1,0) (id # 1), capacity 10
Edge (1,2) (id # 4), capacity 10
Edge (1,3) (id # 6), capacity 10
Edge (1,4) (id # 8), capacity 1 (ST Cut)
Edge (2,0) (id # 3), capacity 10
Edge (2,1) (id # 5), capacity 10
Edge (2,4) (id #10), capacity 4 (ST Cut)
Edge (3,1) (id # 7), capacity 10
Edge (3,4) (id #12), capacity 3 (ST Cut)
Edge (3,5) (id #14), capacity 2 (ST Cut)
Edge (4,1) (id # 9), capacity 1
Edge (4,2) (id #11), capacity 4
Edge (4,3) (id #13), capacity 3
Edge (4,5) (id #16), capacity 10
Edge (5,3) (id #15), capacity 2
Edge (5,4) (id #17), capacity 10
Max flow 2
Nodes {0, 1, 2, 3, 4} are in source subset
Edge (0,1) (id # 0), capacity 10
Edge (0,2) (id # 2), capacity 10
Edge (1,0) (id # 1), capacity 10
Edge (1,3) (id # 4), capacity 10
Edge (2,0) (id # 3), capacity 10
Edge (2,4) (id # 6), capacity 4
Edge (3,1) (id # 5), capacity 10
Edge (3,5) (id # 8), capacity 2 (ST Cut)
Edge (4,2) (id # 7), capacity 4
Edge (4,5) (id #10), capacity 0 (ST Cut)
Edge (5,3) (id # 9), capacity 2
Edge (5,4) (id #11), capacity 0
旁注
如果您认为 main 过于复杂，这里有另一种只为两次调用编写它的方法：
g.runSimulation({{0, 1}, {0, 2}, {1, 2}, {1, 3}, {1, 4}, {2, 4}, {3, 4}, {3, 5}, {4, 5}},
{10, 10, 10, 10, 1, 4, 3, 2, 10});
g.runSimulation({{0, 1}, {0, 2}, {1, 3}, {2, 4}, {3, 5}, {4, 5}},
{10, 10, 10, 4, 2, 0});
我有一个应用程序，其中对于给定的固定数量的顶点，需要求解从给定的固定源 (S) 到给定的固定汇 (T) 的大量不同的最大流算法。每个最大流问题的不同之处在于，有向弧本身会随着容量的变化而变化。例如，见下文。
顶点数保持不变，但实际弧及其容量因问题而异。
我有以下代码，因此使用 boost 迭代地解决了上图中图 1 和图 2 的最大流量问题（对文字墙表示歉意，我已尝试使其尽可能小。下面的代码在我的 linux box 上完全可以在 g++ 上编译，但我无法在 wandbox 等在线编译器上正确编译）：
#include <boost/config.hpp>
#include <iostream>
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/boykov_kolmogorov_max_flow.hpp>
using namespace boost;
typedef adjacency_list_traits<vecS, vecS, directedS> Traits;
typedef adjacency_list<
vecS, vecS, directedS,
property<
vertex_name_t, std::string,
property<vertex_index_t, int,
property<vertex_color_t, boost::default_color_type,
property<vertex_distance_t, double,
property<vertex_predecessor_t, Traits::edge_descriptor>
> > > >,
property<
edge_index_t, int,
property<edge_capacity_t, double,
property<edge_weight_t, double,
property<edge_residual_capacity_t, double,
property<edge_reverse_t, Traits::edge_descriptor>
> > > > >
Graph;
Graph g;
property_map<Graph, edge_index_t>::type e;
property_map<Graph, edge_capacity_t>::type cap;
property_map<Graph, edge_weight_t>::type cost;
property_map<Graph, edge_residual_capacity_t>::type rescap;
property_map<Graph, edge_reverse_t>::type rev;
property_map<Graph, vertex_color_t>::type colors;
void initialize(int nnodes) {
e = get(edge_index, g);
cap = get(edge_capacity, g);
cost = get(edge_weight, g);
rescap = get(edge_residual_capacity, g);
rev = get(edge_reverse, g);
colors = get(vertex_color, g);
for(int i = 0; i < nnodes; i++)
add_vertex(g);
}
void clearedges() {
Graph::vertex_iterator v, vend;
for (boost::tie(v, vend) = vertices(g); v != vend; ++v)
boost::clear_out_edges(*v, g);
}
void createedges(std::vector<std::pair<int, int>>& arcs, std::vector<double>& capacity) {
Traits::edge_descriptor edf, edr;//forward and reverse
for (int eindex = 0, sz = static_cast<int>(arcs.size()); eindex < sz; eindex++) {
int fr, to;
fr = arcs[eindex].first;
to = arcs[eindex].second;
edf = add_edge(fr, to, g).first;
edr = add_edge(to, fr, g).first;
e[edf] = 2 * eindex;
e[edr] = e[edf] + 1;
cap[edf] = capacity[eindex];
cap[edr] = capacity[eindex];
rev[edf] = edr;
rev[edr] = edf;
}
}
double solve_max_flow(int s, int t) {
double retval = boykov_kolmogorov_max_flow(g, s, t);
return retval;
}
bool is_part_of_source(int i) {
if (colors[i] == boost::black_color)
return true;
return false;
}
int main() {
initialize(6);
std::vector<std::pair<int, int>> arcs1 = { std::make_pair<int,int>(0,1),
std::make_pair<int,int>(0,2),
std::make_pair<int,int>(1,2),
std::make_pair<int,int>(1,3),
std::make_pair<int,int>(1,4),
std::make_pair<int,int>(2,4),
std::make_pair<int,int>(3,4),
std::make_pair<int,int>(3,5),
std::make_pair<int,int>(4,5)
};
std::vector<double> capacities1 = { 10, 10, 10, 10, 1, 4, 3, 2, 10 };
clearedges();
createedges(arcs1, capacities1);
double maxflow = solve_max_flow(0, 5);
printf("max flow is %f\n", maxflow);
for (int i = 0; i < 6; i++)
if (is_part_of_source(i))
printf("Node %d belongs to subset source is in\n", i);
Graph::edge_iterator e_, eend_;
int Eindex = 0;
for (boost::tie(e_, eend_) = edges(g); e_ != eend_; ++e_) {
int fr = source(*e_, g);
int to = target(*e_, g);
printf("(%d) Edge %d: (%d -> %d), capacity %f\n", Eindex, e[*e_], fr, to, cap[*e_]);
Eindex++;
if (is_part_of_source(fr) && is_part_of_source(to) == false)
printf("----is part of ST Cut-----\n");
else
printf("x\n");
}
std::vector<std::pair<int, int>> arcs2 = { std::make_pair<int,int>(0,1),
std::make_pair<int,int>(0,2),
std::make_pair<int,int>(1,3),
std::make_pair<int,int>(2,4),
std::make_pair<int,int>(3,5),
std::make_pair<int,int>(4,5)
};
std::vector<double> capacities2 = { 10, 10, 10, 4, 2, 0 };
clearedges();
createedges(arcs2, capacities2);
maxflow = solve_max_flow(0, 5);
printf("max flow is %f\n", maxflow);
for (int i = 0; i < 6; i++)
if (is_part_of_source(i))
printf("Node %d belongs to subset source is in\n", i);
Eindex = 0;
for (boost::tie(e_, eend_) = edges(g); e_ != eend_; ++e_) {
int fr = source(*e_, g);
int to = target(*e_, g);
printf("(%d) Edge %d: (%d -> %d), capacity %f\n", Eindex, e[*e_], fr, to, cap[*e_]);
Eindex++;
if (is_part_of_source(fr) && is_part_of_source(to) == false)
printf("----is part of ST Cut-----\n");
else
printf("x\n");
}
getchar();
}
我有以下问题。
(a) 如果底层顶点保持固定，但只有弧和它们的容量在迭代之间发生变化，有什么比使用 clear_out_edges 清除弧然后使用 [=14= 更快的方法吗？ ] 添加具有新容量的新弧线？此外，clear_out_edges 是否也正确地清除了 属性 可能具有刚刚删除的边描述符作为键的映射条目？
(b) Boost max-flow 算法似乎想要显式添加反向弧。截至目前，在函数 createedges 中，我通过前向边缘描述符 (edf) 和反向边缘描述符 (edr) 明确地执行此操作。这是否有任何性能损失，尤其是当需要解决的最大流量问题数量在 1000 多个时？还有比这更高效的吗？
(c) 我能够通过以下代码部分正确枚举最小 S/T 切割的弧线：
int Eindex = 0;
for (boost::tie(e_, eend_) = edges(g); e_ != eend_; ++e_) {
int fr = source(*e_, g);
int to = target(*e_, g);
printf("(%d) Edge %d: (%d -> %d), capacity %f\n", Eindex, e[*e_], fr, to, cap[*e_]);
Eindex++;
if (is_part_of_source(fr) && is_part_of_source(to) == false)
printf("----is part of ST Cut-----\n");
else
printf("x\n");
}
有没有比上面更有效的方法或枚举S/T切割的弧线？
有很多问题。如果您使用现代 C++ 和编译器警告，您可以减少代码并发现打印顶点描述符中的错误（printf 不安全；使用诊断程序！）。
这是我的评论。
显着变化：
捆绑属性而不是单独的内部属性
这意味着传递命名参数（但请参阅
没有更多的全局变量，如果简单的构造函数就足够了，就没有更多的循环初始化
不再有重复代码（没有什么比 capacity1 和 capacity2 随处可见更容易引起错误的了）
使用
clear_vertex而不是clear_out_edges- 这可能没有什么不同 (?) 但似乎表达意图更好一些不再有 printf（我将使用 libfmt，它也在 c++23 中），所以例如
fmt::print("Max flow {}\nNodes {} are in source subset\n", maxflow, vertices(_g) | filtered(is_source));打印
Max flow 10 Nodes {0, 1, 2, 3} are in source subset一气呵成
打印您认为正在打印的内容。特别是，如果可以的话，使用库支持打印边缘
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/boykov_kolmogorov_max_flow.hpp>
#include <boost/range/adaptors.hpp>
#include <fmt/ostream.h>
#include <fmt/ranges.h>
using boost::adaptors::filtered;
using Traits = boost::adjacency_list_traits<boost::vecS, boost::vecS, boost::directedS>;
using V = Traits::vertex_descriptor;
using E = Traits::edge_descriptor;
using Capacity = double;
using Color = boost::default_color_type;
struct VertexProps {
// std::string name;
Color color;
Capacity distance;
E predecessor;
};
struct EdgeProps {
int id;
Capacity weight, residual;
E reverse;
};
using Graph = boost::adjacency_list<
boost::vecS, boost::vecS, boost::directedS,
VertexProps,
// see :(
boost::property<boost::edge_capacity_t, Capacity, EdgeProps>>;
struct MyGraph {
MyGraph(size_t nnodes) : _g(nnodes) {}
void runSimulation(auto const& arcs, auto const& capacities)
{
reconfigure(arcs, capacities);
Capacity maxflow = solve_max_flow(0, 5);
auto cap = get(boost::edge_capacity, _g);
auto is_source = [this](V v) { return _g[v].color == Color::black_color; };
fmt::print("Max flow {}\nNodes {} are in source subset\n", maxflow,
vertices(_g) | filtered(is_source));
for (E e : boost::make_iterator_range(edges(_g))) {
bool st_cut =
is_source(source(e, _g)) and
not is_source(target(e, _g));
fmt::print("Edge {} (id #{:2}), capacity {:3} {}\n", e, _g[e].id,
cap[e], st_cut ? "(ST Cut)" : "");
}
}
private:
Graph _g;
void reconfigure(auto const& arcs, auto const& capacities)
{
assert(arcs.size() == capacities.size());
for (auto v : boost::make_iterator_range(vertices(_g))) {
// boost::clear_out_edges(v, g);
boost::clear_vertex(v, _g);
}
auto cap = get(boost::edge_capacity, _g);
auto eidx = get(&EdgeProps::id, _g);
auto rev = get(&EdgeProps::reverse, _g);
auto eindex = 0;
for (auto [fr, to] : arcs) {
auto edf = add_edge(fr, to, _g).first;
auto edr = add_edge(to, fr, _g).first;
eidx[edf] = 2 * eindex;
eidx[edr] = eidx[edf] + 1;
cap[edf] = cap[edr] = capacities[eindex];
rev[edf] = edr;
rev[edr] = edf;
++eindex;
}
}
Capacity solve_max_flow(V src, V sink)
{
return boykov_kolmogorov_max_flow(
_g, src, sink,
// named arguments
boost::reverse_edge_map(get(&EdgeProps::reverse, _g))
.residual_capacity_map(get(&EdgeProps::residual, _g))
.vertex_color_map(get(&VertexProps::color, _g))
.predecessor_map(get(&VertexProps::predecessor, _g))
.distance_map(get(&VertexProps::distance, _g))
// end named arguments
);
}
};
int main() {
MyGraph g{6};
using namespace std;
for (auto&& [arcs, capacities] : { tuple
// 1
{vector{pair{0, 1}, {0, 2}, {1, 2}, {1, 3}, {1, 4},
{2, 4}, {3, 4}, {3, 5}, {4, 5}},
vector{10, 10, 10, 10, 1, 4, 3, 2, 10}},
// 2
{vector{pair{0, 1}, {0, 2}, {1, 3}, {2, 4}, {3, 5}, {4, 5}},
vector{10, 10, 10, 4, 2, 0}},
})
{
g.runSimulation(arcs, capacities);
}
}
版画
Max flow 10
Nodes {0, 1, 2, 3} are in source subset
Edge (0,1) (id # 0), capacity 10
Edge (0,2) (id # 2), capacity 10
Edge (1,0) (id # 1), capacity 10
Edge (1,2) (id # 4), capacity 10
Edge (1,3) (id # 6), capacity 10
Edge (1,4) (id # 8), capacity 1 (ST Cut)
Edge (2,0) (id # 3), capacity 10
Edge (2,1) (id # 5), capacity 10
Edge (2,4) (id #10), capacity 4 (ST Cut)
Edge (3,1) (id # 7), capacity 10
Edge (3,4) (id #12), capacity 3 (ST Cut)
Edge (3,5) (id #14), capacity 2 (ST Cut)
Edge (4,1) (id # 9), capacity 1
Edge (4,2) (id #11), capacity 4
Edge (4,3) (id #13), capacity 3
Edge (4,5) (id #16), capacity 10
Edge (5,3) (id #15), capacity 2
Edge (5,4) (id #17), capacity 10
Max flow 2
Nodes {0, 1, 2, 3, 4} are in source subset
Edge (0,1) (id # 0), capacity 10
Edge (0,2) (id # 2), capacity 10
Edge (1,0) (id # 1), capacity 10
Edge (1,3) (id # 4), capacity 10
Edge (2,0) (id # 3), capacity 10
Edge (2,4) (id # 6), capacity 4
Edge (3,1) (id # 5), capacity 10
Edge (3,5) (id # 8), capacity 2 (ST Cut)
Edge (4,2) (id # 7), capacity 4
Edge (4,5) (id #10), capacity 0 (ST Cut)
Edge (5,3) (id # 9), capacity 2
Edge (5,4) (id #11), capacity 0
旁注
如果您认为 main 过于复杂，这里有另一种只为两次调用编写它的方法：
g.runSimulation({{0, 1}, {0, 2}, {1, 2}, {1, 3}, {1, 4}, {2, 4}, {3, 4}, {3, 5}, {4, 5}},
{10, 10, 10, 10, 1, 4, 3, 2, 10});
g.runSimulation({{0, 1}, {0, 2}, {1, 3}, {2, 4}, {3, 5}, {4, 5}},
{10, 10, 10, 4, 2, 0});