doc/groups.dox
branch1.3
changeset 1280 fbdde70389da
parent 1271 fb1c7da561ce
equal deleted inserted replaced
71:6872630fe256 72:857689171a9e
   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 */