equal
deleted
inserted
replaced
225 directed graph, an \f$c_a:A\rightarrow\mathbf{R}^+_0\f$ capacity |
225 directed graph, an \f$c_a:A\rightarrow\mathbf{R}^+_0\f$ capacity |
226 function and given \f$s, t \in V\f$ source and target node. The |
226 function and given \f$s, t \in V\f$ source and target node. The |
227 maximum flow is the \f$f_a\f$ solution of the next optimization problem: |
227 maximum flow is the \f$f_a\f$ solution of the next optimization problem: |
228 |
228 |
229 \f[ 0 \le f_a \le c_a \f] |
229 \f[ 0 \le f_a \le c_a \f] |
230 \f[ \sum_{v\in\delta^{-}(u)}f_{vu}=\sum_{v\in\delta^{+}(u)}f_{uv} \qquad \forall u \in V \setminus \{s,t\}\f] |
230 \f[ \sum_{v\in\delta^{-}(u)}f_{vu}=\sum_{v\in\delta^{+}(u)}f_{uv} |
|
231 \qquad \forall u \in V \setminus \{s,t\}\f] |
231 \f[ \max \sum_{v\in\delta^{+}(s)}f_{uv} - \sum_{v\in\delta^{-}(s)}f_{vu}\f] |
232 \f[ \max \sum_{v\in\delta^{+}(s)}f_{uv} - \sum_{v\in\delta^{-}(s)}f_{vu}\f] |
232 |
233 |
233 LEMON contains several algorithms for solving maximum flow problems: |
234 LEMON contains several algorithms for solving maximum flow problems: |
234 - \ref lemon::EdmondsKarp "Edmonds-Karp" |
235 - \ref lemon::EdmondsKarp "Edmonds-Karp" |
235 - \ref lemon::Preflow "Goldberg's Preflow algorithm" |
236 - \ref lemon::Preflow "Goldberg's Preflow algorithm" |
265 \f$X\f$ subset of the vertices with minimum overall capacity on |
266 \f$X\f$ subset of the vertices with minimum overall capacity on |
266 outgoing arcs. Formally, there is \f$G=(V,A)\f$ directed graph, an |
267 outgoing arcs. Formally, there is \f$G=(V,A)\f$ directed graph, an |
267 \f$c_a:A\rightarrow\mathbf{R}^+_0\f$ capacity function. The minimum |
268 \f$c_a:A\rightarrow\mathbf{R}^+_0\f$ capacity function. The minimum |
268 cut is the \f$X\f$ solution of the next optimization problem: |
269 cut is the \f$X\f$ solution of the next optimization problem: |
269 |
270 |
270 \f[ \min_{X \subset V, X\not\in \{\emptyset, V\}}\sum_{uv\in A, u\in X, v\not\in X}c_{uv}\f] |
271 \f[ \min_{X \subset V, X\not\in \{\emptyset, V\}} |
|
272 \sum_{uv\in A, u\in X, v\not\in X}c_{uv}\f] |
271 |
273 |
272 LEMON contains several algorithms related to minimum cut problems: |
274 LEMON contains several algorithms related to minimum cut problems: |
273 |
275 |
274 - \ref lemon::HaoOrlin "Hao-Orlin algorithm" to calculate minimum cut |
276 - \ref lemon::HaoOrlin "Hao-Orlin algorithm" to calculate minimum cut |
275 in directed graphs |
277 in directed graphs |
298 /** |
300 /** |
299 @defgroup planar Planarity embedding and drawing |
301 @defgroup planar Planarity embedding and drawing |
300 @ingroup algs |
302 @ingroup algs |
301 \brief Algorithms for planarity checking, embedding and drawing |
303 \brief Algorithms for planarity checking, embedding and drawing |
302 |
304 |
303 This group describes the algorithms for planarity checking, embedding and drawing. |
305 This group describes the algorithms for planarity checking, |
|
306 embedding and drawing. |
304 |
307 |
305 \image html planar.png |
308 \image html planar.png |
306 \image latex planar.eps "Plane graph" width=\textwidth |
309 \image latex planar.eps "Plane graph" width=\textwidth |
307 */ |
310 */ |
308 |
311 |
475 /** |
478 /** |
476 @defgroup lemon_io Lemon Input-Output |
479 @defgroup lemon_io Lemon Input-Output |
477 @ingroup io_group |
480 @ingroup io_group |
478 \brief Reading and writing \ref lgf-format "Lemon Graph Format". |
481 \brief Reading and writing \ref lgf-format "Lemon Graph Format". |
479 |
482 |
480 This group describes methods for reading and writing \ref lgf-format "Lemon Graph Format". |
483 This group describes methods for reading and writing |
|
484 \ref lgf-format "Lemon Graph Format". |
481 */ |
485 */ |
482 |
486 |
483 /** |
487 /** |
484 @defgroup eps_io Postscript exporting |
488 @defgroup eps_io Postscript exporting |
485 @ingroup io_group |
489 @ingroup io_group |