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.

Figure 5.21. A network

A network

Each edge is labeled with its capacity. s is the source of the network, and t is the sink.


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.)

Figure 5.22. A maximum flow

A maximum flow

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. The mapping f is a flow because it satisfies the conditions of the capacity constraint and the flow conservation. f is even a maximum flow with value 120; this is equal to the sum of the flows of the edges incident to t and equal to the sum of the flows of the edges leaving s. The flow is maximum because there is a cut {s,a,c} and {b,d,t} with also a value of 120; see also Section “Minimum cuts” for this.


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.

Figure 5.23. A minimum cut

A minimum cut

A cut of a network graph. The cut consists of the subsets S={s,a,c} and T={b,d,t}. The cut edges are drawn thick. The cut is an s-t-cut. The value of the cut is 60+30+30=120. It is also a minimum cut (with respect to the source s and the sink t), because there is a flow from s to t with value 120 in this network.


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]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.

Figure 5.24. A network with edges incident to the source and leaving the sink.

A network with edges incident to the source and leaving the sink.


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.




Imprint-Dataprotection