292 rectangular bounding box of a set of \ref lemon::dim2::Point |
292 rectangular bounding box of a set of \ref lemon::dim2::Point |
293 "dim2::Point"'s. |
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 @defgroup algs Algorithms |
297 @defgroup algs Algorithms |
306 \brief This group contains the several algorithms |
298 \brief This group contains the several algorithms |
307 implemented in LEMON. |
299 implemented in LEMON. |
308 |
300 |
309 This group contains the several algorithms |
301 This group contains the several algorithms |
332 when all arc lengths are non-negative. |
324 when all arc lengths are non-negative. |
333 - \ref BellmanFord "Bellman-Ford" algorithm for finding shortest paths |
325 - \ref BellmanFord "Bellman-Ford" algorithm for finding shortest paths |
334 from a source node when arc lenghts can be either positive or negative, |
326 from a source node when arc lenghts can be either positive or negative, |
335 but the digraph should not contain directed cycles with negative total |
327 but the digraph should not contain directed cycles with negative total |
336 length. |
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 - \ref Suurballe A successive shortest path algorithm for finding |
329 - \ref Suurballe A successive shortest path algorithm for finding |
342 arc-disjoint paths between two nodes having minimum total length. |
330 arc-disjoint paths between two nodes having minimum total length. |
343 */ |
331 */ |
344 |
332 |
345 /** |
333 /** |
369 \f[ \max\sum_{sv\in A} f(sv) - \sum_{vs\in A} f(vs) \f] |
357 \f[ \max\sum_{sv\in A} f(sv) - \sum_{vs\in A} f(vs) \f] |
370 \f[ \sum_{uv\in A} f(uv) = \sum_{vu\in A} f(vu) |
358 \f[ \sum_{uv\in A} f(uv) = \sum_{vu\in A} f(vu) |
371 \quad \forall u\in V\setminus\{s,t\} \f] |
359 \quad \forall u\in V\setminus\{s,t\} \f] |
372 \f[ 0 \leq f(uv) \leq cap(uv) \quad \forall uv\in A \f] |
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: |
362 \ref Preflow is an efficient implementation of Goldberg-Tarjan's |
375 - \ref EdmondsKarp Edmonds-Karp algorithm |
363 preflow push-relabel algorithm \cite goldberg88newapproach for finding |
376 \cite edmondskarp72theoretical. |
364 maximum flows. It also provides functions to query the minimum cut, |
377 - \ref Preflow Goldberg-Tarjan's preflow push-relabel algorithm |
365 which is the dual problem of maximum flow. |
378 \cite goldberg88newapproach. |
|
379 - \ref DinitzSleatorTarjan Dinitz's blocking flow algorithm with dynamic trees |
|
380 \cite dinic70algorithm, \cite sleator83dynamic. |
|
381 - \ref GoldbergTarjan !Preflow push-relabel algorithm with dynamic trees |
|
382 \cite goldberg88newapproach, \cite 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. |
|
388 |
366 |
389 \ref Circulation is a preflow push-relabel algorithm implemented directly |
367 \ref Circulation is a preflow push-relabel algorithm implemented directly |
390 for finding feasible circulations, which is a somewhat different problem, |
368 for finding feasible circulations, which is a somewhat different problem, |
391 but it is strongly related to maximum flow. |
369 but it is strongly related to maximum flow. |
392 For more information, see \ref Circulation. |
370 For more information, see \ref Circulation. |
517 can be finding maximum cardinality, maximum weight or minimum cost |
495 can be finding maximum cardinality, maximum weight or minimum cost |
518 matching. The search can be constrained to find perfect or |
496 matching. The search can be constrained to find perfect or |
519 maximum cardinality matching. |
497 maximum cardinality matching. |
520 |
498 |
521 The matching algorithms implemented in LEMON: |
499 The matching algorithms implemented in LEMON: |
522 - \ref MaxBipartiteMatching Hopcroft-Karp augmenting path algorithm |
|
523 for calculating maximum cardinality matching in bipartite graphs. |
|
524 - \ref PrBipartiteMatching Push-relabel algorithm |
|
525 for calculating maximum cardinality matching in bipartite graphs. |
|
526 - \ref MaxWeightedBipartiteMatching |
|
527 Successive shortest path algorithm for calculating maximum weighted |
|
528 matching and maximum weighted bipartite matching in bipartite graphs. |
|
529 - \ref MinCostMaxBipartiteMatching |
|
530 Successive shortest path algorithm for calculating minimum cost maximum |
|
531 matching in bipartite graphs. |
|
532 - \ref MaxMatching Edmond's blossom shrinking algorithm for calculating |
500 - \ref MaxMatching Edmond's blossom shrinking algorithm for calculating |
533 maximum cardinality matching in general graphs. |
501 maximum cardinality matching in general graphs. |
534 - \ref MaxWeightedMatching Edmond's blossom shrinking algorithm for calculating |
502 - \ref MaxWeightedMatching Edmond's blossom shrinking algorithm for calculating |
535 maximum weighted matching in general graphs. |
503 maximum weighted matching in general graphs. |
536 - \ref MaxWeightedPerfectMatching |
504 - \ref MaxWeightedPerfectMatching |
651 The currently supported solvers are \cite glpk, \cite clp, \cite cbc, |
619 The currently supported solvers are \cite glpk, \cite clp, \cite cbc, |
652 \cite cplex, \cite soplex. |
620 \cite cplex, \cite soplex. |
653 */ |
621 */ |
654 |
622 |
655 /** |
623 /** |
656 @defgroup lp_utils Tools for Lp and Mip Solvers |
|
657 @ingroup lp_group |
|
658 \brief Helper tools to the Lp and Mip solvers. |
|
659 |
|
660 This group adds some helper tools to general optimization framework |
|
661 implemented in LEMON. |
|
662 */ |
|
663 |
|
664 /** |
|
665 @defgroup metah Metaheuristics |
|
666 @ingroup gen_opt_group |
|
667 \brief Metaheuristics for LEMON library. |
|
668 |
|
669 This group contains some metaheuristic optimization tools. |
|
670 */ |
|
671 |
|
672 /** |
|
673 @defgroup utils Tools and Utilities |
624 @defgroup utils Tools and Utilities |
674 \brief Tools and utilities for programming in LEMON |
625 \brief Tools and utilities for programming in LEMON |
675 |
626 |
676 Tools and utilities for programming in LEMON. |
627 Tools and utilities for programming in LEMON. |
677 */ |
628 */ |