r713:4ac30454f1c1
Fri, 24 Jul 2009 10:27:40
[Not Reviewed]
0 comments (0 inline)
0
8
0
4
4
4
4
12
5
| ... | ... |
@@ -376,5 +376,5 @@ |
| 376 | 376 |
|
| 377 | 377 |
\f[ \min_{X \subset V, X\not\in \{\emptyset, V\}}
|
| 378 |
\sum_{uv\in A
|
|
| 378 |
\sum_{uv\in A: u\in X, v\not\in X}cap(uv) \f]
|
|
| 379 | 379 |
|
| 380 | 380 |
LEMON contains several algorithms related to minimum cut problems: |
| ... | ... |
@@ -399,6 +399,6 @@ |
| 399 | 399 |
like connectivity, bipartiteness, euler property, simplicity etc. |
| 400 | 400 |
|
| 401 |
\image html edge_biconnected_components.png |
|
| 402 |
\image latex edge_biconnected_components.eps "bi-edge-connected components" width=\textwidth |
|
| 401 |
\image html connected_components.png |
|
| 402 |
\image latex connected_components.eps "Connected components" width=\textwidth |
|
| 403 | 403 |
*/ |
| 404 | 404 |
| ... | ... |
@@ -414,6 +414,6 @@ |
| 414 | 414 |
///The simplest way to execute the BFS algorithm is to use one of the |
| 415 | 415 |
///member functions called \ref run(Node) "run()".\n |
| 416 |
///If you need more control on the execution, first you have to call |
|
| 417 |
///\ref init(), then you can add several source nodes with |
|
| 416 |
///If you need better control on the execution, you have to call |
|
| 417 |
///\ref init() first, then you can add several source nodes with |
|
| 418 | 418 |
///\ref addSource(). Finally the actual path computation can be |
| 419 | 419 |
///performed with one of the \ref start() functions. |
| ... | ... |
@@ -1426,6 +1426,6 @@ |
| 1426 | 1426 |
/// The simplest way to execute the BFS algorithm is to use one of the |
| 1427 | 1427 |
/// member functions called \ref run(Node) "run()".\n |
| 1428 |
/// If you need more control on the execution, first you have to call |
|
| 1429 |
/// \ref init(), then you can add several source nodes with |
|
| 1428 |
/// If you need better control on the execution, you have to call |
|
| 1429 |
/// \ref init() first, then you can add several source nodes with |
|
| 1430 | 1430 |
/// \ref addSource(). Finally the actual path computation can be |
| 1431 | 1431 |
/// performed with one of the \ref start() functions. |
| ... | ... |
@@ -73,5 +73,9 @@ |
| 73 | 73 |
/// It must conform to the \ref concepts::ReadWriteMap "ReadWriteMap" |
| 74 | 74 |
/// concept. |
| 75 |
#ifdef DOXYGEN |
|
| 76 |
typedef GR::ArcMap<Value> FlowMap; |
|
| 77 |
#else |
|
| 75 | 78 |
typedef typename Digraph::template ArcMap<Value> FlowMap; |
| 79 |
#endif |
|
| 76 | 80 |
|
| 77 | 81 |
/// \brief Instantiates a FlowMap. |
| ... | ... |
@@ -88,7 +92,10 @@ |
| 88 | 92 |
/// The elevator type used by the algorithm. |
| 89 | 93 |
/// |
| 90 |
/// \sa Elevator |
|
| 91 |
/// \sa LinkedElevator |
|
| 94 |
/// \sa Elevator, LinkedElevator |
|
| 95 |
#ifdef DOXYGEN |
|
| 96 |
typedef lemon::Elevator<GR, GR::Node> Elevator; |
|
| 97 |
#else |
|
| 92 | 98 |
typedef lemon::Elevator<Digraph, typename Digraph::Node> Elevator; |
| 99 |
#endif |
|
| 93 | 100 |
|
| 94 | 101 |
/// \brief Instantiates an Elevator. |
| ... | ... |
@@ -468,6 +475,6 @@ |
| 468 | 475 |
/// \name Execution Control |
| 469 | 476 |
/// The simplest way to execute the algorithm is to call \ref run().\n |
| 470 |
/// If you need more control on the initial solution or the execution, |
|
| 471 |
/// first you have to call one of the \ref init() functions, then |
|
| 477 |
/// If you need better control on the initial solution or the execution, |
|
| 478 |
/// you have to call one of the \ref init() functions first, then |
|
| 472 | 479 |
/// the \ref start() function. |
| 473 | 480 |
| ... | ... |
@@ -412,6 +412,6 @@ |
| 412 | 412 |
///The simplest way to execute the DFS algorithm is to use one of the |
| 413 | 413 |
///member functions called \ref run(Node) "run()".\n |
| 414 |
///If you need more control on the execution, first you have to call |
|
| 415 |
///\ref init(), then you can add a source node with \ref addSource() |
|
| 414 |
///If you need better control on the execution, you have to call |
|
| 415 |
///\ref init() first, then you can add a source node with \ref addSource() |
|
| 416 | 416 |
///and perform the actual computation with \ref start(). |
| 417 | 417 |
///This procedure can be repeated if there are nodes that have not |
| ... | ... |
@@ -1370,6 +1370,6 @@ |
| 1370 | 1370 |
/// The simplest way to execute the DFS algorithm is to use one of the |
| 1371 | 1371 |
/// member functions called \ref run(Node) "run()".\n |
| 1372 |
/// If you need more control on the execution, first you have to call |
|
| 1373 |
/// \ref init(), then you can add a source node with \ref addSource() |
|
| 1372 |
/// If you need better control on the execution, you have to call |
|
| 1373 |
/// \ref init() first, then you can add a source node with \ref addSource() |
|
| 1374 | 1374 |
/// and perform the actual computation with \ref start(). |
| 1375 | 1375 |
/// This procedure can be repeated if there are nodes that have not |
| ... | ... |
@@ -585,6 +585,6 @@ |
| 585 | 585 |
///The simplest way to execute the %Dijkstra algorithm is to use |
| 586 | 586 |
///one of the member functions called \ref run(Node) "run()".\n |
| 587 |
///If you need more control on the execution, first you have to call |
|
| 588 |
///\ref init(), then you can add several source nodes with |
|
| 587 |
///If you need better control on the execution, you have to call |
|
| 588 |
///\ref init() first, then you can add several source nodes with |
|
| 589 | 589 |
///\ref addSource(). Finally the actual path computation can be |
| 590 | 590 |
///performed with one of the \ref start() functions. |
| ... | ... |
@@ -360,8 +360,8 @@ |
| 360 | 360 |
/// \c t. |
| 361 | 361 |
/// \code |
| 362 |
/// |
|
| 362 |
/// GomoryHu<Graph> gom(g, capacities); |
|
| 363 | 363 |
/// gom.run(); |
| 364 | 364 |
/// int cnt=0; |
| 365 |
/// for( |
|
| 365 |
/// for(GomoryHu<Graph>::MinCutNodeIt n(gom,s,t); n!=INVALID; ++n) ++cnt; |
|
| 366 | 366 |
/// \endcode |
| 367 | 367 |
class MinCutNodeIt |
| ... | ... |
@@ -457,8 +457,8 @@ |
| 457 | 457 |
/// \c t. |
| 458 | 458 |
/// \code |
| 459 |
/// |
|
| 459 |
/// GomoryHu<Graph> gom(g, capacities); |
|
| 460 | 460 |
/// gom.run(); |
| 461 | 461 |
/// int value=0; |
| 462 |
/// for( |
|
| 462 |
/// for(GomoryHu<Graph>::MinCutEdgeIt e(gom,s,t); e!=INVALID; ++e) |
|
| 463 | 463 |
/// value+=capacities[e]; |
| 464 | 464 |
/// \endcode |
| ... | ... |
@@ -489,6 +489,6 @@ |
| 489 | 489 |
/// The simplest way to execute the algorithm is to use |
| 490 | 490 |
/// one of the member functions called \c run(...). \n |
| 491 |
/// If you need more control on the execution, |
|
| 492 |
/// first you must call \ref init(), then you can add several |
|
| 491 |
/// If you need better control on the execution, |
|
| 492 |
/// you have to call \ref init() first, then you can add several |
|
| 493 | 493 |
/// source nodes with \ref addSource(). |
| 494 | 494 |
/// Finally \ref start() will perform the arborescence |
| ... | ... |
@@ -53,5 +53,9 @@ |
| 53 | 53 |
/// The type of the map that stores the flow values. |
| 54 | 54 |
/// It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept. |
| 55 |
#ifdef DOXYGEN |
|
| 56 |
typedef GR::ArcMap<Value> FlowMap; |
|
| 57 |
#else |
|
| 55 | 58 |
typedef typename Digraph::template ArcMap<Value> FlowMap; |
| 59 |
#endif |
|
| 56 | 60 |
|
| 57 | 61 |
/// \brief Instantiates a FlowMap. |
| ... | ... |
@@ -68,7 +72,10 @@ |
| 68 | 72 |
/// The elevator type used by Preflow algorithm. |
| 69 | 73 |
/// |
| 70 |
/// \sa Elevator |
|
| 71 |
/// \sa LinkedElevator |
|
| 72 |
|
|
| 74 |
/// \sa Elevator, LinkedElevator |
|
| 75 |
#ifdef DOXYGEN |
|
| 76 |
typedef lemon::Elevator<GR, GR::Node> Elevator; |
|
| 77 |
#else |
|
| 78 |
typedef lemon::Elevator<Digraph, typename Digraph::Node> Elevator; |
|
| 79 |
#endif |
|
| 73 | 80 |
|
| 74 | 81 |
/// \brief Instantiates an Elevator. |
| ... | ... |
@@ -390,6 +397,6 @@ |
| 390 | 397 |
/// The simplest way to execute the preflow algorithm is to use |
| 391 | 398 |
/// \ref run() or \ref runMinCut().\n |
| 392 |
/// If you need more control on the initial solution or the execution, |
|
| 393 |
/// first you have to call one of the \ref init() functions, then |
|
| 399 |
/// If you need better control on the initial solution or the execution, |
|
| 400 |
/// you have to call one of the \ref init() functions first, then |
|
| 394 | 401 |
/// \ref startFirstPhase() and if you need it \ref startSecondPhase(). |
| 395 | 402 |
|
0 comments (0 inline)