Consider the following original input graph on which the max flow algorithm is applied:
The following code (thanks to user sehe) compiles and runs fine and gives the correct output. Code is reproduced below for completion:
#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 preedcessor;
};
struct EdgeProps {
int id;
Capacity weight, residual;
E reverse;
};
using Graph = boost::adjacency_list<
boost::vecS, boost::vecS, boost::directedS,
VertexProps,
// see https://stackoverflow.com/a/64744086/85371 :(
boost::property<boost::edge_capacity_t, Capacity, EdgeProps>>;
struct MyGraph {
MyGraph(size_t nnodes) : _g(nnodes) {}
void runSimulation(std::vector<std::pair<V, V>> const& arcs,
std::vector<Capacity> const& capacities)
{
reconfigure(arcs, capacities);
Capacity maxflow = solve_max_flow(0, 3);
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::preedcessor, _g))
.distance_map(get(&VertexProps::distance, _g))
// end named arguments
);
}
};
int main() {
MyGraph g{4};
g.runSimulation({{0, 1}, {0, 2}, {1, 2}, {2, 1}, {1, 3}, {2, 3}},
{10, 1, 10, 1, 1, 10});
}
My questions relate particularly to arcs (1->2) and (2->1).
(a) Boost documentation for the max flow algorithm requires the user to explicitly provide the reverse arcs for each of the arcs in the original input graph. So, in the example above, the directed arcs (1 -> 2) and (2 -> 1) are added to the graph object twice in the following code snippet:
auto edf = add_edge(fr, to, _g).first; //Arc (1->2) added, Arc (2->1) added
auto edr = add_edge(to, fr, _g).first; //Arc (2->1) added, Arc (1->2) added
eidx[edf] = 2 * eindex;
eidx[edr] = eidx[edf] + 1;
cap[edf] = cap[edr] = capacities[eindex];
rev[edf] = edr;
rev[edr] = edf;
While in this particular example the correctness of the solution could be seen, is this guaranteed in all cases? That is, can the repeated arc addition of the same arc multiple times (once as the forward arc, and once as the reverse arc) to the graph object cause any internal stuff to break in the boost algorithm for this problem?
(b) The boost documentation states the following:
Remarks: While the push-relabel method states that each edge in E^T has to have capacity of 0, the reverse edges for this algorithm ARE allowed to carry capacities. If there are already reverse edges in the input Graph G, those can be used. This can halve the amount of edges and will noticeably increase the performance.
Does this mean that in this particular case, when I add the forward arc (1->2), I need NOT explicitly add the reverse arc (2->1) and likewise when I add the forward arc (2->1), I need NOT explicitly add the reverse arc (1->2) as happened in the code snippet above?