# Changeset 2514:57143c09dc20 in lemon-0.x for doc/groups.dox

Ignore:
Timestamp:
11/17/07 21:58:11 (16 years ago)
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@3379
Message:

Redesign the maximum flow algorithms

Redesigned interface
Preflow changed to use elevator
Edmonds-Karp does not use the ResGraphAdaptor?
Goldberg-Tarjan algorithm (Preflow with Dynamic Trees)
Dinitz-Sleator-Tarjan (Blocking flow with Dynamic Tree)

File:
1 edited

### Legend:

Unmodified
 r2500 feasible circulations. \image html flow.png \image latex flow.eps "Graph flow" width=\textwidth The maximum flow problem is to find a flow between a single-source and 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. */