Python NetworkX max_flow_min_cost işlevi sonsuza kadar koşuyor

Question

Belirli grafiklerde max_flow_min_cost işlevini kullanmaya çalışıyorum, ancak bazen algoritma sonsuza kadar sürüyor (veya en azından çok uzun bir süre) gibi görünüyor ve bunun nedenini anlamıyorum. dava. İşte bu kadar uzun süre çalışmasına neden olan bir grafik. Yukarıdaki grafik değiştirme ancak 2 ya da 3 batmaya hedef kapasiteli yaparsanız Hepsi aynı düğümleri

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

sahip, aynı zamanda sonsuza kadar çalışır. Kapasite 4'e eşitse, algoritma düzgün çalışır. Bu tam olarak arandı:

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

Teşekkür ederiz! Herhangi bir yardım takdir edilecektir. G'nin kodlarıyla ilgili bir sorun olması durumunda, NetworkX projesinde bir Yönlendirilmiş Grafik (DiGraph)

Düzenleme: I opened an issue olduğunu belirtmekte yarar var.

Answer 1

Benim için çalışıyor:

>>> 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 yılında algoritma ağırlıkları kayan nokta sayıları eğer çalışması garanti edilmez. P: Orijinal yazarlar Gelecek için buraya

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