0
$\begingroup$

The max-flow algorithm finds the maximum flow through a graph given edge capacities. However, if there is an option between flowing through two edges, it will typically just leverage one of those edges fully and ignore the other. One can influence which of the edges should be preferred by using "min_cost_max_flow" and setting the costs of the preferable edges lower. However, this still makes some edges preferable compared with others. What if I want the flow to be evenly distributed among edges in such a situation? Here is a toy example. We can see that max flow leverages vertex-1 and flows 4 units through it. However, it could just as easily have sent 2 units through vertex-1 and 2 units through vertex-2. How can I make it do this? To make this concrete, we can say that the variance of flow across the edges should be minimized (with flowing the max volume possible being the first goal of course).

enter image description here

Note: I've posted a similar question on CS stackexchange: https://stackoverflow.com/questions/64635070/max-flow-modify-networkx-source-code-so-a-few-edges-dont-hog-all-the-flow. There, I'm not looking for the optimal solution in terms of variance, but any change to the source code (with toy code sample provided) that will make the flow less concentrated on the vertex in question in the toy example.

$\endgroup$
  • 1
    $\begingroup$ Can you give a more precise specification of what you want the algorithm to achieve? A goal such as "balance the flow evenly" is not a specification. How do you measure the balance in more complex situations? If improving balance in one area hurts balance in another, how do you want to trade that off, and what quantitative metric would you use to measure how balanced a solution is? Coding questions are off-topic here and we discourage putting code in questions; I don't see how it is relevant in any case. $\endgroup$ – D.W. Oct 11 at 20:47
  • $\begingroup$ @D.W. - Let's just say for now that the variance of flow across edges should be minimized? $\endgroup$ – Rohit Pandey Oct 11 at 21:50
  • $\begingroup$ @D.W. Thought I'd add the code to demonstrate that standard algorithms seem to not care about balancing the flow across edges at all. $\endgroup$ – Rohit Pandey Oct 11 at 22:02
  • $\begingroup$ Welcome to COMPUTER SCIENCE @SE. If the capacity of (s, 1) was 9 instead of 5, would you prefer low variance in utilisation ratio/relative flow (3 1) over low variance in absolute flow (2 2)? $\endgroup$ – greybeard Oct 12 at 10:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.