Python NetworkX max_flow_min_cost 函数运行永远

Question

我正在尝试在某些图表上使用 max_flow_min_cost，但有时算法运行似乎永远存在（或至少在极长的一段时间内），而我不不明白为什么会这样。这是导致它运行这么长的图表。他们都有相同的节点

nodes = [
    ('1in', {'y': -1, 'x': -1, 'type': 'passenger in', 'number': 1}), 
    ('2out', {'y': 1, 'x': -1, 'type': 'passenger out', 'number': 2}),
    ('destination', {'y': 0, 'x': 0, 'type': 'destination'}), 
    ('2in', {'y': 1, 'x': -1, 'type': 'passenger in', 'number': 2}),
    ('source', {'type': 'meta'}), 
    ('4in', {'y': -1, 'x': 1, 'type': 'passenger in', 'number': 4}),
    ('1out', {'y': -1, 'x': -1, 'type': 'passenger out', 'number': 1}),
    ('4out', {'y': -1, 'x': 1, 'type': 'passenger out', 'number': 4}),
    ('sink', {'type': 'meta'}), 
    ('3in', {'y': 1, 'x': 1, 'type': 'passenger in', 'number': 3}),
    ('3out', {'y': 1, 'x': 1, 'type': 'passenger out', 'number': 3})
]

edges = [
    ('1in', '1out', {'cost': 0, 'capacity': 1}), 
    ('2out', '4in', {'cost': -9.48, 'capacity': 1}), 
    ('2out', 'destination', {'cost': -10.9, 'capacity': 1}), 
    ('2out', '3in', {'cost': -10.31, 'capacity': 1}), 
    ('destination', 'sink', {'cost': 0, 'capacity': 1}), 
    ('2in', '2out', {'cost': 0, 'capacity': 1}), 
    ('source', '2in', {'cost': 0, 'capacity': 1}), 
    ('source', '4in', {'cost': 0, 'capacity': 1}), 
    ('source', '1in', {'cost': 0, 'capacity': 1}), 
    ('source', '3in', {'cost': 0, 'capacity': 1}), 
    ('4in', '4out', {'cost': 0, 'capacity': 1}), 
    ('1out', '2in', {'cost': -10.31, 'capacity': 1}), 
    ('1out', '4in', {'cost': -10.31, 'capacity': 1}), 
    ('1out', 'destination', {'cost':-10.9, 'capacity': 1}), 
    ('1out', '3in', {'cost': -9.48, 'capacity': 1}), 
    ('4out', 'destination', {'cost': -10.9, 'capacity': 1}), 
    ('3in', '3out', {'cost': 0, 'capacity': 1}), 
    ('3out', '4in', {'cost': -10.31, 'capacity': 1}), 
    ('3out', 'destination', {'cost': -10.9, 'capacity': 1})
]

如果我修改上图但使从目的地到接收器的容量为 2 或 3，它也永远运行s。如果我使容量等于 4，则算法运行没问题。这是确切的调用：

nx.max_flow_min_cost(G,'source','sink',weight='cost')

谢谢！任何帮助将不胜感激。值得一提的是G是一个有向图(DiGraph)

编辑：我 opened an issue 在 NetworkX 项目上，以防他们的代码出现问题。

Answer 1

对我来说效果很好：

>>> G = nx.Graph()
>>> G.add_edges_from([
    ('1in', '1out', {'cost': 0, 'capacity': 1}), 
    ('2out', '4in', {'cost': -9.48, 'capacity': 1}), 
    ('2out', 'destination', {'cost': -10.9, 'capacity': 1}), 
    ('2out', '3in', {'cost': -10.31, 'capacity': 1}), 
    ('destination', 'sink', {'cost': 0, 'capacity': 1}), 
    ('2in', '2out', {'cost': 0, 'capacity': 1}), 
    ('source', '2in', {'cost': 0, 'capacity': 1}), 
    ('source', '4in', {'cost': 0, 'capacity': 1}), 
    ('source', '1in', {'cost': 0, 'capacity': 1}), 
    ('source', '3in', {'cost': 0, 'capacity': 1}), 
    ('4in', '4out', {'cost': 0, 'capacity': 1}), 
    ('1out', '2in', {'cost': -10.31, 'capacity': 1}), 
    ('1out', '4in', {'cost': -10.31, 'capacity': 1}), 
    ('1out', 'destination', {'cost':-10.9, 'capacity': 1}), 
    ('1out', '3in', {'cost': -9.48, 'capacity': 1}), 
    ('4out', 'destination', {'cost': -10.9, 'capacity': 1}), 
    ('3in', '3out', {'cost': 0, 'capacity': 1}), 
    ('3out', '4in', {'cost': -10.31, 'capacity': 1}), 
    ('3out', 'destination', {'cost': -10.9, 'capacity': 1})
])

>>> nx.max_flow_min_cost(G, 'source', 'sink', weight='cost')
{'1in': {'1out': 0, 'source': 0},
 '1out': {'1in': 0, '2in': 1, '3in': 1, '4in': 1, 'destination': 1},
 '2in': {'1out': 1, '2out': 1, 'source': 0},
 '2out': {'2in': 0, '3in': 1, '4in': 1, 'destination': 1},
 '3in': {'1out': 1, '2out': 1, '3out': 0, 'source': 0},
 '3out': {'3in': 0, '4in': 1, 'destination': 1},
 '4in': {'1out': 1, '2out': 1, '3out': 1, '4out': 0, 'source': 0},
 '4out': {'4in': 0, 'destination': 1},
 'destination': {'1out': 1, '2out': 0, '3out': 1, '4out': 1, 'sink': 1},
 'sink': {'destination': 0},
 'source': {'1in': 0, '2in': 1, '3in': 0, '4in': 0}}

Answer 2

如果权重是浮点数，networkx.max_flow_min_cost中的算法不能保证有效。在此处的 networkx 网站上查看原作者问题的回答

https://github.com/networkx/networkx/issues/2076#issuecomment-210200259

Python NetworkX max_flow_min_cost 函数运行永远

Python NetworkX max_flow_min_cost function running forever

python

algorithm

graph

networkx

graph-algorithm

Python NetworkX max_flow_min_cost 函数 运行 永远

Python NetworkX max_flow_min_cost function running forever

python

algorithm

graph

networkx

graph-algorithm

Python NetworkX max_flow_min_cost 函数运行永远