### 5.3.4. Network flow algorithms

Learning objectives

 Algorithms from `max_flow.h`, `min_cost_flow.h`, and `min_cut.h` Maximum flows Maximum flows with minimum cost Minimum cuts

#### Maximum flows

Each day, a parcel service wants to transport a maximum number of parcels from city s to city t. Each transport has to pass the intermediate cities a, b, c, or d, as depicted in Figure 5.21. Each individual transport route e=(x,y) from a city x to a city y has only a certain, limited capacity, that is, only a limited number cap(e) of parcels can be transported from city x to city y via e per day, because, for example, only a certain number of trucks is available on this route.

Of course, the number of parcels that can be forwarded from a city x per day cannot be larger than the number of parcels that arrive there. In the intermediate cities, all arriving parcels must be forwarded (per day); there shall be no stacking parcels. In the forwarding process, the capacity of a transport route may never be exceeded, though. Only in city t, the “sink”, parcels may be opened and used up - they vanish there; accordingly, parcels may be created and packed only in city s, the “source” - they come into existence there.

The problem of the parcel service is that it cannot modify the capacities of the transport routes; it only can define the forwarding of the parcels, that is, it can define how many parcels shall flow per day over each transport route without capacities being exceeded. It wants to define these flows such that a maximum possible number of parcels arrive in city t per day. In other words: It wants to generate a maximum flow from s to t. In doing so, it is not essential that the parcels are transported from s to t as fast as possible - it is essential that as many parcels as possible “vanish” in the sink per day.[41]

A directed graph G whose edges e carry a non-negative capacity information cap(e) is called a network. Let s, the source, and t, the sink, be two different nodes of G. A network flow from s to t in such a network is a mapping f that maps each edge e a value f(e) such that the following conditions are satisfied:

1. Capacity constraint: 0 <= f(e) <= cap(e), that is, no flow along an edge is negative or exceeds the feasible capacity.

2. Flow conservation: For each node except s and t the following holds: The sum of the f(e) over all edges e incident to v is equal to the sum of the f(g) over all edges g leaving v. This is known in physics as Kirchhoff's Law: The sum of the currents entering any node (that is, any junction of wires) equals the sum of the currents leaving that node.

The value of a flow f is “what arrives at t, but does not vanish there”, that is, the sum of the f(e) over all edges e incident to t minus the sum of the f(g) over all edges g leaving t. Due to the flow conservation, the value of a flow also equals the sum of the flows leaving s minus the sum of the flows entering s.

A maximum flow from s to t is a flow with a maximum value. It can be shown that there is always a flow with a maximum value in which the sum of the flows leaving t and the sum of the flows entering s both are 0. Therefore, edges incident to s or leaving t may be neglected in the computation of a maximum flow (see also Exercise 66 for this).

Figure 5.22 shows such a maximum flow for the network from Figure 5.21: In a labeling “f/c” of an edge, f stands for the flow that is routed over this edge and c for the capacity of this edge. (We shall soon see why this flow indeed is maximum.)

For computing such maximum flows, LEDA offers some functions, which are declared in the header file `max_flow.h`.

As an example of these, we show the usage of the function `MAX_FLOW()`:

```int MAX_FLOW(graph& G,
node s, node t,
edge_array<int>& cap,
edge_array<int>& f);```

Besides the directed graph `graph G`, this function expects the source `s` and the sink `t`, as well as an edge array `cap` valid on `G` that holds the capacities of the edges, and an edge array `f` valid on `G`, in which it will store the individual flow values of the maximum flow computed. It returns the value of the maximum flow computed.

The following program lets the user edit a (directed) graph. He must label the data labels of the edges with the capacities. (The values input are not yet shown at first!) Then he may select two nodes. The first one is regarded as the source, the second one as the sink, and `MAX_FLOW()` is called. The program then labels the user labels of the edges with strings of the shape “f/c”, with c being the capacity taken from the data label and f the value of the flow over this edge in the computed maximum flow. Figure 5.22 has been created with it.

Filename: MaximumFlow.C
LEDA users as of version 5.0: Note that header files are now partitioned into modules (subfolders)!
```#include <LEDA/max_flow.h>
#include <LEDA/graph.h>
#include <LEDA/edge_array.h>
#include <LEDA/graphwin.h>
#include <LEDA/list.h>
#include <iostream>

using leda::GRAPH;
using leda::GraphWin;
using leda::window;
using leda::node;
using leda::edge;
using leda::edge_array;
using leda::list;
using leda::string;

int main()
{
GRAPH<string,int> G;

GraphWin gw(G, 500, 500, "Maximum Flow");
gw.set_edge_label_type(leda::data_label);
gw.set_node_label_type(leda::data_label);
gw.set_node_border_width(2);
gw.set_flush(false);
gw.display(window::center,window::center);

while(gw.edit()) {

// get source s and sink t
// as the two selected nodes of GraphWin
node s, t;
list<node> L = gw.get_selected_nodes();
if(L.size() != 2) {
gw.message("Select exactly 2 nodes! Click <done>.");
gw.wait();
gw.del_message();
continue;
}
else {
s = L.tail(); // get_selected_nodes() pushes new nodes
t = L.head(); // to the front; so reverse order here
}

// setup cost information: use information associated to GRAPH<,>
edge_array<int> cap(G);
edge e;
forall_edges(e, G)
cap[e] = G.inf(e);

// define edge array on G for flow values
edge_array<int> f(G);

// compute maximum flow from s to t
int max_flow = MAX_FLOW(G, s, t, cap, f);

forall_edges(e, G)
gw.set_user_label(e,
string("%ld", f[e]) + "/" + string("%ld", cap[e]));
gw.set_edge_label_type(leda::user_label);
gw.redraw();

gw.message("The value of a maximum flow from "
+ G.inf(s) + " to " + G.inf(t) + " is "
+ string("%ld", max_flow) + ". Click <done>.");
gw.wait();
gw.del_message();
gw.redraw();
}

}
```

#### Maximum flows with minimum cost

Maximum flows need not to be unique; there may be several possibilities for generating a maximum flow from s to t. This allows for a generalization of the problem definition:

Let us additionally imagine in Figure 5.21 that transporting a parcel over an edge causes costs that differ from edge to edge, that is, that each edge e is labeled with an additional cost information cost(e). So the transport of f(e) parcels over edge e costs f(e)·cost(e) silver dollars per day. The parcel service then wants to realize a maximum flow with minimum cost, that is, a maximum flow f that minimizes the sum over all f(e)·cost(e).

LEDA offers some functions for computing such maximum flows with minimum cost. They are declared in the header file `min_cost_flow.h`.

For example, the function

```int MIN_COST_MAX_FLOW(graph& G,
node s, node t,
edge_array<int>& cap,
edge_array<int>& cost,
edge_array<int>& f);```

expects the costs of the edges as an argument in an additional edge array `cost`. It returns the value of a maximum flow with minimum cost and stores the flow values of this flow in the edge array `f`.

#### Minimum cuts

A cut of a network divides it into two non-empty parts. Formally speaking, a cut is a partition (S,T) of the node set V into two non-empty subsets S and T. Figure 5.23 shows a cut of the graph of Figure 5.21.

A cut edge is an edge that is crossed by the cut, that is, whose source belongs to S and whose target belongs to T, or vice-versa. An s-t-cut is a cut (S,T) that separates the source s from the sink t in the sets S and T.

The value of a cut is the sum of all weights (capacities) of all edges that cross the cut from S to T, that is, whose source belongs to S and whose target belongs to T. A minimum cut cut is a cut of minimum value.

A well-known theorem from graph theory states that the maximum flow is always equal to the minimum s-t-cut. Furthermore, the value of every flow is less or equal to the value of every s-t-cut. Therefore the cut from Figure 5.23 is also a minimum s-t-cut. The value of this cut is 120, and since we see a flow also with value 120 in Figure 5.22, there can be neither a smaller s-t-cut, nor a larger one; so this proves not only the minimality of the s-t-cut from Figure 5.23, but also the maximality of the flow from Figure 5.22.

For computing minimum cuts, LEDA offers some functions, which are declared in the header file `min_cut.h`.

Important LEDA defines the term “cut” with respect to undirected graphs: A cut is a partition of the node set into two non-empty subsets S and T. The value of a cut is the sum of all weights (capacities) of all edges that have one end point in S and the other end point in T. So it is not essential in which direction the edges cross the cut.Moreover, the functions from `min_cut.h` compute a minimum cut without taking into account a designated source s and a designated sink t; so all possible cuts are taken into consideration.

For example, the function

`int MIN_CUT(graph& G, edge_array<int>& cap, list<node>& C);`

returns the value of a minimum cut and stores one of the two subsets S and T of this cut in the list `C`.

In Figure 5.23, this function returns the value 120 and partitions the node set into S={s,a,c} and T={b,d,t}. Here it happens more or less by chance that, in addition, this partition yields a minimum cut that proves the maximality of the flow from Figure 5.22.

The following program lets the user edit a (directed) graph. He must label the data labels of the edges with the weights (capacities). `MIN_CUT()` then computes a minimum cut of the network specified in this manner. (Again we note that there is no designated source and sink here.) The nodes of the subset T are made visible with a rectangular frame; edges that cross the cut are drawn thick. Figure 5.23 has been created with it.

Filename: MinimumCut.C
LEDA users as of version 5.0: Note that header files are now partitioned into modules (subfolders)!
```#include <LEDA/min_cut.h>
#include <LEDA/graph.h>
#include <LEDA/edge_array.h>
#include <LEDA/graphwin.h>
#include <LEDA/list.h>
#include <iostream>

using leda::GRAPH;
using leda::GraphWin;
using leda::window;
using leda::node;
using leda::edge;
using leda::edge_array;
using leda::list;
using leda::string;

int main()
{
GRAPH<string,int> G;

GraphWin gw(G, 500, 500, "Minimum Cut");
gw.set_edge_label_type(leda::data_label);
gw.set_node_label_type(leda::data_label);
gw.set_node_border_width(2);
gw.set_flush(false);
gw.display(window::center,window::center);

while(gw.edit()) {

// setup cost information: use information associated to GRAPH<,>
edge_array<int> weight(G);
edge e;
forall_edges(e,G)
weight[e] = G.inf(e);

// compute minimum cut
list<node> cut_nodes;
int min_cut= MIN_CUT(G, weight, cut_nodes);

// minimum cut may have changed; reset attribute values
gw.set_node_shape(leda::circle_node);

// show cut nodes as rectangular nodes
gw.set_shape(cut_nodes, leda::rectangle_node);
gw.set_edge_width(1);
gw.set_edge_color(leda::black);

// show cut edges thick and red
forall_edges(e, G) {
node s = G.source(e);
node t = G.target(e);
// is e a cut edge? the following is not an efficient search!
if(cut_nodes.search(s) && !cut_nodes.search(t)
|| !cut_nodes.search(s) && cut_nodes.search(t)) {
gw.set_width(e, 4);
gw.set_color(e, leda::red);
}
}

gw.message("The value of a minimum cut is "
+ string("%ld",min_cut)+ ". Click <done>.");
gw.wait();
gw.del_message();
gw.redraw();
}

}
```

#### Further information

More information about these functions can be found on the corresponding manual pages of `max_flow.h`, `min_cost_flow.h` and `min_cut.h`.

For example, the function `MIN_COST_FLOW()` allows to solve a generalized flow problem: Each edge has a minimum and a maximum capacity and a cost information. In addition, each node may be source or sink; it may specify how much flow (per time unit) it feeds into the network or extracts from it. This function computes a flow with minimum cost that satisfies all these constraints.

#### Exercises

 Exercise 66. The definition of a network flow previously given does not forbid edges leaving t or incident to s, over which flow may be transported also; the network from Figure 5.22 could look also like in Figure 5.24. LEDA's functions for computing maximum flows do not guarantee that they compute the flows that are transported over such edges in a maximum flow to be 0. Work out when such flows can be different from 0, and why, even in this case, the value of a maximum flow does not change.

[41] In the beginning, that is, on the first day, there are no parcels in the network, of course. Not until after some days, the first parcels arrive at t. From this moment on, however, the network is in a stable state, that is, as many parcels vanish in the sink as parcels are fed in from the source. In the intermediate cities, no parcels stack up and no additional parcels are fed in; merely the arriving parcels are forwarded. When we talk of a network flow here, we only talk about these stable states, not about the start phase in which the network is filled with parcels.