Maximum Flow ( max_flow )

Let G = (V, E) be a directed graph, let s and t be distinct vertices in G and let cap : E - > IR_{$\ge$ 0} be a non-negative function on the edges of G. For an edge e, we call cap(e) the capacity of e. An (s, t)-flow or simply flow is a function f : E - > IR_{$\ge$ 0} satisfying the capacity constraints and the flow conservation constraints:

$\begin{array}{lcl} (1) & 0<= f(e)<= cap(e) & \mbox{ for every edge } e\mathrm{... ...\mathrm{\ in\ } V\backslash \{\hspace{0.05em}s,t\hspace{0.05em} \} \end{array}$

The value of the flow in the net flow into t (equivalently, the net flow out of s). The net flow into t is the flow into t minus the flow out of t. A flow is maximum if its value is at least as large as the value of any other flow.

All max flow implementations can be used with any number type NT. It is unsafe however, to use them for number types that incur rounding error; see the LEDA book for an example of what might go wrong. Non-integral capacities should be scaled to integral capacities when using a number type that may incur rounding error. If all capacities are integral and bounded by C then all intermediate values handled by the algorithm are integers bounded by nC. Only additions and subtractions are used in the algorithms.

In order to use any of the template functions the files

#include <LEDA/graph_algs.h>
#include <LEDA/templates/max_flow.t>

must be included. The functions MAX_FLOW_T and CHECK_MAX_FLOW_T are pre-instantiated for the number types int and double. The pre-instantiated versions have the names MAX_FLOW and CHECK_MAX_FLOW, respectively. In order to use them it suffices to include

#include <LEDA/graph_algs.h>

The following functions are available:

NT	MAX_FLOW_T(graph G, node s, node t, edge_array<NT> cap, edge_array<NT>& f)
		computes a maximum (s, t)-flow f in the network (G, s, t, cap) and returns the value of the flow. The implementation uses the preflow-push method of Goldberg and Tarjan [39] with the local and global relabeling heuristic and the gap heuristic. The highest level rule is used to select active nodes. The section on maximum flow of the LEDA book gives full information.
NT	MAX_FLOW_T(graph G, node s, node t, edge_array<NT> cap, edge_array<NT>& f, int& num_pushes, int& num_edge_inspections, int& num_relabels, int& num_global_relabels, int& num_gaps, float h)
		as above; The additional parameter report some statistics of the execution (the number of pushes, the number of edge inspections, the number of relabels, the number of global relabels, and the number of nodes moved by the gap heuristic. The parameter h controls the global relabeling heuristic. The global relabeling heuristic is called every h*m edge inspections. The choice h = 5 seems reasonable.
void	CHECK_MAX_FLOW_T(graph G, node s, node t, edge_array<NT> cap, edge_array<NT> f)
		checks whether f is a maximum flow in the network (G, s, t, cap). The functions aborts if this is not the case.

The following functions are only available in template form. They allow to study the effect of different heuristics and of different selection rules on the preflow push method. The class SET must provide the following operations: construction, destruction, del, insert, insert0, and clear; see the LEDA book for details. Three implementations are part of the distribution: fifo_set, hl_set, and mfifo_set.

NT	MAX_FLOW_BASIC_T(graph G, node s, node t, edge_array<NT> cap, edge_array<NT>& flow, SET& U, int& num_pushes, int& num_edge_inspections, int& num_relabels)
		The basic version of the preflow push algorithm: No heuristic is used.
NT	MAX_FLOW_LH_T(graph G, node s, node t, edge_array<NT> cap, edge_array<NT>& flow, SET& U, int& num_pushes, int& num_edge_inspections, int& num_relabels)
		The preflow push method with the distinction between low and high nodes.
NT	MAX_FLOW_LRH_T(graph G, node s, node t, edge_array<NT> cap, edge_array<NT>& flow, SET& U, int& num_pushes, int& num_edge_inspections, int& num_relabels)
		The preflow push method with the distinction between low and high nodes and the local relabeling heuristic.
NT	MAX_FLOW_GRH_T(graph G, node s, node t, edge_array<NT> cap, edge_array<NT>& flow, SET& U, int& num_pushes, int& num_edge_inspections, int& num_relabels, int& num_global_relabels, float h)
		The preflow push method with the distinction between low and high nodes, the local relabeling heuristic, the global relabeling heuristic, and the two-phase approach. The global relabeling heuristic is applied every h*m edge inspections.
NT	MAX_FLOW_GAP_T(graph G, node s, node t, edge_array<NT> cap, edge_array<NT>& flow, SET& U, int& num_pushes, int& num_edge_inspections, int& num_relabels, int& num_global_relabels, int& num_gaps, float h)
		The preflow push method with the distinction between low and high nodes, the local relabeling heuristic, the global relabeling heuristic, the two-phase approach, and the gap heuristic. The global relabeling heuristic is applied every h*m edge inspections.

The following generators can be used to generate max-flow problems with integer capacities. The generators return a GRAPH<int,int> G and nodes s and t. The edge capacities are available as edge data, i.e., the capacity of edge e is available as G[e] and the edge array of capacities is passed as G.edge_data(). For detailed information about the generators we refer to the LEDA book.

void	max_flow_gen_rand(GRAPH<int,int>& G, node& s, node& t, int n, int m)
		A random graph with n nodes, m edges, and random edge capacities in [2,11] for the edges out of s and in [1,10] for all other edges.
void	max_flow_gen_CG1(GRAPH<int,int>& G, node& s, node& t, int n)
		A generator suggested by Cherkassky and Goldberg.
void	max_flow_gen_CG2(GRAPH<int,int>& G, node& s, node& t, int n)
		Another generator suggested by Cherkassky and Goldberg.
void	max_flow_gen_AMO(GRAPH<int,int>& G, node& s, node& t, int n)
		A generator suggested by Ahuja, Magnanti, and Orlin.
int	MAX_FLOWS(graph& G, node s, node t, edge_array<int> cap, edge_array<int>& flow, int h=0)
double	MAX_FLOWS(graph& G, node s, node t, edge_array<double> cap, edge_array<double>& flow, int h=0)