CODEWITHSUNDEEP
pythonalgorithmgraphgraph-algorithmnetworkx
Arya
Arya

Reputation: 1469

Python NetworkX max_flow_min_cost function running forever

I'm trying to use the max_flow_min_cost on certain graphs, but it seems like sometimes the algorithm runs forever (or at least for an extremely long time), and I don't understand why this is the case. Here is a graph that cause it to run that long. They all have the same nodes 

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

If I modify the above graph but make the capacity from destination to sink 2 or 3, it also runs forever. If I make capacity equal to 4, the algorithm runs fine. This is the exact call:

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

Thank you! Any help will be appreciated. It's worth mentioning that G is a Directed Graph (DiGraph)

Edit: I opened an issue on the NetworkX project, in case it's an issue with their code.

Upvotes: 1

Views: 1287

Answers (2)

Aric
Aric

Reputation: 25289

The algorithm in networkx.max_flow_min_cost is not guaranteed to work if the weights are floating point numbers. See the original authors question answered at the networkx web site here

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

Upvotes: 4

Imanol Luengo
Imanol Luengo

Reputation: 15889

It works fine for me:

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

Upvotes: 1

Related Questions