doc/groups.dox
changeset 225 c5a40fc54f1a
parent 209 765619b7cbb2
child 236 da953e387d31
equal deleted inserted replaced
7:1a4b0b76efe6 8:738add9f4cce
   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