1.1 --- a/doc/groups.dox Mon Sep 28 15:53:20 2009 +0200
1.2 +++ b/doc/groups.dox Thu Nov 05 10:27:17 2009 +0100
1.3 @@ -316,7 +316,8 @@
1.4 \brief Common graph search algorithms.
1.5
1.6 This group contains the common graph search algorithms, namely
1.7 -\e breadth-first \e search (BFS) and \e depth-first \e search (DFS).
1.8 +\e breadth-first \e search (BFS) and \e depth-first \e search (DFS)
1.9 +\ref clrs01algorithms.
1.10 */
1.11
1.12 /**
1.13 @@ -324,7 +325,8 @@
1.14 @ingroup algs
1.15 \brief Algorithms for finding shortest paths.
1.16
1.17 -This group contains the algorithms for finding shortest paths in digraphs.
1.18 +This group contains the algorithms for finding shortest paths in digraphs
1.19 +\ref clrs01algorithms.
1.20
1.21 - \ref Dijkstra algorithm for finding shortest paths from a source node
1.22 when all arc lengths are non-negative.
1.23 @@ -346,7 +348,7 @@
1.24 \brief Algorithms for finding minimum cost spanning trees and arborescences.
1.25
1.26 This group contains the algorithms for finding minimum cost spanning
1.27 -trees and arborescences.
1.28 +trees and arborescences \ref clrs01algorithms.
1.29 */
1.30
1.31 /**
1.32 @@ -355,7 +357,7 @@
1.33 \brief Algorithms for finding maximum flows.
1.34
1.35 This group contains the algorithms for finding maximum flows and
1.36 -feasible circulations.
1.37 +feasible circulations \ref clrs01algorithms, \ref amo93networkflows.
1.38
1.39 The \e maximum \e flow \e problem is to find a flow of maximum value between
1.40 a single source and a single target. Formally, there is a \f$G=(V,A)\f$
1.41 @@ -370,12 +372,16 @@
1.42 \f[ 0 \leq f(uv) \leq cap(uv) \quad \forall uv\in A \f]
1.43
1.44 LEMON contains several algorithms for solving maximum flow problems:
1.45 -- \ref EdmondsKarp Edmonds-Karp algorithm.
1.46 -- \ref Preflow Goldberg-Tarjan's preflow push-relabel algorithm.
1.47 -- \ref DinitzSleatorTarjan Dinitz's blocking flow algorithm with dynamic trees.
1.48 -- \ref GoldbergTarjan Preflow push-relabel algorithm with dynamic trees.
1.49 +- \ref EdmondsKarp Edmonds-Karp algorithm
1.50 + \ref edmondskarp72theoretical.
1.51 +- \ref Preflow Goldberg-Tarjan's preflow push-relabel algorithm
1.52 + \ref goldberg88newapproach.
1.53 +- \ref DinitzSleatorTarjan Dinitz's blocking flow algorithm with dynamic trees
1.54 + \ref dinic70algorithm, \ref sleator83dynamic.
1.55 +- \ref GoldbergTarjan !Preflow push-relabel algorithm with dynamic trees
1.56 + \ref goldberg88newapproach, \ref sleator83dynamic.
1.57
1.58 -In most cases the \ref Preflow "Preflow" algorithm provides the
1.59 +In most cases the \ref Preflow algorithm provides the
1.60 fastest method for computing a maximum flow. All implementations
1.61 also provide functions to query the minimum cut, which is the dual
1.62 problem of maximum flow.
1.63 @@ -393,18 +399,22 @@
1.64 \brief Algorithms for finding minimum cost flows and circulations.
1.65
1.66 This group contains the algorithms for finding minimum cost flows and
1.67 -circulations. For more information about this problem and its dual
1.68 -solution see \ref min_cost_flow "Minimum Cost Flow Problem".
1.69 +circulations \ref amo93networkflows. For more information about this
1.70 +problem and its dual solution, see \ref min_cost_flow
1.71 +"Minimum Cost Flow Problem".
1.72
1.73 LEMON contains several algorithms for this problem.
1.74 - \ref NetworkSimplex Primal Network Simplex algorithm with various
1.75 - pivot strategies.
1.76 + pivot strategies \ref dantzig63linearprog, \ref kellyoneill91netsimplex.
1.77 - \ref CostScaling Push-Relabel and Augment-Relabel algorithms based on
1.78 - cost scaling.
1.79 + cost scaling \ref goldberg90approximation, \ref goldberg97efficient,
1.80 + \ref bunnagel98efficient.
1.81 - \ref CapacityScaling Successive Shortest %Path algorithm with optional
1.82 - capacity scaling.
1.83 - - \ref CancelAndTighten The Cancel and Tighten algorithm.
1.84 - - \ref CycleCanceling Cycle-Canceling algorithms.
1.85 + capacity scaling \ref edmondskarp72theoretical.
1.86 + - \ref CancelAndTighten The Cancel and Tighten algorithm
1.87 + \ref goldberg89cyclecanceling.
1.88 + - \ref CycleCanceling Cycle-Canceling algorithms
1.89 + \ref klein67primal, \ref goldberg89cyclecanceling.
1.90
1.91 In general NetworkSimplex is the most efficient implementation,
1.92 but in special cases other algorithms could be faster.
1.93 @@ -443,6 +453,43 @@
1.94 */
1.95
1.96 /**
1.97 +@defgroup min_mean_cycle Minimum Mean Cycle Algorithms
1.98 +@ingroup algs
1.99 +\brief Algorithms for finding minimum mean cycles.
1.100 +
1.101 +This group contains the algorithms for finding minimum mean cycles
1.102 +\ref clrs01algorithms, \ref amo93networkflows.
1.103 +
1.104 +The \e minimum \e mean \e cycle \e problem is to find a directed cycle
1.105 +of minimum mean length (cost) in a digraph.
1.106 +The mean length of a cycle is the average length of its arcs, i.e. the
1.107 +ratio between the total length of the cycle and the number of arcs on it.
1.108 +
1.109 +This problem has an important connection to \e conservative \e length
1.110 +\e functions, too. A length function on the arcs of a digraph is called
1.111 +conservative if and only if there is no directed cycle of negative total
1.112 +length. For an arbitrary length function, the negative of the minimum
1.113 +cycle mean is the smallest \f$\epsilon\f$ value so that increasing the
1.114 +arc lengths uniformly by \f$\epsilon\f$ results in a conservative length
1.115 +function.
1.116 +
1.117 +LEMON contains three algorithms for solving the minimum mean cycle problem:
1.118 +- \ref Karp "Karp"'s original algorithm \ref amo93networkflows,
1.119 + \ref dasdan98minmeancycle.
1.120 +- \ref HartmannOrlin "Hartmann-Orlin"'s algorithm, which is an improved
1.121 + version of Karp's algorithm \ref dasdan98minmeancycle.
1.122 +- \ref Howard "Howard"'s policy iteration algorithm
1.123 + \ref dasdan98minmeancycle.
1.124 +
1.125 +In practice, the Howard algorithm proved to be by far the most efficient
1.126 +one, though the best known theoretical bound on its running time is
1.127 +exponential.
1.128 +Both Karp and HartmannOrlin algorithms run in time O(ne) and use space
1.129 +O(n<sup>2</sup>+e), but the latter one is typically faster due to the
1.130 +applied early termination scheme.
1.131 +*/
1.132 +
1.133 +/**
1.134 @defgroup matching Matching Algorithms
1.135 @ingroup algs
1.136 \brief Algorithms for finding matchings in graphs and bipartite graphs.
1.137 @@ -534,13 +581,16 @@
1.138 */
1.139
1.140 /**
1.141 -@defgroup lp_group Lp and Mip Solvers
1.142 +@defgroup lp_group LP and MIP Solvers
1.143 @ingroup gen_opt_group
1.144 -\brief Lp and Mip solver interfaces for LEMON.
1.145 +\brief LP and MIP solver interfaces for LEMON.
1.146
1.147 -This group contains Lp and Mip solver interfaces for LEMON. The
1.148 -various LP solvers could be used in the same manner with this
1.149 -interface.
1.150 +This group contains LP and MIP solver interfaces for LEMON.
1.151 +Various LP solvers could be used in the same manner with this
1.152 +high-level interface.
1.153 +
1.154 +The currently supported solvers are \ref glpk, \ref clp, \ref cbc,
1.155 +\ref cplex, \ref soplex.
1.156 */
1.157
1.158 /**
1.159 @@ -679,8 +729,8 @@
1.160 @ingroup concept
1.161 \brief Skeleton and concept checking classes for graph structures
1.162
1.163 -This group contains the skeletons and concept checking classes of LEMON's
1.164 -graph structures and helper classes used to implement these.
1.165 +This group contains the skeletons and concept checking classes of
1.166 +graph structures.
1.167 */
1.168
1.169 /**