python - 对于以下情况，NetworkX 的minimum_cut 算法是否正确？

Question

我很难验证 Python NetworkX 库的最大流最小割算法是否按预期工作(Edmonds-Karp 等)。我不知道我是否使用了错误的方法，或者我对最大流量最小切割的期望是否错误。我主要感兴趣的是容量(弧权重)如何影响较大图中的最小切割。例如通过弧权重影响切割位置。

我对容量(弧形重量)有点迷失了。我尝试了几个不同的小图，其中所有路径最终都汇聚在目标节点上，并且在所有情况下，权重似乎并不重要，因为切割节点/边总是最接近目标节点，其中最小的切割次数适用。也许这就是 Therom 试图解决的全部问题，而我误解了它的目的。

无论如何，这是一些代码。该图非常小，适合玩重量游戏。

import networkx as nx # NetworkX v1.10
...
#   >a->e
#  /     \
# s->b->f->t
#  \     /
#   >c->g
G = nx.DiGraph()
G.add_edge("s", "a", capacity=2)
G.add_edge("s", "b", capacity=2)
G.add_edge("s", "c", capacity=2)
G.add_edge("a", "e", capacity=2)
G.add_edge("b", "f", capacity=2)
G.add_edge("c", "g", capacity=4)
G.add_edge("e", "t", capacity=2)
G.add_edge("f", "t", capacity=2)
G.add_edge("g", "t", capacity=4)

cut_nodes = nx.algorithms.connectivity.minimum_node_cut(G, "s", "t")
print "Cut nodes: " + str(cut_nodes)
# Always produces cuts for e, f, g

cut_edges = nx.algorithms.connectivity.minimum_edge_cut(G, "s", "t")
print "Cut edges: " + str(cut_edges)
# Always produces cuts for e->t, f->t, g->t

这足以处理容量数字。我不确定容量是否应该有所作为。我知道只要s能达到t，就会进行削减。如果我调整容量，使路径 s->a->e->t 在 s->a 之间具有更高或更低的容量，则始终得出相同的切割边/节点。

我公开询问这个问题的原因是在 NetworkX 0.8.1 中，我尝试使用相同的支持，但将容量边缘属性指定为“权重”。即使文档支持基于容量的替代标签，API 也不会使用它。

如果容量应该影响上面图表中的切割内容，那么这可能是 NetworkX 问题。我不知道。

感谢您提前提供任何启发!

更新

感谢Abdallah-Sobehy 指出minimum_node_cut 和minimum_edge_cut 方法只关心节点基数。我遇到的问题是，minimum_edge_st_cut 的文档可能是正确的，因为它说“NetworkX 图的边缘预计有一个名为“容量”的属性。如果此属性不存在，则边缘被认为具有无限容量”

Abdallah-Sobehy 的用于确定边缘切割的代码非常有效。另一种方法(引用 NetworkX 源代码)可能是:

cut_edges = set()
for u, cn in ((n, G[n]) for n in partitions[0]):
    cut_edges.update((u, v) for v in cn if v in partitions[1])

我还想尝试找到要从 cut_edges 中剪切的节点。我的理解是节点切割与边缘切割不同，因为问题不一样。像边权重(容量)这样的东西对于以相同方式切割的节点来说并不重要。 (您需要一些节点权重并考虑基数)

无论如何，在这个问题上，我只是简单地计算剪切边中的依赖节点(例如(node1 -> node2)作为要剪切的节点，并对涉及源和目标的剪切边进行一些特殊处理.它可能对我有用，但我还不确定。

更新 2(可能是最终版本)

我想我会根据剪切边缘代码扔进我的剪切节点只是为了笑。

cut_nodes = set()
for e in cut_edges:
    cut_nodes.update(e[1])
cut_st_nodes = set()
if s in cut_nodes or t in cut_nodes:
    for e in cut_edges:
        if e == (s, t):
            cut_st_nodes.update(t)
        elif e == (t, s):
            cut_st_nodes.update(t)
        elif t == e[1] or s == e[1]:
            cut_st_nodes.update(e[0])
cut_nodes -= set([s, t])
cut_nodes |= cut_st_nodes

这里的推理可能是错误的，因为所有切割边都是有方向的，并且边中的源节点依赖于边中的目标节点，因此删除目标节点将反射(reflect)边切割。 (例如，n1 -> n2，n1 依赖于 n2，因此删除 n2)如果这是真的，那么只需从切割边抓取所有目标节点即可，除非涉及图源或目标。我添加了 cut_node_st 来捕获源节点或目标节点作为边缘剪切绑定(bind)目标节点涉及的此类情况。 (例如 n1 -> 源，或 n2 -> 目标)

我将 cut_nodes_st 与 cut_nodes 分开，直到最后，因为我只希望 s 和 t 在涉及这些特殊情况时出现在 cut_nodes 中。

想法？

Answer 1

您的结论是正确的，即更改“容量”不会影响minimum_edge_cut和minimum_node_cut函数的结果。但我相信这在 Networkx 中不是一个问题，因为根据文档，这些函数试图找到基数方面的最小切割(即节点/边的最小数量，如果删除，源和之间将没有路径)汇节点)。因此，改变容量并不重要。

但最近我想做你所指的事情。我发现答案就在 minimum_cut 中函数，其中文档使用最大流最小割理论，并明确说明考虑容量(或您选择的任何属性)来将图划分为 2 组节点(每个节点包括 s 或 t)，其中切削刃能力最小。在这里使用容量值会产生不同的结果。

函数返回cut_value，即所有切割边的总容量，以及2组节点，每个节点都是包含“s”的分区或“t”，您可以从中轻松计算edge_cut。

为了澄清更多信息，我将此部分添加到您的代码中:

cut_weight, partitions = nx.minimum_cut(G, "s", "t")
print "cut edges capacity " + str(cut_weight)
print "Set of nodes in the 's' partition: " + str(partitions[0])
print "Set of nodes in the 't' partition: " + str(partitions[1])
edge_cut_list = [] # Computed by listing edges between the 2 partitions
for p1_node in partitions[0]:
    for p2_node in partitions[1]:
        if G.has_edge(p1_node,p2_node):
            edge_cut_list.append((p1_node,p2_node))
print "Edges of the cut: " + str(edge_cut_list)

The output yielded a total edge cut capacity of 6 which is less than the cut computed by minimum_edge_cut 8 (because it does not take edges weight into consideration.

cut edges capacity 6
Set of nodes in the 's' partition: set(['a', 's', 'b', 'e', 'f'])
Set of nodes in the 't' partition: set(['c', 't', 'g'])
Edges of the cut: [('s', 'c'), ('e', 't'), ('f', 't')]