In trying to solve the example problem provided on Boost's website: https://www.boost.org/doc/libs/1_54_0/libs/graph/example/boykov_kolmogorov-eg.cpp
(the code has to be run as <executable> < max_flow.dat where max_flow.dat comes along with boost installation at \boost\lib\graph\example\)
with the small change of displaying all flows by commenting out the line
if (capacity[*ei] > 0) provides the following output:
c The total flow:
s 13
c flow values:
f 0 6 3
f 0 1 6
f 0 2 4
f 0 1 0
f 0 2 0
f 1 0 -6
f 1 5 1
f 1 0 0
f 1 3 5
f 1 3 0
f 2 0 -4
f 2 4 4
f 2 3 0
f 2 0 0
f 2 3 0
f 3 1 -5
f 3 2 0
f 3 7 5
f 3 2 0
f 3 1 0
f 4 2 -4
f 4 5 0
f 4 6 4
f 4 5 0
f 4 6 0
f 5 1 -1
f 5 4 0
f 5 4 0
f 5 7 1
f 5 7 0
f 6 0 0
f 6 4 -4
f 6 7 7
f 6 4 0
f 6 7 0
f 7 3 -5
f 7 5 -1
f 7 6 -4
f 7 6 0
f 7 5 0
My questions are:
(1) Given the display loop:
graph_traits < Graph >::vertex_iterator u_iter, u_end;
graph_traits < Graph >::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)
cout << ...
Why are some arcs displayed multiple times in the output for e.g.,
f 6 4 -4
f 6 4 0
Are we not just iterating sequentially through each out edge of each vertex? So, where does the repetition come from?
(2) Focussing on, say, node 6, and nonzero flows to/from it, there are 3 inflows 0 -> 6 of 3, 4 -> 6 of 4 and 7 -> 6 of -4, and 2 outflows of 6 -> 4 of -4 and 6 -> 7 of 7. This leads me to believe that the net inflow (total incoming flow - total outgoing flow) is 0 for each node in the final optimal solution. Does the algorithm guarantee that the eventual flows produced by the algorithm [the paper is available here] will satisfy the requirement that the net inflow into a node, any node, in the graph will be 0? Related to this, what is the right "interpretation" of the flow from 7 -> 6 being -4 in the example above?
Cross posted on github also: https://github.com/boostorg/graph/issues/366
Q. (1) Given the display loop: Why are some arcs displayed multiple times in the output for e.g.,
The reverse edges are added (with capacity 0) in read_dimacs_max_flow, as required for the algorithm to work. The sample max_flow.dat contains both (4,6) and (6,4) with capacity 20.
This causes the respective reverse edges to appear with 0 capacity.
Note the file will refer to them as 5,7 respectively 7,5.
Q. Does the algorithm guarantee that the eventual flows produced by the algorithm [the paper is available here] will satisfy the requirement that the net inflow into a node, any node, in the graph will be 0?
Yes. See the documentation here: Network Flow Algorithms where it lists the three constraints on the flow function:
The third bullet codifies the constraint you were asking about.
Q. Related to this, what is the right "interpretation" of the flow from 7 -> 6 being -4 in the example above?
There is no interpretation. Edges with zero capacity will typically be reverse edges, which is why the output omits them altogether.
In my understanding, the residual capacity on such reverse edges is required as bookkeeping for the algorithm. I agree the reverse edge modeling and mapping feel like a leaky abstraction (implementation details), but I'm sure there's a historical reason/convention for implementations to do this (e.g. to stay close to the original algorithm papers).
Here's a toy program that shows you some more detail and checks invariants along the way, using more modern C++ so it's less hurtful to the eyes too:
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/boykov_kolmogorov_max_flow.hpp>
#include <boost/graph/read_dimacs.hpp>
#include <iostream>
#include <ranges>
#include <string>
namespace r = std::ranges;
namespace v = std::ranges::views;
using Traits = boost::adjacency_list_traits<boost::vecS, boost::vecS, boost::directedS>;
using Graph = boost::adjacency_list<
boost::vecS, boost::vecS, boost::directedS,
boost::property<
boost::vertex_name_t, std::string,
boost::property<boost::vertex_index_t, long,
boost::property<boost::vertex_color_t, boost::default_color_type,
boost::property<boost::vertex_distance_t, long,
boost::property<boost::vertex_predecessor_t,
Traits::edge_descriptor>>>>>,
boost::property<boost::edge_capacity_t, long,
boost::property<boost::edge_residual_capacity_t, long,
boost::property<boost::edge_reverse_t, Traits::edge_descriptor>>>>;
int main() {
using boost::make_iterator_range;
Graph g;
auto cap = get(boost::edge_capacity, g);
auto res_cap = get(boost::edge_residual_capacity, g);
auto rev = get(boost::edge_reverse, g);
Graph::vertex_descriptor s{}, t{};
read_dimacs_max_flow(g, cap, rev, s, t);
std::vector<boost::default_color_type> color(num_vertices(g));
std::vector<long> distance(num_vertices(g));
auto dump = [&g, cap, res_cap] {
std::cout << "c flow values:\n";
std::cout << "# s t" /*"\tcap\tres."*/ "\tflow\n";
for (auto u : make_iterator_range(vertices(g)))
for (auto e : make_iterator_range(out_edges(u, g)))
if (cap[e] > 0)
std::cout << "f " << u << " " << target(e, g) //
// << "\t" << cap[e] //
// << "\t" << res_cap[e] //
<< "\t" << (cap[e] - res_cap[e]) //
<< std::endl;
};
// std::cout << "# before\n";
// dump();
// pre-conditions, checks
auto const cap_vw = make_iterator_range(edges(g)) | v::transform([=](auto e) { return cap[e]; });
std::vector const saved_caps(cap_vw.begin(), cap_vw.end());
assert(r::none_of(make_iterator_range(edges(g)), [res_cap](auto e) { return res_cap[e]; }));
long flow = boykov_kolmogorov_max_flow(g, s, t);
std::cout << "# after\n";
std::cout << "c The total flow:" << std::endl;
std::cout << "s " << flow << std::endl << std::endl;
std::vector const result_caps(cap_vw.begin(), cap_vw.end());
// capacities never change, so filtering for cap[e]>0 filters on the input property
assert(saved_caps == result_caps);
dump();
}
Printing
# after
c The total flow:
s 13
c flow values:
# s t flow
f 0 6 3
f 0 1 6
f 0 2 4
f 1 5 1
f 1 0 0
f 1 3 5
f 2 4 4
f 2 3 0
f 2 0 0
f 3 7 5
f 3 2 0
f 3 1 0
f 4 5 0
f 4 6 4
f 5 4 0
f 5 7 1
f 6 7 7
f 6 4 0
f 7 6 0
f 7 5 0