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:

The network flow

We will replace question marks with the optimum values.

Import libraries

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.

Code

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.

Code

And finally, all that remains is to invoke the solver and display the results.

Code

Here is the output of the program:

Output

The maximum flow value is 10 and the flow looks like this:

Optimal flow

Putting it all together:

An industrial engineer who wants to create a better world for all humanity and the future. https://www.linkedin.com/in/frknklcsln/