\image html flow.png

 The maximum flow problem is to find a flow between a single-source and

 \image latex flow.eps "Graph flow" width=\textwidth

 single-target that is maximum. Formally, there is \f$G=(V,A)\f$

 directed graph, an \f$c_a:A\rightarrow\mathbf{R}^+_0\f$ capacity

 function and given \f$s, t \in V\f$ source and target node. The

 maximum flow is the solution of the next optimization problem:

 \f[ 0 \le f_a \le c_a \f]

 \f[ \sum_{v\in\delta^{-}(u)}f_{vu}=\sum_{v\in\delta^{+}(u)}f_{uv} \quad u \in V \setminus \{s,t\}\f]

 \f[ \max \sum_{v\in\delta^{+}(s)}f_{uv} - \sum_{v\in\delta^{-}(s)}f_{vu}\f]

 The lemon contains several algorithms for solve maximum flow problems:

 - \ref lemon::EdmondsKarp "Edmonds-Karp" 

 - \ref lemon::Preflow "Goldberg's Preflow algorithm"

 - \ref lemon::DinitzSleatorTarjan "Dinitz's blocking flow algorithm with dynamic tree"

 - \ref lemon::GoldbergTarjan "Preflow algorithm with dynamic trees"

 In most cases the \ref lemon::Preflow "preflow" algorithm provides the

 fastest method to compute the maximum flow. All impelementations

 provides functions for query the minimum cut, which is the dual linear

 programming probelm of the maximum flow.