Learning objectives
Algorithms from max_flow.h , min_cost_flow.h , and min_cut.h 
Maximum flows 
Maximum flows with minimum cost 
Minimum cuts 
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 nonnegative 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:
Capacity constraint: 0 <= f(e) <= cap(e), that is, no flow along an edge is negative or exceeds the feasible capacity.
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.
#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 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
.
A cut of a network divides it into two nonempty parts. Formally speaking, a cut is a partition (S,T) of the node set V into two nonempty 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 viceversa. An stcut 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 wellknown theorem from graph theory states that the maximum flow is always equal to the minimum stcut. Furthermore, the value of every flow is less or equal to the value of every stcut. Therefore the cut from Figure 5.23 is also a minimum stcut. 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 stcut, nor a larger one; so this proves not only the minimality of the stcut 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 nonempty 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

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.
#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(); } }
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.
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.