如何转换带有过量流量的预流推送网络到流量网络

Question

我实现了最高流量的最高标签推送relabel算法的第一阶段，但是我找不到任何有关如何实现第二阶段的资源，即将预流推送网络转换为有效的流量网络。

Answer 1

如果您确实需要最大流量（可以直接从预流中派生最小流量并使用它来验证预流量），那么我知道两种方法。

第一种方法在原始的Goldberg - Tarjan关于推送relabel算法的论文中进行了介绍。实质上，第二阶段几乎与第一阶段完全一样。唯一的区别是源距离为n（而不是距离为0的sink）。这具有将过多的路由返回到源的效果。

我不确定第二种方法的描述。我知道这是在Goldberg的实施中，Boost Graph implementation基于此（请参阅convert_preflow_to_flow）。从概念上讲，有三个步骤。

1. 直到预流是无环的，通过在逆循环发送足够的流量，以除去从流图圆弧的一个取消流动循环。

2. 将流图的节点从最接近到最靠近的进行拓扑排序。

3. 对于拓扑顺序中的每个节点，通过减少传入弧上的流量（这会导致未处理节点的多余部分相应增加）来消除其多余部分。

实际上，步骤1和2都涉及深度优先搜索。天真地，在检测并取消每个周期后，重新开始深度优先搜索周期检测，但可以将深度优先搜索重新绕回到首次使用取消删除的弧的点，从而节省了时间再次在搜索中达到这一点。拓扑顺序可以作为搜索的副产品获得，为步骤2节省了单独的遍历。