0

Actually there are discussions about this problem:

The approach is to add another node (source/sink or both) and add also edges (with infinite capacities) to link them with the rest of nodes. Finally, we got a graph with one source - one sink, afterward, we just apply the Maximum Flow Algorithm.

My Questions:

  1. How to compute Maximum Flow for graph contains infinite capacities since all NetworkX methods does not support it?
  2. Are there any other methods to solve this kind of problem?

Thank you

Community
  • 1
  • 1
David29
  • 21
  • 4
  • If you have float capacities, why not use `math.inf`? Otherwise, I would go with `sys.maxsize`. – ypnos Apr 14 '19 at 22:07
  • @ypnos thank you, unfortunately the maximum flow method included in NetworkX library does not support **infinite capacity**. Is there a way to adapt this method or are there any other methods ? – David29 Apr 14 '19 at 22:57
  • I use graph-tool instead of networkx, it takes long to compile but worth it. See https://graph-tool.skewed.de/static/doc/flow.html for maximum flow algorithms. – ypnos Apr 15 '19 at 12:38
  • Very useful, thanks – David29 Apr 15 '19 at 18:06
  • Two nodes with an infinite-capacity edge between them can just be merged. – user2357112 Apr 17 '19 at 08:19

0 Answers0