r969:7af2ae7c1428
Thu, 18 Mar 2010 00:29:35
[Not Reviewed]
0 comments (0 inline)
0
1
0
4
64
| ... | ... |
@@ -291,20 +291,12 @@ |
| 291 | 291 |
- \ref lemon::dim2::Box "dim2::Box" can be used to determine the |
| 292 | 292 |
rectangular bounding box of a set of \ref lemon::dim2::Point |
| 293 | 293 |
"dim2::Point"'s. |
| 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. |
| 308 | 300 |
|
| 309 | 301 |
This group contains the several algorithms |
| 310 | 302 |
implemented in LEMON. |
| ... | ... |
@@ -331,16 +323,12 @@ |
| 331 | 323 |
- \ref Dijkstra algorithm for finding shortest paths from a source node |
| 332 | 324 |
when all arc lengths are non-negative. |
| 333 | 325 |
- \ref BellmanFord "Bellman-Ford" algorithm for finding shortest paths |
| 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 |
*/ |
| 344 | 332 |
|
| 345 | 333 |
/** |
| 346 | 334 |
@defgroup spantree Minimum Spanning Tree Algorithms |
| ... | ... |
@@ -368,26 +356,16 @@ |
| 368 | 356 |
|
| 369 | 357 |
\f[ \max\sum_{sv\in A} f(sv) - \sum_{vs\in A} f(vs) \f]
|
| 370 | 358 |
\f[ \sum_{uv\in A} f(uv) = \sum_{vu\in A} f(vu)
|
| 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, |
| 391 | 369 |
but it is strongly related to maximum flow. |
| 392 | 370 |
For more information, see \ref Circulation. |
| 393 | 371 |
*/ |
| ... | ... |
@@ -438,14 +416,12 @@ |
| 438 | 416 |
\sum_{uv\in A: u\in X, v\not\in X}cap(uv) \f]
|
| 439 | 417 |
|
| 440 | 418 |
LEMON contains several algorithms related to minimum cut problems: |
| 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 |
|
| 449 | 425 |
If you want to find minimum cut just between two distinict nodes, |
| 450 | 426 |
see the \ref max_flow "maximum flow problem". |
| 451 | 427 |
*/ |
| ... | ... |
@@ -502,22 +478,12 @@ |
| 502 | 478 |
easier than in general graphs. The goal of the matching optimization |
| 503 | 479 |
can be finding maximum cardinality, maximum weight or minimum cost |
| 504 | 480 |
matching. The search can be constrained to find perfect or |
| 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 |
| 521 | 487 |
maximum weighted matching in general graphs. |
| 522 | 488 |
- \ref MaxWeightedPerfectMatching |
| 523 | 489 |
Edmond's blossom shrinking algorithm for calculating maximum weighted |
| ... | ... |
@@ -556,21 +522,12 @@ |
| 556 | 522 |
|
| 557 | 523 |
\image html planar.png |
| 558 | 524 |
\image latex planar.eps "Plane graph" width=\textwidth |
| 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. |
| 574 | 531 |
|
| 575 | 532 |
This group contains some algorithms implemented in LEMON |
| 576 | 533 |
in order to make it easier to implement complex algorithms. |
| ... | ... |
@@ -596,29 +553,12 @@ |
| 596 | 553 |
|
| 597 | 554 |
The currently supported solvers are \ref glpk, \ref clp, \ref cbc, |
| 598 | 555 |
\ref cplex, \ref soplex. |
| 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 |
|
| 622 | 562 |
Tools and utilities for programming in LEMON. |
| 623 | 563 |
*/ |
| 624 | 564 |
|
0 comments (0 inline)