COIN-OR::LEMON - Graph Library

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


Ignore:
Timestamp:
11/17/07 21:58:11 (16 years ago)
Author:
Balazs Dezso
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
Added
Removed
  • doc/groups.dox

    r2500 r2514  
    224224feasible circulations.
    225225
    226 \image html flow.png
    227 \image latex flow.eps "Graph flow" width=\textwidth
     226The maximum flow problem is to find a flow between a single-source and
     227single-target that is maximum. Formally, there is \f$G=(V,A)\f$
     228directed graph, an \f$c_a:A\rightarrow\mathbf{R}^+_0\f$ capacity
     229function and given \f$s, t \in V\f$ source and target node. The
     230maximum flow is the solution of the next optimization problem:
     231
     232\f[ 0 \le f_a \le c_a \f]
     233\f[ \sum_{v\in\delta^{-}(u)}f_{vu}=\sum_{v\in\delta^{+}(u)}f_{uv} \quad u \in V \setminus \{s,t\}\f]
     234\f[ \max \sum_{v\in\delta^{+}(s)}f_{uv} - \sum_{v\in\delta^{-}(s)}f_{vu}\f]
     235
     236The lemon contains several algorithms for solve maximum flow problems:
     237- \ref lemon::EdmondsKarp "Edmonds-Karp"
     238- \ref lemon::Preflow "Goldberg's Preflow algorithm"
     239- \ref lemon::DinitzSleatorTarjan "Dinitz's blocking flow algorithm with dynamic tree"
     240- \ref lemon::GoldbergTarjan "Preflow algorithm with dynamic trees"
     241
     242In most cases the \ref lemon::Preflow "preflow" algorithm provides the
     243fastest method to compute the maximum flow. All impelementations
     244provides functions for query the minimum cut, which is the dual linear
     245programming probelm of the maximum flow.
     246
    228247*/
    229248
Note: See TracChangeset for help on using the changeset viewer.