r969:7af2ae7c1428
Thu, 18 Mar 2010 00:29:35
[Not Reviewed]
0 comments (0 inline)
0
1
0
4
64
| ... | ... |
@@ -294,14 +294,6 @@ |
| 294 | 294 |
*/ |
| 295 | 295 |
|
| 296 | 296 |
/** |
| 297 |
@defgroup matrices Matrices |
|
| 298 |
@ingroup auxdat |
|
| 299 |
\brief Two dimensional data storages implemented in LEMON. |
|
| 300 |
|
|
| 301 |
This group contains two dimensional data storages implemented in LEMON. |
|
| 302 |
*/ |
|
| 303 |
|
|
| 304 |
/** |
|
| 305 | 297 |
@defgroup algs Algorithms |
| 306 | 298 |
\brief This group contains the several algorithms |
| 307 | 299 |
implemented in LEMON. |
| ... | ... |
@@ -334,10 +326,6 @@ |
| 334 | 326 |
from a source node when arc lenghts can be either positive or negative, |
| 335 | 327 |
but the digraph should not contain directed cycles with negative total |
| 336 | 328 |
length. |
| 337 |
- \ref FloydWarshall "Floyd-Warshall" and \ref Johnson "Johnson" algorithms |
|
| 338 |
for solving the \e all-pairs \e shortest \e paths \e problem when arc |
|
| 339 |
lenghts can be either positive or negative, but the digraph should |
|
| 340 |
not contain directed cycles with negative total length. |
|
| 341 | 329 |
- \ref Suurballe A successive shortest path algorithm for finding |
| 342 | 330 |
arc-disjoint paths between two nodes having minimum total length. |
| 343 | 331 |
*/ |
| ... | ... |
@@ -371,20 +359,10 @@ |
| 371 | 359 |
\quad \forall u\in V\setminus\{s,t\} \f]
|
| 372 | 360 |
\f[ 0 \leq f(uv) \leq cap(uv) \quad \forall uv\in A \f] |
| 373 | 361 |
|
| 374 |
LEMON contains several algorithms for solving maximum flow problems: |
|
| 375 |
- \ref EdmondsKarp Edmonds-Karp algorithm |
|
| 376 |
\ref edmondskarp72theoretical. |
|
| 377 |
- \ref Preflow Goldberg-Tarjan's preflow push-relabel algorithm |
|
| 378 |
\ref goldberg88newapproach. |
|
| 379 |
- \ref DinitzSleatorTarjan Dinitz's blocking flow algorithm with dynamic trees |
|
| 380 |
\ref dinic70algorithm, \ref sleator83dynamic. |
|
| 381 |
- \ref GoldbergTarjan !Preflow push-relabel algorithm with dynamic trees |
|
| 382 |
\ref goldberg88newapproach, \ref sleator83dynamic. |
|
| 383 |
|
|
| 384 |
In most cases the \ref Preflow algorithm provides the |
|
| 385 |
fastest method for computing a maximum flow. All implementations |
|
| 386 |
also provide functions to query the minimum cut, which is the dual |
|
| 387 |
problem of maximum flow. |
|
| 362 |
\ref Preflow is an efficient implementation of Goldberg-Tarjan's |
|
| 363 |
preflow push-relabel algorithm \ref goldberg88newapproach for finding |
|
| 364 |
maximum flows. It also provides functions to query the minimum cut, |
|
| 365 |
which is the dual problem of maximum flow. |
|
| 388 | 366 |
|
| 389 | 367 |
\ref Circulation is a preflow push-relabel algorithm implemented directly |
| 390 | 368 |
for finding feasible circulations, which is a somewhat different problem, |
| ... | ... |
@@ -441,8 +419,6 @@ |
| 441 | 419 |
|
| 442 | 420 |
- \ref HaoOrlin "Hao-Orlin algorithm" for calculating minimum cut |
| 443 | 421 |
in directed graphs. |
| 444 |
- \ref NagamochiIbaraki "Nagamochi-Ibaraki algorithm" for |
|
| 445 |
calculating minimum cut in undirected graphs. |
|
| 446 | 422 |
- \ref GomoryHu "Gomory-Hu tree computation" for calculating |
| 447 | 423 |
all-pairs minimum cut in undirected graphs. |
| 448 | 424 |
|
| ... | ... |
@@ -505,16 +481,6 @@ |
| 505 | 481 |
maximum cardinality matching. |
| 506 | 482 |
|
| 507 | 483 |
The matching algorithms implemented in LEMON: |
| 508 |
- \ref MaxBipartiteMatching Hopcroft-Karp augmenting path algorithm |
|
| 509 |
for calculating maximum cardinality matching in bipartite graphs. |
|
| 510 |
- \ref PrBipartiteMatching Push-relabel algorithm |
|
| 511 |
for calculating maximum cardinality matching in bipartite graphs. |
|
| 512 |
- \ref MaxWeightedBipartiteMatching |
|
| 513 |
Successive shortest path algorithm for calculating maximum weighted |
|
| 514 |
matching and maximum weighted bipartite matching in bipartite graphs. |
|
| 515 |
- \ref MinCostMaxBipartiteMatching |
|
| 516 |
Successive shortest path algorithm for calculating minimum cost maximum |
|
| 517 |
matching in bipartite graphs. |
|
| 518 | 484 |
- \ref MaxMatching Edmond's blossom shrinking algorithm for calculating |
| 519 | 485 |
maximum cardinality matching in general graphs. |
| 520 | 486 |
- \ref MaxWeightedMatching Edmond's blossom shrinking algorithm for calculating |
| ... | ... |
@@ -559,15 +525,6 @@ |
| 559 | 525 |
*/ |
| 560 | 526 |
|
| 561 | 527 |
/** |
| 562 |
@defgroup approx Approximation Algorithms |
|
| 563 |
@ingroup algs |
|
| 564 |
\brief Approximation algorithms. |
|
| 565 |
|
|
| 566 |
This group contains the approximation and heuristic algorithms |
|
| 567 |
implemented in LEMON. |
|
| 568 |
*/ |
|
| 569 |
|
|
| 570 |
/** |
|
| 571 | 528 |
@defgroup auxalg Auxiliary Algorithms |
| 572 | 529 |
@ingroup algs |
| 573 | 530 |
\brief Auxiliary algorithms implemented in LEMON. |
| ... | ... |
@@ -599,23 +556,6 @@ |
| 599 | 556 |
*/ |
| 600 | 557 |
|
| 601 | 558 |
/** |
| 602 |
@defgroup lp_utils Tools for Lp and Mip Solvers |
|
| 603 |
@ingroup lp_group |
|
| 604 |
\brief Helper tools to the Lp and Mip solvers. |
|
| 605 |
|
|
| 606 |
This group adds some helper tools to general optimization framework |
|
| 607 |
implemented in LEMON. |
|
| 608 |
*/ |
|
| 609 |
|
|
| 610 |
/** |
|
| 611 |
@defgroup metah Metaheuristics |
|
| 612 |
@ingroup gen_opt_group |
|
| 613 |
\brief Metaheuristics for LEMON library. |
|
| 614 |
|
|
| 615 |
This group contains some metaheuristic optimization tools. |
|
| 616 |
*/ |
|
| 617 |
|
|
| 618 |
/** |
|
| 619 | 559 |
@defgroup utils Tools and Utilities |
| 620 | 560 |
\brief Tools and utilities for programming in LEMON |
| 621 | 561 |
|
0 comments (0 inline)