问题标签 [push-relabel]

我很难理解来自 CLRS 的以下引理：

_{设 G 是一个流网络，s 和 t 是源和汇节点，f 是从 s 到 t 的预流，h 是 G 上的高度函数。那么在残差图 G f}中没有从 s 到 t 的增广路径.

为什么是这样？

我已经做了一个 MATLAB 版本的 push-relabel FIFO 代码（和维基百科上的完全一样并尝试过。放电功能和维基百科完全一样。

它非常适用于小图（例如节点数 = 7）。但是，当我增加图形大小（即节点/顶点数> 3500 或更多）时，“重新标记”函数运行非常缓慢，这在“放电”函数中被调用。我的图表很大（即 > 3000 个节点），所以我需要优化我的代码。

我尝试根据 WIKIPEDIA 关于全局重新标记/间隙重新标记的建议优化代码：1）为每个节点制作邻居列表，并让 index seen[u] 成为迭代器，而不是 range 。2）使用间隙启发式。

我被困在第一个，我不明白我到底要做什么，因为似乎遗漏了细节。（我制作了邻居列表，这样对于顶点 u，到 u 的任何连接节点 v(1..n) 都已经在邻居列表中，只是不确定如何使用 seen[u] 索引进行迭代）。

AND 放电函数使用 's' 邻域结构列表：

while (excess(u) > 0) %测试当前节点是否超出>0，如果是...

结尾

有人可以指导，展示或帮助我吗？

我不明白如何通过推送重新标记来实现间隙启发式。维基是这样描述的：

“在间隙重新标记启发式中，我们维护一个大小为 n 的数组 A，在 A[i] 中保存每个标签的节点数（最多 n）。如果找到标签 d，使得 A[d] = 0，那么所有标签 > d 的节点都被重新标记为标签 n。”

使用间隙启发式。如果有一个'k'使得没有节点height（u）=k，您可以为除source之外的所有节点设置height（u）= max（height（u），height（source）+1），其中height (u) >k。这是因为任何这样的“k”都表示图中的最小切割，并且不会有更多的流量从节点 S={u where height(u) > k} 流向 T={v, where height(v) 中的节点0。但是 height(u) > height(v)+1 与 height(u) > k 和 height(v) < k 相矛盾。

有人可以用伪代码向我解释如何将间隙启发式添加到 FIFO 推送重新标签中，如 wiki 的示例代码中所示？

谢谢，文斯

我一直在尝试找到一些开源代码，它可以执行 Goldberg 的 push 和 relabel 或 preflow-push 、 preflow-relabel 来解决 GENERAL 图的图切割问题。

我知道 CUDA 有 npp GrabCut 2D 示例代码，而且我也知道当每个像素都被视为一个节点时，nppiGraphCut() 会解决 2D 平面的图形切割问题。但是，鉴于以下图形输入，我想要解决的问题：

源、汇、节点数、从节点到节点、前向弧权重（从 -> 到节点） 后向弧权重（到 -> 从节点） 源权重（源到非终端节点容量） 汇权重（非终端节点接收容量）

我在matlab中有这个，如下图是这样给出的，其中源用sourceWeights连接到节点<1><2><3>，节点<1><2><3>用sinkWeights连接到sink节点。同样，容量之间也有节点，但只连接一个方向（即反向容量为0）。

<1> -> <2> -> <3> -> <4> -> <5> -> <6> ...

这可以在 nppGraphCut 中用作一维数组 (<1><2><3>) 来执行图形切割吗？

我正在对此进行编码，并且需要了解这两种不同算法的限制：1）容量必须是整数吗？2）图必须是非循环的吗？

谁能给点提示？

谢谢

我正在从 topcoder 站点学习 push-relabel 算法：http: //community.topcoder.com/tc ?module=Static&d1=tutorials&d2=maxflowPushRelabel 我认为实现有问题。节点饱和时如何将多余的流量推回节点。例如：

在找到从 1 到 3 的最大流量时，在某一阶段我需要将流量从 2 推回到 1（因为 2 没有出边）。但在先进先出算法的代码实现中，第16行的循环从0 to G[u].size(). 既然 2 没有从 2 到 1 的任何边，它怎么能把流量推回到 1 呢？

如果需要，这是我糟糕的实现：

我一直在尝试理解这段代码；它是 C++ 中 push-relabel 算法的实现：

代码可以编译并且可以工作，但我不明白我应该如何将输入传递给它。理想情况下，一个main()函数应该读取源和接收器（无论如何它们都是“虚构的”，并且只是算法工作所必需的），然后是构建图形所需的所有数据AddEdge()。但是如何做到这一点目前超出了我的范围。

我的main()应该是这样的

我认为这source应该用于初始化 some Edge.froms，它应该与sinkand some Edge.tos 类似，但我不知道如何构建图形。

I implemented first phase of the highest label push relabel algorithm for maximum flow but I could not find any resources about how to implement the second phase, i.e. to convert the preflow push network to a valid flow network.

我正在使用 boost 库来查找最大流量 (push relabel) ，并且有一个文件 read_dimacs.hpp 读取数据但 stdin。问题是我的数据文件太大，我想直接从文件中读取数据文件。任何人都可以帮助我。代码如下

Boost 提供了三种不同的算法来查找有向图中的最大流量：boykov_kolmogorov、edmonds_karp和push_relabel。它们都有命名和非命名参数版本。他们使用的参数集也非常相似。尽管如此，使用相同的参数，这些算法中的一些可以编译，而有些则不能。

push_relabel与命名和非命名版本都可以很好地编译：

boykov_kolmogorov使用非命名版本编译：

但命名版本失败：

/celibs/boost_1_73_0/boost/graph/detail/adjacency_list.hpp:2768:17：错误：形成对 void 的引用

edmonds_karp失败，命名和非命名版本都出现相同的错误：

/celibs/boost_1_73_0/boost/concept_check.hpp:147:9：错误：使用已删除的功能

完整示例在这里：https ://godbolt.org/z/dvjfec

我是否以不正确的方式传递参数？如何正确传递它们？

谢谢！