doc/groups.dox
 changeset 210 81cfc04531e8 parent 209 765619b7cbb2 child 236 da953e387d31
equal 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