我必须写一个程序，它需要保持一个有向流图的一些数据。我需要计算的最大流量在运行时。

I have to write a program which requires to maintain some data in a directed flow graph. I need to compute the maximum-flow at runtime.

我知道，有处理图形，执行几乎所有的经典算法存在的几个库，但我的问题是，我的图是动态的，这意味着它的发展在运行时。每次进化之后，我需要重新计算新的最大流量。

I know that there exist several libraries for handling graphs, implementing almost every classical algorithm, but my problem is that my graph is dynamic, meaning it evolves at runtime. After every evolution, I need to recompute the new maximum-flow.

这是进化，无论是：

和我需要重新计算的最大流量从源S至已修改在该步骤中的边缘的目的地节点。例如：

and what I need to re-compute is the maximum-flow from the source S to the destination node of the edge that has been modified at that step. For example:

                     S                            S  
                     |                            |
                     5                            5
                     |                            |
                     V                            V
                     A---3--->B                   A---5--->B
    adding edge      |        |     increasing    |        |
      B-->D          2        1      A-->B of     2        1
                     |        |     two units     |        |
                     V        V                   V        V
                     C---3--->D                   C---3--->D

                      OUTPUT: 3                    OUTPUT: 5  
                    (maxflow S-D)                (maxflow S-B)

考虑演化的非常具体的性质在我的曲线图，这算法/库将有更多的时间，高性能？我的意思是，考虑到一个事实，即在每一步的曲线图几乎是相同的（除了一个边缘）的previous一步，是有可以有效地重复利用其previous计算的中间结果的算法？

Considering the very specific nature of the evolution in my graph, which algorithm/library would be more time-performant? I mean, considering the fact that at each step the graph is almost identical to the previous step (except for one edge), is there an algorithm that can efficiently re-use intermediate results of its previous computations?

我知道的事实，目的是不同的，每次使问题有点硬....我如何能为O更好的任何想法在每个步骤（VE ^ 2）？

I know that the fact that the destination is different every time makes the problem a bit hard.... any idea on how I can be better than O(VE^2) at each step?

而如果我也认为这是可能的变化？

And what if I also consider this possible evolution?

我试图理解所有的标准算法，并认为我怎么能进行修改，但作为图论不完全是我的领域，我非常失败......

I tried to understand all the standard algorithms and think how I could modify them, but being graph theory not exactly my field, I miserably failed...

任何帮助将AP preciated。 谢谢你。

Any help will be appreciated. Thanks.

推荐答案

唯一的文章中，我可以找到关于这个问题的一般情况下的增量算法最大流问题，由Kumar和古普塔。这是后面的收费墙，但其主要思想是pretty的简单。当我们增加电弧的能力的 UV 的，遍历两次图形以查找所有顶点的是W 的摆在路径上从取值的到的牛逼的图中的与弧线与正值剩余容量和的 UV 的。 （从的 U 的向后遍历和转发的 v 的）与previously计算流量，对这些顶点运行戈德堡-的Tarjan启动。

The only article I can find on the general case of this problem is An Incremental Algorithm for the Maximum Flow Problem, by Kumar and Gupta. It's behind a paywall, but the main idea is pretty simple. When we increase the capacity of arc uv, traverse the graph twice to find all vertices w that lie on a path from s to t in the graph with arcs with positive residual capacity and uv. (Traverse backward from u and forward from v.) Starting with the previously computed flow, run Goldberg–Tarjan on these vertices.

要添加一个弧形，先用容量零添加，然后提高其能力。库马尔 - 古普塔也被认为是降低容量/删除弧线。这是更复杂的;他们推流从 T 的回的 v 的，然后删除的 v 的，那么推动再次流动。

To add an arc, first add it with capacity zero and then increase its capacity. Kumar–Gupta also considered decreasing capacity/removing arcs. This is more complicated; they push flow from t back to v, then delete v, then push flow forward again.