r651:3adf5e2d1e62
Thu, 07 May 2009 02:07:59
[Not Reviewed]
0 comments (0 inline)
0
3
0
| ... | ... |
@@ -330,18 +330,23 @@ |
| 330 | 330 |
LEMON contains several algorithms for solving maximum flow problems: |
| 331 | 331 |
- \ref EdmondsKarp Edmonds-Karp algorithm. |
| 332 | 332 |
- \ref Preflow Goldberg-Tarjan's preflow push-relabel algorithm. |
| 333 | 333 |
- \ref DinitzSleatorTarjan Dinitz's blocking flow algorithm with dynamic trees. |
| 334 | 334 |
- \ref GoldbergTarjan Preflow push-relabel algorithm with dynamic trees. |
| 335 | 335 |
|
| 336 | 336 |
In most cases the \ref Preflow "Preflow" algorithm provides the |
| 337 | 337 |
fastest method for computing a maximum flow. All implementations |
| 338 |
provides functions to also query the minimum cut, which is the dual |
|
| 339 |
problem of the maximum flow. |
|
| 338 |
also provide functions to query the minimum cut, which is the dual |
|
| 339 |
problem of maximum flow. |
|
| 340 |
|
|
| 341 |
\ref Circulation is a preflow push-relabel algorithm implemented directly |
|
| 342 |
for finding feasible circulations, which is a somewhat different problem, |
|
| 343 |
but it is strongly related to maximum flow. |
|
| 344 |
For more information, see \ref Circulation. |
|
| 340 | 345 |
*/ |
| 341 | 346 |
|
| 342 | 347 |
/** |
| 343 | 348 |
@defgroup min_cost_flow Minimum Cost Flow Algorithms |
| 344 | 349 |
@ingroup algs |
| 345 | 350 |
|
| 346 | 351 |
\brief Algorithms for finding minimum cost flows and circulations. |
| 347 | 352 |
|
| ... | ... |
@@ -536,20 +541,20 @@ |
| 536 | 541 |
|
| 537 | 542 |
\image html bipartite_matching.png |
| 538 | 543 |
\image latex bipartite_matching.eps "Bipartite Matching" width=\textwidth |
| 539 | 544 |
*/ |
| 540 | 545 |
|
| 541 | 546 |
/** |
| 542 | 547 |
@defgroup spantree Minimum Spanning Tree Algorithms |
| 543 | 548 |
@ingroup algs |
| 544 |
\brief Algorithms for finding |
|
| 549 |
\brief Algorithms for finding minimum cost spanning trees and arborescences. |
|
| 545 | 550 |
|
| 546 |
This group contains the algorithms for finding a minimum cost spanning |
|
| 547 |
tree in a graph. |
|
| 551 |
This group contains the algorithms for finding minimum cost spanning |
|
| 552 |
trees and arborescences. |
|
| 548 | 553 |
*/ |
| 549 | 554 |
|
| 550 | 555 |
/** |
| 551 | 556 |
@defgroup auxalg Auxiliary Algorithms |
| 552 | 557 |
@ingroup algs |
| 553 | 558 |
\brief Auxiliary algorithms implemented in LEMON. |
| 554 | 559 |
|
| 555 | 560 |
This group contains some algorithms implemented in LEMON |
| ... | ... |
@@ -36,21 +36,17 @@ |
| 36 | 36 |
project. |
| 37 | 37 |
You are free to use it in your commercial or |
| 38 | 38 |
non-commercial applications under very permissive |
| 39 | 39 |
\ref license "license terms". |
| 40 | 40 |
</b> |
| 41 | 41 |
|
| 42 | 42 |
\subsection howtoread How to read the documentation |
| 43 | 43 |
|
| 44 |
If you want to get a quick start and see the most important features then |
|
| 45 |
take a look at our \ref quicktour |
|
| 46 |
"Quick Tour to LEMON" which will guide you along. |
|
| 47 |
|
|
| 48 |
If you |
|
| 44 |
If you would like to get to know the library, see |
|
| 49 | 45 |
<a class="el" href="http://lemon.cs.elte.hu/pub/tutorial/">LEMON Tutorial</a>. |
| 50 | 46 |
|
| 51 |
If you know what you are looking for then try to find it under the |
|
| 47 |
If you know what you are looking for, then try to find it under the |
|
| 52 | 48 |
<a class="el" href="modules.html">Modules</a> section. |
| 53 | 49 |
|
| 54 | 50 |
If you are a user of the old (0.x) series of LEMON, please check out the |
| 55 | 51 |
\ref migration "Migration Guide" for the backward incompatibilities. |
| 56 | 52 |
*/ |
| ... | ... |
@@ -494,17 +494,17 @@ |
| 494 | 494 |
} |
| 495 | 495 |
return true; |
| 496 | 496 |
} |
| 497 | 497 |
|
| 498 | 498 |
/// \brief Start Edmonds' algorithm |
| 499 | 499 |
/// |
| 500 | 500 |
/// This function runs the original Edmonds' algorithm. |
| 501 | 501 |
/// |
| 502 |
/// \pre \ref |
|
| 502 |
/// \pre \ref init(), \ref greedyInit() or \ref matchingInit() must be |
|
| 503 | 503 |
/// called before using this function. |
| 504 | 504 |
void startSparse() {
|
| 505 | 505 |
for(NodeIt n(_graph); n != INVALID; ++n) {
|
| 506 | 506 |
if ((*_status)[n] == UNMATCHED) {
|
| 507 | 507 |
(*_blossom_rep)[_blossom_set->insert(n)] = n; |
| 508 | 508 |
_tree_set->insert(n); |
| 509 | 509 |
(*_status)[n] = EVEN; |
| 510 | 510 |
processSparse(n); |
| ... | ... |
@@ -513,17 +513,17 @@ |
| 513 | 513 |
} |
| 514 | 514 |
|
| 515 | 515 |
/// \brief Start Edmonds' algorithm with a heuristic improvement |
| 516 | 516 |
/// for dense graphs |
| 517 | 517 |
/// |
| 518 | 518 |
/// This function runs Edmonds' algorithm with a heuristic of postponing |
| 519 | 519 |
/// shrinks, therefore resulting in a faster algorithm for dense graphs. |
| 520 | 520 |
/// |
| 521 |
/// \pre \ref |
|
| 521 |
/// \pre \ref init(), \ref greedyInit() or \ref matchingInit() must be |
|
| 522 | 522 |
/// called before using this function. |
| 523 | 523 |
void startDense() {
|
| 524 | 524 |
for(NodeIt n(_graph); n != INVALID; ++n) {
|
| 525 | 525 |
if ((*_status)[n] == UNMATCHED) {
|
| 526 | 526 |
(*_blossom_rep)[_blossom_set->insert(n)] = n; |
| 527 | 527 |
_tree_set->insert(n); |
| 528 | 528 |
(*_status)[n] = EVEN; |
| 529 | 529 |
processDense(n); |
0 comments (0 inline)