You signed in with another tab or window. Reload to refresh your session.You signed out in another tab or window. Reload to refresh your session.You switched accounts on another tab or window. Reload to refresh your session.Dismiss alert
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?
The text was updated successfully, but these errors were encountered:
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
wheremax_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:My questions are:
(1) Given the display loop:
Why are some arcs displayed multiple times in the output for e.g.,
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?
The text was updated successfully, but these errors were encountered: