Description
Hello,
( X-Posted on https://stackoverflow.com/questions/78056215/what-does-negative-flow-on-a-reverse-arc-of-a-graph-in-boykov-kolmogorov-max-flo )
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?