+- Python Forum (https://python-forum.io)
+-- Forum: Python Coding (https://python-forum.io/forum-7.html)
+--- Forum: General Coding Help (https://python-forum.io/forum-8.html)
+--- Thread: Find Maximum Flow for graph with infinite capacities (/thread-17546.html)
Find Maximum Flow for graph with infinite capacities - Dav - Apr-15-2019
I want to know how I could compute maximum flow for a graph G(V,E) that includes one or more infinite capacities.
Thanks
RE: Find Maximum Flow for graph with infinite capacities - Larz60+ - Apr-15-2019
Perhaps:
NetworkX is a Python language software package for the creation, manipulation, and study of the structure, dynamics, and function of complex networks
https://networkx.github.io/documentation/networkx-1.10/
Maximum Flow:
https://networkx.github.io/documentation/networkx-1.10/reference/generated/networkx.algorithms.flow.maximum_flow_value.html
RE: Find Maximum Flow for graph with infinite capacities - Dav - Apr-16-2019
(Apr-15-2019, 06:17 PM)Larz60+ Wrote: Perhaps:Thank you
NetworkX is a Python language software package for the creation, manipulation, and study of the structure, dynamics, and function of complex networks
https://networkx.github.io/documentation/networkx-1.10/
Maximum Flow:
https://networkx.github.io/documentation/networkx-1.10/reference/generated/networkx.algorithms.flow.maximum_flow_value.html
I already use networkx for any graph manipulation but it does not support infinite capacity as mentioned hereafter (from https://networkx.github.io/documentation/networkx-1.10/reference/generated/networkx.algorithms.flow.maximum_flow_value.html):
Quote: ... If the graph has a path of infinite capacity, the value of a feasible flow on the graph is unbounded above and the function raises a NetworkXUnbounded.
So I am wondering if there are other ways to do that.
Any proposition ?
Thank you
RE: Find Maximum Flow for graph with infinite capacities - Larz60+ - Apr-16-2019
Sorry, I was lucky to find that one.
RE: Find Maximum Flow for graph with infinite capacities - scidam - Apr-16-2019
What would happened, if you replaced infinity with a sufficiently large number?
RE: Find Maximum Flow for graph with infinite capacities - Larz60+ - Apr-16-2019
Try it all it takes is time.
RE: Find Maximum Flow for graph with infinite capacities - Dav - Apr-16-2019
(Apr-16-2019, 06:25 AM)scidam Wrote: What would happened, if you replaced infinity with a sufficiently large number?
(Apr-16-2019, 09:10 AM)Larz60+ Wrote: Try it all it takes is time.
Thank you so much, I appreciate your helps
The outgoing edges (from source node) should not have infinite capacities (and it does not matter if you put huge number or even infinity somewhere else)