r843:189760a7cdd0
Thu, 07 May 2009 02:05:12
[Not Reviewed]
0 comments (0 inline)
0
2
0
16
104
| ... | ... |
@@ -236,14 +236,6 @@ |
| 236 | 236 |
*/ |
| 237 | 237 |
|
| 238 | 238 |
/** |
| 239 |
@defgroup matrices Matrices |
|
| 240 |
@ingroup datas |
|
| 241 |
\brief Two dimensional data storages implemented in LEMON. |
|
| 242 |
|
|
| 243 |
This group contains two dimensional data storages implemented in LEMON. |
|
| 244 |
*/ |
|
| 245 |
|
|
| 246 |
/** |
|
| 247 | 239 |
@defgroup paths Path Structures |
| 248 | 240 |
@ingroup datas |
| 249 | 241 |
\brief %Path structures implemented in LEMON. |
| ... | ... |
@@ -293,16 +285,8 @@ |
| 293 | 285 |
|
| 294 | 286 |
This group contains the algorithms for finding shortest paths in digraphs. |
| 295 | 287 |
|
| 296 |
- \ref Dijkstra algorithm for finding shortest paths from a source node |
|
| 297 |
when all arc lengths are non-negative. |
|
| 298 |
- \ref BellmanFord "Bellman-Ford" algorithm for finding shortest paths |
|
| 299 |
from a source node when arc lenghts can be either positive or negative, |
|
| 300 |
but the digraph should not contain directed cycles with negative total |
|
| 301 |
length. |
|
| 302 |
- \ref FloydWarshall "Floyd-Warshall" and \ref Johnson "Johnson" algorithms |
|
| 303 |
for solving the \e all-pairs \e shortest \e paths \e problem when arc |
|
| 304 |
lenghts can be either positive or negative, but the digraph should |
|
| 305 |
not contain directed cycles with negative total length. |
|
| 288 |
- \ref Dijkstra Dijkstra's algorithm for finding shortest paths from a |
|
| 289 |
source node when all arc lengths are non-negative. |
|
| 306 | 290 |
- \ref Suurballe A successive shortest path algorithm for finding |
| 307 | 291 |
arc-disjoint paths between two nodes having minimum total length. |
| 308 | 292 |
*/ |
| ... | ... |
@@ -327,16 +311,14 @@ |
| 327 | 311 |
\quad \forall u\in V\setminus\{s,t\} \f]
|
| 328 | 312 |
\f[ 0 \leq f(uv) \leq cap(uv) \quad \forall uv\in A \f] |
| 329 | 313 |
|
| 330 |
LEMON contains several algorithms for solving maximum flow problems: |
|
| 331 |
- \ref EdmondsKarp Edmonds-Karp algorithm. |
|
| 332 |
- \ref Preflow Goldberg-Tarjan's preflow push-relabel algorithm. |
|
| 333 |
- \ref DinitzSleatorTarjan Dinitz's blocking flow algorithm with dynamic trees. |
|
| 334 |
|
|
| 314 |
\ref Preflow implements the preflow push-relabel algorithm of Goldberg and |
|
| 315 |
Tarjan for solving this problem. It also provides functions to query the |
|
| 316 |
minimum cut, which is the dual problem of maximum flow. |
|
| 335 | 317 |
|
| 336 |
In most cases the \ref Preflow "Preflow" algorithm provides the |
|
| 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. |
|
| 318 |
\ref Circulation is a preflow push-relabel algorithm implemented directly |
|
| 319 |
for finding feasible circulations, which is a somewhat different problem, |
|
| 320 |
but it is strongly related to maximum flow. |
|
| 321 |
For more information, see \ref Circulation. |
|
| 340 | 322 |
*/ |
| 341 | 323 |
|
| 342 | 324 |
/** |
| ... | ... |
@@ -421,27 +403,9 @@ |
| 421 | 403 |
\f$uv\in A\f$ with respect to the potential function \f$\pi\f$, i.e. |
| 422 | 404 |
\f[ cost^\pi(uv) = cost(uv) + \pi(u) - \pi(v).\f] |
| 423 | 405 |
|
| 424 |
All algorithms provide dual solution (node potentials) as well, |
|
| 425 |
if an optimal flow is found. |
|
| 426 |
|
|
| 427 |
LEMON contains several algorithms for solving minimum cost flow problems. |
|
| 428 |
- \ref NetworkSimplex Primal Network Simplex algorithm with various |
|
| 429 |
pivot strategies. |
|
| 430 |
- \ref CostScaling Push-Relabel and Augment-Relabel algorithms based on |
|
| 431 |
cost scaling. |
|
| 432 |
- \ref CapacityScaling Successive Shortest %Path algorithm with optional |
|
| 433 |
capacity scaling. |
|
| 434 |
- \ref CancelAndTighten The Cancel and Tighten algorithm. |
|
| 435 |
- \ref CycleCanceling Cycle-Canceling algorithms. |
|
| 436 |
|
|
| 437 |
Most of these implementations support the general inequality form of the |
|
| 438 |
minimum cost flow problem, but CancelAndTighten and CycleCanceling |
|
| 439 |
only support the equality form due to the primal method they use. |
|
| 440 |
|
|
| 441 |
In general NetworkSimplex is the most efficient implementation, |
|
| 442 |
but in special cases other algorithms could be faster. |
|
| 443 |
For example, if the total supply and/or capacities are rather small, |
|
| 444 |
|
|
| 406 |
\ref NetworkSimplex is an efficient implementation of the primal Network |
|
| 407 |
Simplex algorithm for finding minimum cost flows. It also provides dual |
|
| 408 |
solution (node potentials), if an optimal flow is found. |
|
| 445 | 409 |
*/ |
| 446 | 410 |
|
| 447 | 411 |
/** |
| ... | ... |
@@ -465,8 +429,6 @@ |
| 465 | 429 |
|
| 466 | 430 |
- \ref HaoOrlin "Hao-Orlin algorithm" for calculating minimum cut |
| 467 | 431 |
in directed graphs. |
| 468 |
- \ref NagamochiIbaraki "Nagamochi-Ibaraki algorithm" for |
|
| 469 |
calculating minimum cut in undirected graphs. |
|
| 470 | 432 |
- \ref GomoryHu "Gomory-Hu tree computation" for calculating |
| 471 | 433 |
all-pairs minimum cut in undirected graphs. |
| 472 | 434 |
|
| ... | ... |
@@ -487,45 +449,21 @@ |
| 487 | 449 |
*/ |
| 488 | 450 |
|
| 489 | 451 |
/** |
| 490 |
@defgroup planar Planarity Embedding and Drawing |
|
| 491 |
@ingroup algs |
|
| 492 |
\brief Algorithms for planarity checking, embedding and drawing |
|
| 493 |
|
|
| 494 |
This group contains the algorithms for planarity checking, |
|
| 495 |
embedding and drawing. |
|
| 496 |
|
|
| 497 |
\image html planar.png |
|
| 498 |
\image latex planar.eps "Plane graph" width=\textwidth |
|
| 499 |
*/ |
|
| 500 |
|
|
| 501 |
/** |
|
| 502 | 452 |
@defgroup matching Matching Algorithms |
| 503 | 453 |
@ingroup algs |
| 504 | 454 |
\brief Algorithms for finding matchings in graphs and bipartite graphs. |
| 505 | 455 |
|
| 506 |
This group contains the algorithms for calculating |
|
| 507 |
matchings in graphs and bipartite graphs. The general matching problem is |
|
| 508 |
finding a subset of the edges for which each node has at most one incident |
|
| 509 |
edge. |
|
| 456 |
This group contains the algorithms for calculating matchings in graphs. |
|
| 457 |
The general matching problem is finding a subset of the edges for which |
|
| 458 |
each node has at most one incident edge. |
|
| 510 | 459 |
|
| 511 | 460 |
There are several different algorithms for calculate matchings in |
| 512 |
graphs. The matching problems in bipartite graphs are generally |
|
| 513 |
easier than in general graphs. The goal of the matching optimization |
|
| 461 |
graphs. The goal of the matching optimization |
|
| 514 | 462 |
can be finding maximum cardinality, maximum weight or minimum cost |
| 515 | 463 |
matching. The search can be constrained to find perfect or |
| 516 | 464 |
maximum cardinality matching. |
| 517 | 465 |
|
| 518 | 466 |
The matching algorithms implemented in LEMON: |
| 519 |
- \ref MaxBipartiteMatching Hopcroft-Karp augmenting path algorithm |
|
| 520 |
for calculating maximum cardinality matching in bipartite graphs. |
|
| 521 |
- \ref PrBipartiteMatching Push-relabel algorithm |
|
| 522 |
for calculating maximum cardinality matching in bipartite graphs. |
|
| 523 |
- \ref MaxWeightedBipartiteMatching |
|
| 524 |
Successive shortest path algorithm for calculating maximum weighted |
|
| 525 |
matching and maximum weighted bipartite matching in bipartite graphs. |
|
| 526 |
- \ref MinCostMaxBipartiteMatching |
|
| 527 |
Successive shortest path algorithm for calculating minimum cost maximum |
|
| 528 |
matching in bipartite graphs. |
|
| 529 | 467 |
- \ref MaxMatching Edmond's blossom shrinking algorithm for calculating |
| 530 | 468 |
maximum cardinality matching in general graphs. |
| 531 | 469 |
- \ref MaxWeightedMatching Edmond's blossom shrinking algorithm for calculating |
| ... | ... |
@@ -557,15 +495,6 @@ |
| 557 | 495 |
*/ |
| 558 | 496 |
|
| 559 | 497 |
/** |
| 560 |
@defgroup approx Approximation Algorithms |
|
| 561 |
@ingroup algs |
|
| 562 |
\brief Approximation algorithms. |
|
| 563 |
|
|
| 564 |
This group contains the approximation and heuristic algorithms |
|
| 565 |
implemented in LEMON. |
|
| 566 |
*/ |
|
| 567 |
|
|
| 568 |
/** |
|
| 569 | 498 |
@defgroup gen_opt_group General Optimization Tools |
| 570 | 499 |
\brief This group contains some general optimization frameworks |
| 571 | 500 |
implemented in LEMON. |
| ... | ... |
@@ -585,23 +514,6 @@ |
| 585 | 514 |
*/ |
| 586 | 515 |
|
| 587 | 516 |
/** |
| 588 |
@defgroup lp_utils Tools for Lp and Mip Solvers |
|
| 589 |
@ingroup lp_group |
|
| 590 |
\brief Helper tools to the Lp and Mip solvers. |
|
| 591 |
|
|
| 592 |
This group adds some helper tools to general optimization framework |
|
| 593 |
implemented in LEMON. |
|
| 594 |
*/ |
|
| 595 |
|
|
| 596 |
/** |
|
| 597 |
@defgroup metah Metaheuristics |
|
| 598 |
@ingroup gen_opt_group |
|
| 599 |
\brief Metaheuristics for LEMON library. |
|
| 600 |
|
|
| 601 |
This group contains some metaheuristic optimization tools. |
|
| 602 |
*/ |
|
| 603 |
|
|
| 604 |
/** |
|
| 605 | 517 |
@defgroup utils Tools and Utilities |
| 606 | 518 |
\brief Tools and utilities for programming in LEMON |
| 607 | 519 |
| ... | ... |
@@ -45,8 +45,8 @@ |
| 45 | 45 |
/// |
| 46 | 46 |
/// Note that this problem is a special case of the \ref min_cost_flow |
| 47 | 47 |
/// "minimum cost flow problem". This implementation is actually an |
| 48 |
/// efficient specialized version of the \ref CapacityScaling |
|
| 49 |
/// "Successive Shortest Path" algorithm directly for this problem. |
|
| 48 |
/// efficient specialized version of the Successive Shortest Path |
|
| 49 |
/// algorithm directly for this problem. |
|
| 50 | 50 |
/// Therefore this class provides query functions for flow values and |
| 51 | 51 |
/// node potentials (the dual solution) just like the minimum cost flow |
| 52 | 52 |
/// algorithms. |
0 comments (0 inline)