首页 文章

在下列情况下,NetworkX minimum_cut算法是否正确?

提问于
浏览
1

我正在努力验证Python NetworkX库的max-flow min-cut算法是否按预期工作(Edmonds-Karp等等) . 我不知道我是否使用它错了或者我对max-flow min-cut的期望是错误的 . 大多数情况下,我对容量(弧度)如何影响较大图形中的最小切割感兴趣 . 例如影响通过弧重进行切割的位置 .

能力点(弧重)对我来说有点失落 . 我尝试了不同的小图形,其中所有路径最终会聚在目标节点上,并且在所有情况下,权重似乎并不重要,因为切割节点/边缘总是最接近目标节点,其中最小削减数量适用 . 也许这就是所有这些都试图解决,我误解了它的目的 .

无论如何,这里有一些代码 . 该图表非常小,适合玩重量 .

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问题 . 我不知道 .

感谢任何提前启发!

Update

感谢Abdallah-Sobehy指出minimum_node_cut和minimum_edge_cut方法onyl关心节点基数 . 我猜想的问题是minimal_edge_st_cut的文档可能是正确的,因为它表示“NetworkX图形的图形边缘应该具有一个名为'capacity'的属性 . 如果该属性不存在,则边缘被认为具有无限容量“

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)作为要切割的节点,对切割边缘进行一些特殊处理,其中涉及源和目标 . 为我工作,但我还不确定 .

Update 2 (final probably)

我以为我会根据切边代码折腾切割节点只是为了笑 .

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

这里的推理可能是错误的,即所有切割边缘都是方向性的,并且边缘中的源节点依赖于边缘中的taret节点,因此移除目标节点将反映边缘切割 . (例如,n1 - > n2,n1依赖于n2,因此删除n2)如果这是真的,那么只需从切割边缘抓取所有目标节点就可以了,除非涉及图形源或目标 . 我添加了cut_node_st来捕获这些类型的情况,其中源节点或目标节点作为边缘剪切绑定目标节点 . (例如n1 - > source,或n2 - > target)

我将cut_nodes_st与cut_nodes分开直到结束,因为我只希望s和t出现在cut_nodes中,当它们涉及这些特殊情况时 .

思考?

1 回答

  • 3

    您的结论是正确的,即更改“容量”不会影响minimum_edge_cut和minimum_node_cut函数的结果 . 但我认为,根据文档,这不是Networkx中的一个问题,这些函数试图找到基数方面的最小切割(即如果移除的最小数量的节点/边缘将不存在源和汇聚节点) . 因此,改变容量并不重要 .

    但最近我想做你所指的 . 我发现答案在minimum_cut函数中,其中文档使用max-flow min-cut理论并清楚地说明了将图表划分为2组节点时的容量(或您选择的任何属性)(每个包括 capacity of cutting edges 最小的s或t) . 在这里玩容量值会产生不同的结果 .

    该函数返回 cut_value ,这是所有切削刃的总容量,以及 2 sets of nodes 每个都是包含"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)
    

    输出产生的总边缘切割能力为6小于minimum_edge_cut 8计算的削减(因为它不考虑边缘权重) .

    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')]
    

相关问题