Calculating max flows to the different sinks

[skaurus]

Hello again!

Am I right that there is no option to change a sink dynamically, and if I want to calculate max flow in the same graph between different nodes - I have to recreate it each time?

Actually I think the most convenient api for that would be ability to just pass any two node ids to the Outflow function 🤔

[kalexmills]

Changing the sources and sinks in the graph can change the maximum flow, so when you make that kind of a change, you might also change the flow. This library doesn't attempt to solve dynamic max-flow -- keeping the max-flow updated in a graph that can change over time.

If you're not changing the structure of the graph but you're interested in efficiently finding the maximum flow between any pair of nodes, you might be interested in something called a Gomory-Hu tree. This library doesn't attempt to compute one, but it's the sort of thing it sounds like you're after.

https://www.geeksforgeeks.org/gomory-hu-tree-introduction/

EDIT: there also appears to be a paper on dynamic max flow available without a paywall here: https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.414.8340&rep=rep1&type=pdf

EDIT2: At a glance, that paper clearly aims to solve a very different sort of dynamic problem.

[skaurus]

Ah, so the calculation is changing the initial state of the graph. Thank you for the very elaborate answer!

I've looked through the code briefly to try to understand what is changing and if it is feasible (and would make sense) to add the ability to reset that state back, and found reset method! And it is actually is called inside PushRelabel 🤔

I might be missing something, but maybe that does mean that with some tweaks it would be not so hard to actually change the source/sink between computations and call PushRelabel + Outflow multiple times?

If so, maybe at some point I would take a shot at it.

EDIT: I just checked, and I can call PushRelabel any number of times, with Outflow in between or not - the answer will not change. So it seems that reset is working as expected by its name.

[kalexmills]

I might be missing something, but maybe that does mean that with some tweaks it would be not so hard to actually change the source/sink between computations and call PushRelabel + Outflow multiple times?

I would need to look into the proof of correctness + termination for the Push-Relabel algorithm to know for sure whether this can work. Playing with implementations like you're suggesting and expecting correct results isn't usually sound -- it pays to go back to the math.

If you try and start with a flow already computed, one other difficulty is that the algorithm may have to waste time undoing a bunch of bad decisions in order to arrive at the new max flow.