A Maximum Flow Problem Solution with Python
Many problems in computer science can be represented by a graph consisting of nodes and links between them. Examples are network flow problems, which involve transporting goods or material across a network, such as a railway system. You can represent a network flow by a graph whose nodes are cities and whose arcs are rail lines between them. (They’re called flows because their properties are similar to those of water flowing through a network of pipes.)
A key constraint in network flows is that each arc has a capacity — the maximum amount that can be transported across the arc in a fixed period of time. The maximum flow problem is to determine the maximum total amount that can be transported across all arcs in the network, subject to the capacity constraints. [Google OR-Tools]
An Example
Let’s say we have a network flow like this:
We will replace question marks with the optimum values.
After the import section is done, we can start coding. We need to make a list to understandable by the computer. So, I will create 3 lists for nodes and capacities.
This means the capacity of the arc which starts with 0 and ends with 1 is 6. Same for others. Start with 2 and ends with 3 is 5, and so on.
In this part, we will give these nodes and capacities to the algorithm to create the flow. The capacities are the constraints for the problem.
And finally, all that remains is to invoke the solver and display the results.
Here is the output of the program:
The maximum flow value is 10 and the flow looks like this:
Putting it all together:
