Maximum Flows

In the following sections, we present an example of a maximum flow (max flow) problem.

A max flow example

The problem is defined by the following graph, which represents a transportation network:

20 30 40 30 20 10 20 5 10 0 1 2 3 4

We wish to transport meterial from node 0 (the source) to node 4 (the sink). The numbers next to the arcs are their capacities — the capacity of an arc is the maximum amount that can be transported across it in a fixed period of time. The capacities are the constraints for the problem.

A flow is an assignment of a non-negative number to each arc (the flow amount) that satisfies the following flow conservation rule:

The max flow problem is to find a flow for which the sum of the flow amounts for the entire network is as large as possible.

The following sections present Python and C# programs to find the maximum flow from the source (0) to the sink (4).

Define the data

You define the graph for the problem with three arrays, for the start nodes, end nodes, and capacities of the arcs. The length of each array equals the number of arcs in the graph. For each i, arc i goes from start_nodes[i] to end_nodes[i], and its capacity is given by capacities[i]. The next section shows how to create the arcs using this data.

Python data
  # Define three parallel arrays: start_nodes, end_nodes, and the capacities
  # between each pair. For instance, the arc from node 0 to node 1 has a
  # capacity of 20.

  start_nodes = [0, 0, 0, 1, 1, 2, 2, 3, 3]
  end_nodes = [1, 2, 3, 2, 4, 3, 4, 2, 4]
  capacities = [20, 30, 10, 40, 30, 10, 20, 5, 20]
C# data
    // Define three parallel arrays: start_nodes, end_nodes, and the capacities
    // between each pair. For instance, the arc from node 0 to node 1 has a
    // capacity of 20.
    // From Taha's 'Introduction to Operations Research',
    // example 6.4-2.

    int numNodes = 5;
    int numArcs = 9;
    int[] start_nodes = {0, 0, 0, 1, 1, 2, 2, 3, 3};
    int[] end_nodes = {1, 2, 3, 2, 4, 3, 4, 2, 4};
    int[] capacities = {20, 30, 10, 40, 30, 10, 20, 5, 20};

Declare the solver and add the arcs

To solve the problem, we use the SimpleMaxFlow solver. (The C# name for the solver is MaxFlow.)

For each start node and end node, we create an arc from start node to end node with the given capacity, using the method AddArcWithCapacity. The capacities are the constraints for the problem.

Python constraints
  max_flow = pywrapgraph.SimpleMaxFlow()
  # Add each arc.
  for i in range(0, len(start_nodes)):
    max_flow.AddArcWithCapacity(start_nodes[i], end_nodes[i], capacities[i])
C# constraints
    MaxFlow maxFlow = new MaxFlow();
// Add each arc.
    for (int i = 0; i < numArcs; ++i)
    {
      int arc = maxFlow.AddArcWithCapacity(start_nodes[i], end_nodes[i],
                                           capacities[i]);
      if (arc != i) throw new Exception("Internal error");
    }
    int source = 0;
    int sink = numNodes - 1;

Invoke the solver and display the results

Now that all the arcs have been defined, all that remains is to invoke the solver and display the results. We invoke the Solve() method, providing the source (0) and sink(4), and then display the flow across each arc.

Python solution
  # Find the maximum flow between node 0 and node 4.
  if max_flow.Solve(0, 4) == max_flow.OPTIMAL:
    print('Max flow:', max_flow.OptimalFlow())
    print('')
    print('  Arc    Flow / Capacity')
    for i in range(max_flow.NumArcs()):
      print('%1s -> %1s   %3s  / %3s' % (
          max_flow.Tail(i),
          max_flow.Head(i),
          max_flow.Flow(i),
          max_flow.Capacity(i)))
    print('Source side min-cut:', max_flow.GetSourceSideMinCut())
    print('Sink side min-cut:', max_flow.GetSinkSideMinCut())
  else:
    print('There was an issue with the max flow input.')
C# solution
    Console.WriteLine("Solving max flow with " + numNodes + " nodes, and " +
                      numArcs + " arcs, source=" + source + ", sink=" + sink);

    // Find the maximum flow between node 0 and node 4.
    int solveStatus = maxFlow.Solve(source, sink);
    if (solveStatus == MaxFlow.OPTIMAL)
    {
      Console.WriteLine("Max. flow: " + totalFlow);
      Console.WriteLine("");
      Console.WriteLine("  Arc     Flow / Capacity");
      for (int i = 0; i < numArcs; ++i)
      {
        Console.WriteLine(maxFlow.Tail(i) + " -> " +
                          maxFlow.Head(i) + "    " +
                          string.Format("{0,3}", maxFlow.Flow(i)) + "  /  " +
                          string.Format("{0,3}", maxFlow.Capacity(i)));
      }
    }
    else
    {
      Console.WriteLine("Solving the max flow problem failed. Solver status: " +
                        solveStatus);
    }
  }

Here is the output of the program:

Max flow: 60

  Arc    Flow / Capacity
0 -> 1    20  /  20
0 -> 2    30  /  30
0 -> 3    10  /  10
1 -> 2     0  /  40
1 -> 4    20  /  30
2 -> 3    10  /  10
2 -> 4    20  /  20
3 -> 2     0  /   5
3 -> 4    20  /  20
Source side min-cut: [0]
Sink side min-cut: [4, 1]
The flow amounts across each arc are displayed under Flow

Complete programs

Putting it all together, here are the complete programs in Python and C#.

Full Python program
"""From Taha 'Introduction to Operations Research', example 6.4-2."""

from __future__ import print_function
from ortools.graph import pywrapgraph

def main():
  """MaxFlow simple interface example."""

  # Define three parallel arrays: start_nodes, end_nodes, and the capacities
  # between each pair. For instance, the arc from node 0 to node 1 has a
  # capacity of 20.

  start_nodes = [0, 0, 0, 1, 1, 2, 2, 3, 3]
  end_nodes = [1, 2, 3, 2, 4, 3, 4, 2, 4]
  capacities = [20, 30, 10, 40, 30, 10, 20, 5, 20]

  # Instantiate a SimpleMaxFlow solver.
  max_flow = pywrapgraph.SimpleMaxFlow()
  # Add each arc.
  for i in range(0, len(start_nodes)):
    max_flow.AddArcWithCapacity(start_nodes[i], end_nodes[i], capacities[i])

  # Find the maximum flow between node 0 and node 4.
  if max_flow.Solve(0, 4) == max_flow.OPTIMAL:
    print('Max flow:', max_flow.OptimalFlow())
    print('')
    print('  Arc    Flow / Capacity')
    for i in range(max_flow.NumArcs()):
      print('%1s -> %1s   %3s  / %3s' % (
          max_flow.Tail(i),
          max_flow.Head(i),
          max_flow.Flow(i),
          max_flow.Capacity(i)))
    print('Source side min-cut:', max_flow.GetSourceSideMinCut())
    print('Sink side min-cut:', max_flow.GetSinkSideMinCut())
  else:
    print('There was an issue with the max flow input.')

if __name__ == '__main__':
  main()
Full C# program

using System;
using Google.OrTools.Graph;

public class CsFlow
{
  private static void SolveMaxFlow()
  {
    // Define three parallel arrays: start_nodes, end_nodes, and the capacities
    // between each pair. For instance, the arc from node 0 to node 1 has a
    // capacity of 20.
    // From Taha's 'Introduction to Operations Research',
    // example 6.4-2.

    int numNodes = 5;
    int numArcs = 9;
    int[] start_nodes = {0, 0, 0, 1, 1, 2, 2, 3, 3};
    int[] end_nodes = {1, 2, 3, 2, 4, 3, 4, 2, 4};
    int[] capacities = {20, 30, 10, 40, 30, 10, 20, 5, 20};

// Instantiate a SimpleMaxFlow solver.
    MaxFlow maxFlow = new MaxFlow();
// Add each arc.
    for (int i = 0; i < numArcs; ++i)
    {
      int arc = maxFlow.AddArcWithCapacity(start_nodes[i], end_nodes[i],
                                           capacities[i]);
      if (arc != i) throw new Exception("Internal error");
    }
    int source = 0;
    int sink = numNodes - 1;

    Console.WriteLine("Solving max flow with " + numNodes + " nodes, and " +
                      numArcs + " arcs, source=" + source + ", sink=" + sink);

    // Find the maximum flow between node 0 and node 4.
    int solveStatus = maxFlow.Solve(source, sink);
    if (solveStatus == MaxFlow.OPTIMAL)
    {
      Console.WriteLine("Max. flow: " + totalFlow);
      Console.WriteLine("");
      Console.WriteLine("  Arc     Flow / Capacity");
      for (int i = 0; i < numArcs; ++i)
      {
        Console.WriteLine(maxFlow.Tail(i) + " -> " +
                          maxFlow.Head(i) + "    " +
                          string.Format("{0,3}", maxFlow.Flow(i)) + "  /  " +
                          string.Format("{0,3}", maxFlow.Capacity(i)));
      }
    }
    else
    {
      Console.WriteLine("Solving the max flow problem failed. Solver status: " +
                        solveStatus);
    }
  }

  static void Main()
  {
    SolveMaxFlow();
  }
}

SimpleMaxFlow methods

The SimpleMaxFlow class provides the following methods, (most of which are not used in this simple example):

  • AddArcWithCapacity()
  • Head()
  • GetSinkSideMinCut()
  • GetSourceSideMinCut()
  • NumArcs()
  • NumNodes()
  • OptimalFlow()
  • Solve()
  • Tail()

More detail on each of these is available on the SimpleMaxFlow reference page.

Enviar comentarios sobre…