# Network Flows

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.

The first person to study this problem was the Russian mathematician A.N.
Tolstoi, in the 1930s. The following map shows the actual railway network for
which he wanted to find a maximum flow. The map itself comes from "Theodore E.
Harris and Frank S. Ross. Fundamentals of a method for evaluating rail net
capacities. Research Memorandum RM-1573, The RAND Corporation, Santa Monica,
California, October 24, 1955. Declassified May 13, 1999".

![a railway network map](https://developers.google.com/static/optimization/images/railway_network.png)

OR-Tools provides several solvers for network flow problems in its
[graph](https://or-tools.github.io/docs/cpp/index.html) libraries.

The following sections present examples of network flow problems and show how to
solve them:

- [Maximum Flows](https://developers.google.com/optimization/flow/maxflow)
- [Minimum Cost Flows](https://developers.google.com/optimization/flow/mincostflow)
- [Assignment as a Minimum Cost Flows](https://developers.google.com/optimization/flow/assignment_min_cost_flow#example)
- [Assignment with Teams of Workers](https://developers.google.com/optimization/flow/assignment_min_cost_flow#teams-workers)