1.1 --- a/doc/groups.dox Mon Jul 16 16:21:40 2018 +0200
1.2 +++ b/doc/groups.dox Wed Oct 17 19:14:07 2018 +0200
1.3 @@ -2,7 +2,7 @@
1.4 *
1.5 * This file is a part of LEMON, a generic C++ optimization library.
1.6 *
1.7 - * Copyright (C) 2003-2010
1.8 + * Copyright (C) 2003-2013
1.9 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
1.10 * (Egervary Research Group on Combinatorial Optimization, EGRES).
1.11 *
1.12 @@ -112,6 +112,14 @@
1.13 obtained. For other examples, the interested user is referred to the
1.14 detailed documentation of particular adaptors.
1.15
1.16 +Since the adaptor classes conform to the \ref graph_concepts "graph concepts",
1.17 +an adaptor can even be applied to another one.
1.18 +The following image illustrates a situation when a \ref SubDigraph adaptor
1.19 +is applied on a digraph and \ref Undirector is applied on the subgraph.
1.20 +
1.21 +\image html adaptors2.png
1.22 +\image latex adaptors2.eps "Using graph adaptors" width=\textwidth
1.23 +
1.24 The behavior of graph adaptors can be very different. Some of them keep
1.25 capabilities of the original graph while in other cases this would be
1.26 meaningless. This means that the concepts that they meet depend
1.27 @@ -309,7 +317,7 @@
1.28
1.29 This group contains the common graph search algorithms, namely
1.30 \e breadth-first \e search (BFS) and \e depth-first \e search (DFS)
1.31 -\ref clrs01algorithms.
1.32 +\cite clrs01algorithms.
1.33 */
1.34
1.35 /**
1.36 @@ -318,7 +326,7 @@
1.37 \brief Algorithms for finding shortest paths.
1.38
1.39 This group contains the algorithms for finding shortest paths in digraphs
1.40 -\ref clrs01algorithms.
1.41 +\cite clrs01algorithms.
1.42
1.43 - \ref Dijkstra algorithm for finding shortest paths from a source node
1.44 when all arc lengths are non-negative.
1.45 @@ -340,7 +348,7 @@
1.46 \brief Algorithms for finding minimum cost spanning trees and arborescences.
1.47
1.48 This group contains the algorithms for finding minimum cost spanning
1.49 -trees and arborescences \ref clrs01algorithms.
1.50 +trees and arborescences \cite clrs01algorithms.
1.51 */
1.52
1.53 /**
1.54 @@ -349,7 +357,7 @@
1.55 \brief Algorithms for finding maximum flows.
1.56
1.57 This group contains the algorithms for finding maximum flows and
1.58 -feasible circulations \ref clrs01algorithms, \ref amo93networkflows.
1.59 +feasible circulations \cite clrs01algorithms, \cite amo93networkflows.
1.60
1.61 The \e maximum \e flow \e problem is to find a flow of maximum value between
1.62 a single source and a single target. Formally, there is a \f$G=(V,A)\f$
1.63 @@ -365,13 +373,13 @@
1.64
1.65 LEMON contains several algorithms for solving maximum flow problems:
1.66 - \ref EdmondsKarp Edmonds-Karp algorithm
1.67 - \ref edmondskarp72theoretical.
1.68 + \cite edmondskarp72theoretical.
1.69 - \ref Preflow Goldberg-Tarjan's preflow push-relabel algorithm
1.70 - \ref goldberg88newapproach.
1.71 + \cite goldberg88newapproach.
1.72 - \ref DinitzSleatorTarjan Dinitz's blocking flow algorithm with dynamic trees
1.73 - \ref dinic70algorithm, \ref sleator83dynamic.
1.74 + \cite dinic70algorithm, \cite sleator83dynamic.
1.75 - \ref GoldbergTarjan !Preflow push-relabel algorithm with dynamic trees
1.76 - \ref goldberg88newapproach, \ref sleator83dynamic.
1.77 + \cite goldberg88newapproach, \cite sleator83dynamic.
1.78
1.79 In most cases the \ref Preflow algorithm provides the
1.80 fastest method for computing a maximum flow. All implementations
1.81 @@ -391,25 +399,41 @@
1.82 \brief Algorithms for finding minimum cost flows and circulations.
1.83
1.84 This group contains the algorithms for finding minimum cost flows and
1.85 -circulations \ref amo93networkflows. For more information about this
1.86 -problem and its dual solution, see \ref min_cost_flow
1.87 +circulations \cite amo93networkflows. For more information about this
1.88 +problem and its dual solution, see: \ref min_cost_flow
1.89 "Minimum Cost Flow Problem".
1.90
1.91 LEMON contains several algorithms for this problem.
1.92 - \ref NetworkSimplex Primal Network Simplex algorithm with various
1.93 - pivot strategies \ref dantzig63linearprog, \ref kellyoneill91netsimplex.
1.94 + pivot strategies \cite dantzig63linearprog, \cite kellyoneill91netsimplex.
1.95 - \ref CostScaling Cost Scaling algorithm based on push/augment and
1.96 - relabel operations \ref goldberg90approximation, \ref goldberg97efficient,
1.97 - \ref bunnagel98efficient.
1.98 + relabel operations \cite goldberg90approximation, \cite goldberg97efficient,
1.99 + \cite bunnagel98efficient.
1.100 - \ref CapacityScaling Capacity Scaling algorithm based on the successive
1.101 - shortest path method \ref edmondskarp72theoretical.
1.102 + shortest path method \cite edmondskarp72theoretical.
1.103 - \ref CycleCanceling Cycle-Canceling algorithms, two of which are
1.104 - strongly polynomial \ref klein67primal, \ref goldberg89cyclecanceling.
1.105 + strongly polynomial \cite klein67primal, \cite goldberg89cyclecanceling.
1.106
1.107 -In general NetworkSimplex is the most efficient implementation,
1.108 -but in special cases other algorithms could be faster.
1.109 +In general, \ref NetworkSimplex and \ref CostScaling are the most efficient
1.110 +implementations.
1.111 +\ref NetworkSimplex is usually the fastest on relatively small graphs (up to
1.112 +several thousands of nodes) and on dense graphs, while \ref CostScaling is
1.113 +typically more efficient on large graphs (e.g. hundreds of thousands of
1.114 +nodes or above), especially if they are sparse.
1.115 +However, other algorithms could be faster in special cases.
1.116 For example, if the total supply and/or capacities are rather small,
1.117 -CapacityScaling is usually the fastest algorithm (without effective scaling).
1.118 +\ref CapacityScaling is usually the fastest algorithm
1.119 +(without effective scaling).
1.120 +
1.121 +These classes are intended to be used with integer-valued input data
1.122 +(capacities, supply values, and costs), except for \ref CapacityScaling,
1.123 +which is capable of handling real-valued arc costs (other numerical
1.124 +data are required to be integer).
1.125 +
1.126 +For more details about these implementations and for a comprehensive
1.127 +experimental study, see the paper \cite KiralyKovacs12MCF.
1.128 +It also compares these codes to other publicly available
1.129 +minimum cost flow solvers.
1.130 */
1.131
1.132 /**
1.133 @@ -448,7 +472,7 @@
1.134 \brief Algorithms for finding minimum mean cycles.
1.135
1.136 This group contains the algorithms for finding minimum mean cycles
1.137 -\ref clrs01algorithms, \ref amo93networkflows.
1.138 +\cite amo93networkflows, \cite karp78characterization.
1.139
1.140 The \e minimum \e mean \e cycle \e problem is to find a directed cycle
1.141 of minimum mean length (cost) in a digraph.
1.142 @@ -464,19 +488,17 @@
1.143 function.
1.144
1.145 LEMON contains three algorithms for solving the minimum mean cycle problem:
1.146 -- \ref KarpMmc Karp's original algorithm \ref amo93networkflows,
1.147 - \ref dasdan98minmeancycle.
1.148 +- \ref KarpMmc Karp's original algorithm \cite karp78characterization.
1.149 - \ref HartmannOrlinMmc Hartmann-Orlin's algorithm, which is an improved
1.150 - version of Karp's algorithm \ref dasdan98minmeancycle.
1.151 + version of Karp's algorithm \cite hartmann93finding.
1.152 - \ref HowardMmc Howard's policy iteration algorithm
1.153 - \ref dasdan98minmeancycle.
1.154 + \cite dasdan98minmeancycle, \cite dasdan04experimental.
1.155
1.156 -In practice, the \ref HowardMmc "Howard" algorithm proved to be by far the
1.157 +In practice, the \ref HowardMmc "Howard" algorithm turned out to be by far the
1.158 most efficient one, though the best known theoretical bound on its running
1.159 time is exponential.
1.160 Both \ref KarpMmc "Karp" and \ref HartmannOrlinMmc "Hartmann-Orlin" algorithms
1.161 -run in time O(ne) and use space O(n<sup>2</sup>+e), but the latter one is
1.162 -typically faster due to the applied early termination scheme.
1.163 +run in time O(nm) and use space O(n<sup>2</sup>+m).
1.164 */
1.165
1.166 /**
1.167 @@ -539,7 +561,7 @@
1.168 */
1.169
1.170 /**
1.171 -@defgroup planar Planarity Embedding and Drawing
1.172 +@defgroup planar Planar Embedding and Drawing
1.173 @ingroup algs
1.174 \brief Algorithms for planarity checking, embedding and drawing
1.175
1.176 @@ -551,12 +573,52 @@
1.177 */
1.178
1.179 /**
1.180 -@defgroup approx Approximation Algorithms
1.181 +@defgroup tsp Traveling Salesman Problem
1.182 +@ingroup algs
1.183 +\brief Algorithms for the symmetric traveling salesman problem
1.184 +
1.185 +This group contains basic heuristic algorithms for the the symmetric
1.186 +\e traveling \e salesman \e problem (TSP).
1.187 +Given an \ref FullGraph "undirected full graph" with a cost map on its edges,
1.188 +the problem is to find a shortest possible tour that visits each node exactly
1.189 +once (i.e. the minimum cost Hamiltonian cycle).
1.190 +
1.191 +These TSP algorithms are intended to be used with a \e metric \e cost
1.192 +\e function, i.e. the edge costs should satisfy the triangle inequality.
1.193 +Otherwise the algorithms could yield worse results.
1.194 +
1.195 +LEMON provides five well-known heuristics for solving symmetric TSP:
1.196 + - \ref NearestNeighborTsp Neareast neighbor algorithm
1.197 + - \ref GreedyTsp Greedy algorithm
1.198 + - \ref InsertionTsp Insertion heuristic (with four selection methods)
1.199 + - \ref ChristofidesTsp Christofides algorithm
1.200 + - \ref Opt2Tsp 2-opt algorithm
1.201 +
1.202 +\ref NearestNeighborTsp, \ref GreedyTsp, and \ref InsertionTsp are the fastest
1.203 +solution methods. Furthermore, \ref InsertionTsp is usually quite effective.
1.204 +
1.205 +\ref ChristofidesTsp is somewhat slower, but it has the best guaranteed
1.206 +approximation factor: 3/2.
1.207 +
1.208 +\ref Opt2Tsp usually provides the best results in practice, but
1.209 +it is the slowest method. It can also be used to improve given tours,
1.210 +for example, the results of other algorithms.
1.211 +
1.212 +\image html tsp.png
1.213 +\image latex tsp.eps "Traveling salesman problem" width=\textwidth
1.214 +*/
1.215 +
1.216 +/**
1.217 +@defgroup approx_algs Approximation Algorithms
1.218 @ingroup algs
1.219 \brief Approximation algorithms.
1.220
1.221 This group contains the approximation and heuristic algorithms
1.222 implemented in LEMON.
1.223 +
1.224 +<b>Maximum Clique Problem</b>
1.225 + - \ref GrossoLocatelliPullanMc An efficient heuristic algorithm of
1.226 + Grosso, Locatelli, and Pullan.
1.227 */
1.228
1.229 /**
1.230 @@ -586,8 +648,8 @@
1.231 Various LP solvers could be used in the same manner with this
1.232 high-level interface.
1.233
1.234 -The currently supported solvers are \ref glpk, \ref clp, \ref cbc,
1.235 -\ref cplex, \ref soplex.
1.236 +The currently supported solvers are \cite glpk, \cite clp, \cite cbc,
1.237 +\cite cplex, \cite soplex.
1.238 */
1.239
1.240 /**
1.241 @@ -674,6 +736,8 @@
1.242
1.243 This group contains general \c EPS drawing methods and special
1.244 graph exporting tools.
1.245 +
1.246 +\image html graph_to_eps.png
1.247 */
1.248
1.249 /**