doc/groups.dox
 changeset 802 134852d7fb0a parent 789 8e68671af789 child 817 432c54cec63c
     1.1 --- a/doc/groups.dox	Sat Oct 10 08:15:07 2009 +0200
1.2 +++ b/doc/groups.dox	Sat Oct 10 08:18:46 2009 +0200
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.68 -solution see \ref min_cost_flow "Minimum Cost Flow Problem".
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 @@ -534,13 +544,16 @@
1.94  */
1.95
1.96  /**
1.97 -@defgroup lp_group Lp and Mip Solvers
1.98 +@defgroup lp_group LP and MIP Solvers
1.99  @ingroup gen_opt_group
1.100 -\brief Lp and Mip solver interfaces for LEMON.
1.101 +\brief LP and MIP solver interfaces for LEMON.
1.102
1.103 -This group contains Lp and Mip solver interfaces for LEMON. The
1.104 -various LP solvers could be used in the same manner with this
1.105 -interface.
1.106 +This group contains LP and MIP solver interfaces for LEMON.
1.107 +Various LP solvers could be used in the same manner with this
1.108 +high-level interface.
1.109 +
1.110 +The currently supported solvers are \ref glpk, \ref clp, \ref cbc,
1.111 +\ref cplex, \ref soplex.
1.112  */
1.113
1.114  /**