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 \ref goldberg88newapproach for finding |
376 \ref 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 \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. |
|
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. |
439 |
417 |
440 LEMON contains several algorithms related to minimum cut problems: |
418 LEMON contains several algorithms related to minimum cut problems: |
441 |
419 |
442 - \ref HaoOrlin "Hao-Orlin algorithm" for calculating minimum cut |
420 - \ref HaoOrlin "Hao-Orlin algorithm" for calculating minimum cut |
443 in directed graphs. |
421 in directed graphs. |
444 - \ref NagamochiIbaraki "Nagamochi-Ibaraki algorithm" for |
|
445 calculating minimum cut in undirected graphs. |
|
446 - \ref GomoryHu "Gomory-Hu tree computation" for calculating |
422 - \ref GomoryHu "Gomory-Hu tree computation" for calculating |
447 all-pairs minimum cut in undirected graphs. |
423 all-pairs minimum cut in undirected graphs. |
448 |
424 |
449 If you want to find minimum cut just between two distinict nodes, |
425 If you want to find minimum cut just between two distinict nodes, |
450 see the \ref max_flow "maximum flow problem". |
426 see the \ref max_flow "maximum flow problem". |
503 can be finding maximum cardinality, maximum weight or minimum cost |
479 can be finding maximum cardinality, maximum weight or minimum cost |
504 matching. The search can be constrained to find perfect or |
480 matching. The search can be constrained to find perfect or |
505 maximum cardinality matching. |
481 maximum cardinality matching. |
506 |
482 |
507 The matching algorithms implemented in LEMON: |
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 - \ref MaxMatching Edmond's blossom shrinking algorithm for calculating |
484 - \ref MaxMatching Edmond's blossom shrinking algorithm for calculating |
519 maximum cardinality matching in general graphs. |
485 maximum cardinality matching in general graphs. |
520 - \ref MaxWeightedMatching Edmond's blossom shrinking algorithm for calculating |
486 - \ref MaxWeightedMatching Edmond's blossom shrinking algorithm for calculating |
521 maximum weighted matching in general graphs. |
487 maximum weighted matching in general graphs. |
522 - \ref MaxWeightedPerfectMatching |
488 - \ref MaxWeightedPerfectMatching |
557 \image html planar.png |
523 \image html planar.png |
558 \image latex planar.eps "Plane graph" width=\textwidth |
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 @defgroup auxalg Auxiliary Algorithms |
528 @defgroup auxalg Auxiliary Algorithms |
572 @ingroup algs |
529 @ingroup algs |
573 \brief Auxiliary algorithms implemented in LEMON. |
530 \brief Auxiliary algorithms implemented in LEMON. |
574 |
531 |
575 This group contains some algorithms implemented in LEMON |
532 This group contains some algorithms implemented in LEMON |
594 Various LP solvers could be used in the same manner with this |
551 Various LP solvers could be used in the same manner with this |
595 high-level interface. |
552 high-level interface. |
596 |
553 |
597 The currently supported solvers are \ref glpk, \ref clp, \ref cbc, |
554 The currently supported solvers are \ref glpk, \ref clp, \ref cbc, |
598 \ref cplex, \ref soplex. |
555 \ref cplex, \ref soplex. |
599 */ |
|
600 |
|
601 /** |
|
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 */ |
556 */ |
617 |
557 |
618 /** |
558 /** |
619 @defgroup utils Tools and Utilities |
559 @defgroup utils Tools and Utilities |
620 \brief Tools and utilities for programming in LEMON |
560 \brief Tools and utilities for programming in LEMON |