diff -r 6f10c6ec5a21 -r ceb2756dea2a doc/groups.dox --- a/doc/groups.dox Mon Sep 28 15:53:20 2009 +0200 +++ b/doc/groups.dox Thu Nov 05 10:27:17 2009 +0100 @@ -316,7 +316,8 @@ \brief Common graph search algorithms. This group contains the common graph search algorithms, namely -\e breadth-first \e search (BFS) and \e depth-first \e search (DFS). +\e breadth-first \e search (BFS) and \e depth-first \e search (DFS) +\ref clrs01algorithms. */ /** @@ -324,7 +325,8 @@ @ingroup algs \brief Algorithms for finding shortest paths. -This group contains the algorithms for finding shortest paths in digraphs. +This group contains the algorithms for finding shortest paths in digraphs +\ref clrs01algorithms. - \ref Dijkstra algorithm for finding shortest paths from a source node when all arc lengths are non-negative. @@ -346,7 +348,7 @@ \brief Algorithms for finding minimum cost spanning trees and arborescences. This group contains the algorithms for finding minimum cost spanning -trees and arborescences. +trees and arborescences \ref clrs01algorithms. */ /** @@ -355,7 +357,7 @@ \brief Algorithms for finding maximum flows. This group contains the algorithms for finding maximum flows and -feasible circulations. +feasible circulations \ref clrs01algorithms, \ref amo93networkflows. The \e maximum \e flow \e problem is to find a flow of maximum value between a single source and a single target. Formally, there is a \f$G=(V,A)\f$ @@ -370,12 +372,16 @@ \f[ 0 \leq f(uv) \leq cap(uv) \quad \forall uv\in A \f] LEMON contains several algorithms for solving maximum flow problems: -- \ref EdmondsKarp Edmonds-Karp algorithm. -- \ref Preflow Goldberg-Tarjan's preflow push-relabel algorithm. -- \ref DinitzSleatorTarjan Dinitz's blocking flow algorithm with dynamic trees. -- \ref GoldbergTarjan Preflow push-relabel algorithm with dynamic trees. +- \ref EdmondsKarp Edmonds-Karp algorithm + \ref edmondskarp72theoretical. +- \ref Preflow Goldberg-Tarjan's preflow push-relabel algorithm + \ref goldberg88newapproach. +- \ref DinitzSleatorTarjan Dinitz's blocking flow algorithm with dynamic trees + \ref dinic70algorithm, \ref sleator83dynamic. +- \ref GoldbergTarjan !Preflow push-relabel algorithm with dynamic trees + \ref goldberg88newapproach, \ref sleator83dynamic. -In most cases the \ref Preflow "Preflow" algorithm provides the +In most cases the \ref Preflow algorithm provides the fastest method for computing a maximum flow. All implementations also provide functions to query the minimum cut, which is the dual problem of maximum flow. @@ -393,18 +399,22 @@ \brief Algorithms for finding minimum cost flows and circulations. This group contains the algorithms for finding minimum cost flows and -circulations. For more information about this problem and its dual -solution see \ref min_cost_flow "Minimum Cost Flow Problem". +circulations \ref amo93networkflows. For more information about this +problem and its dual solution, see \ref min_cost_flow +"Minimum Cost Flow Problem". LEMON contains several algorithms for this problem. - \ref NetworkSimplex Primal Network Simplex algorithm with various - pivot strategies. + pivot strategies \ref dantzig63linearprog, \ref kellyoneill91netsimplex. - \ref CostScaling Push-Relabel and Augment-Relabel algorithms based on - cost scaling. + cost scaling \ref goldberg90approximation, \ref goldberg97efficient, + \ref bunnagel98efficient. - \ref CapacityScaling Successive Shortest %Path algorithm with optional - capacity scaling. - - \ref CancelAndTighten The Cancel and Tighten algorithm. - - \ref CycleCanceling Cycle-Canceling algorithms. + capacity scaling \ref edmondskarp72theoretical. + - \ref CancelAndTighten The Cancel and Tighten algorithm + \ref goldberg89cyclecanceling. + - \ref CycleCanceling Cycle-Canceling algorithms + \ref klein67primal, \ref goldberg89cyclecanceling. In general NetworkSimplex is the most efficient implementation, but in special cases other algorithms could be faster. @@ -443,6 +453,43 @@ */ /** +@defgroup min_mean_cycle Minimum Mean Cycle Algorithms +@ingroup algs +\brief Algorithms for finding minimum mean cycles. + +This group contains the algorithms for finding minimum mean cycles +\ref clrs01algorithms, \ref amo93networkflows. + +The \e minimum \e mean \e cycle \e problem is to find a directed cycle +of minimum mean length (cost) in a digraph. +The mean length of a cycle is the average length of its arcs, i.e. the +ratio between the total length of the cycle and the number of arcs on it. + +This problem has an important connection to \e conservative \e length +\e functions, too. A length function on the arcs of a digraph is called +conservative if and only if there is no directed cycle of negative total +length. For an arbitrary length function, the negative of the minimum +cycle mean is the smallest \f$\epsilon\f$ value so that increasing the +arc lengths uniformly by \f$\epsilon\f$ results in a conservative length +function. + +LEMON contains three algorithms for solving the minimum mean cycle problem: +- \ref Karp "Karp"'s original algorithm \ref amo93networkflows, + \ref dasdan98minmeancycle. +- \ref HartmannOrlin "Hartmann-Orlin"'s algorithm, which is an improved + version of Karp's algorithm \ref dasdan98minmeancycle. +- \ref Howard "Howard"'s policy iteration algorithm + \ref dasdan98minmeancycle. + +In practice, the Howard algorithm proved to be by far the most efficient +one, though the best known theoretical bound on its running time is +exponential. +Both Karp and HartmannOrlin algorithms run in time O(ne) and use space +O(n2+e), but the latter one is typically faster due to the +applied early termination scheme. +*/ + +/** @defgroup matching Matching Algorithms @ingroup algs \brief Algorithms for finding matchings in graphs and bipartite graphs. @@ -534,13 +581,16 @@ */ /** -@defgroup lp_group Lp and Mip Solvers +@defgroup lp_group LP and MIP Solvers @ingroup gen_opt_group -\brief Lp and Mip solver interfaces for LEMON. +\brief LP and MIP solver interfaces for LEMON. -This group contains Lp and Mip solver interfaces for LEMON. The -various LP solvers could be used in the same manner with this -interface. +This group contains LP and MIP solver interfaces for LEMON. +Various LP solvers could be used in the same manner with this +high-level interface. + +The currently supported solvers are \ref glpk, \ref clp, \ref cbc, +\ref cplex, \ref soplex. */ /** @@ -679,8 +729,8 @@ @ingroup concept \brief Skeleton and concept checking classes for graph structures -This group contains the skeletons and concept checking classes of LEMON's -graph structures and helper classes used to implement these. +This group contains the skeletons and concept checking classes of +graph structures. */ /**