Clever Geek Handbook

Refresh max flow after adding edge

Consider that we have a network flow and using the Edmond-Karp algorithm, we already have a maximum network flow. Now, if we add an arbitrary edge (with a specific bandwidth) to the network, what is the best way to update the maximum flow? I thought about updating the residual network with respect to the new edge and looking for an increase path again until we find a new max flow, but I'm not sure if it works or if this is the best way!

+3


source to share


2 answers


After running maxflow, you know the amount of content that each stream flows.

So, when the cost of changing the edge changes, you can do the following:

  • Suppose the content passed by this edge is w

    .
  • Now make forward dfs

    and backward dfs

    from this land and destroy the final contents w

    of the associated edge.

enter image description here

Here each edge is represented x/y

, where y

means the bandwidth of the edge, and x

means the content that it transmitted.

Now you want to change the edge value 4->3

from 2

to 3

.

All you have to do is do it forward and backward dfs

from an 4->3

edge and undo the 2

weight from that edge as a 4->3

stream w=2

.



The process will look like this:

enter image description here

You are now almost done :)

  1. Change the edge value 4->3

    from 2

    to 3

    and try to find the extension path again :)

Let me know if you find it difficult to understand or I am wrong somehow :)

Edit:

  • If the value of the new edge is greater than the current value than you do not have to cancel the weight. You can simply try to find an additional path that changes the capacity of the edge.

  • But if the capacity is reduced, you need to cancel the weight and try to find a way to increase.

  • If a new addition is added, you can simply add an edge and try to find the extension path if available. this is.

+3


source


In fact, adding a new edge is not very difficult - you have the streams / capacities of the edges before adding the edge, and then you add the edge and its back. Then run the algorithm you are using to find the extension path until you find a non-null stream and that's it. Most of the maximum flow will already be found, so this should (in theory) not be too slow. I don't know which maximum flow algorithm you are using, so I cannot be more specific, but it is possible that after adding a new edge, you violate a property of the algorithm, and thus you find maximum flow in suboptimal mode. However, you have already processed most of the graph, so this shouldn't be too much of a problem.



I would recommend that you use the Ford-Fulkerson algorithm to complete the task no matter what original algorithm you used for maximum flow. I think it will work well in cases where most of the maximum flow has already been detected.

0


source






More articles:


All Articles