Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Question on negative flow on arcs in Boykin-Kolmogorov algorithm -- meaning and interpretation #366

Open
TryerGit opened this issue Feb 25, 2024 · 0 comments

Comments

@TryerGit
Copy link

TryerGit commented Feb 25, 2024

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?

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

No branches or pull requests

1 participant