38 accessed. LEMON provides several physical graph structures to meet |
38 accessed. LEMON provides several physical graph structures to meet |
39 the diverging requirements of the possible users. In order to save on |
39 the diverging requirements of the possible users. In order to save on |
40 running time or on memory usage, some structures may fail to provide |
40 running time or on memory usage, some structures may fail to provide |
41 some graph features like arc/edge or node deletion. |
41 some graph features like arc/edge or node deletion. |
42 |
42 |
43 Alteration of standard containers need a very limited number of |
|
44 operations, these together satisfy the everyday requirements. |
|
45 In the case of graph structures, different operations are needed which do |
|
46 not alter the physical graph, but gives another view. If some nodes or |
|
47 arcs have to be hidden or the reverse oriented graph have to be used, then |
|
48 this is the case. It also may happen that in a flow implementation |
|
49 the residual graph can be accessed by another algorithm, or a node-set |
|
50 is to be shrunk for another algorithm. |
|
51 LEMON also provides a variety of graphs for these requirements called |
|
52 \ref graph_adaptors "graph adaptors". Adaptors cannot be used alone but only |
|
53 in conjunction with other graph representations. |
|
54 |
|
55 You are free to use the graph structure that fit your requirements |
43 You are free to use the graph structure that fit your requirements |
56 the best, most graph algorithms and auxiliary data structures can be used |
44 the best, most graph algorithms and auxiliary data structures can be used |
57 with any graph structures. |
45 with any graph structures. |
58 */ |
|
59 |
|
60 /** |
|
61 @defgroup semi_adaptors Semi-Adaptor Classes for Graphs |
|
62 @ingroup graphs |
|
63 \brief Graph types between real graphs and graph adaptors. |
|
64 |
|
65 This group describes some graph types between real graphs and graph adaptors. |
|
66 These classes wrap graphs to give new functionality as the adaptors do it. |
|
67 On the other hand they are not light-weight structures as the adaptors. |
|
68 */ |
46 */ |
69 |
47 |
70 /** |
48 /** |
71 @defgroup maps Maps |
49 @defgroup maps Maps |
72 @ingroup datas |
50 @ingroup datas |
211 |
181 |
212 This group describes the algorithms for finding shortest paths in graphs. |
182 This group describes the algorithms for finding shortest paths in graphs. |
213 */ |
183 */ |
214 |
184 |
215 /** |
185 /** |
216 @defgroup max_flow Maximum Flow algorithms |
|
217 @ingroup algs |
|
218 \brief Algorithms for finding maximum flows. |
|
219 |
|
220 This group describes the algorithms for finding maximum flows and |
|
221 feasible circulations. |
|
222 |
|
223 The maximum flow problem is to find a flow between a single source and |
|
224 a single target that is maximum. Formally, there is a \f$G=(V,A)\f$ |
|
225 directed graph, an \f$c_a:A\rightarrow\mathbf{R}^+_0\f$ capacity |
|
226 function and given \f$s, t \in V\f$ source and target node. The |
|
227 maximum flow is the \f$f_a\f$ solution of the next optimization problem: |
|
228 |
|
229 \f[ 0 \le f_a \le c_a \f] |
|
230 \f[ \sum_{v\in\delta^{-}(u)}f_{vu}=\sum_{v\in\delta^{+}(u)}f_{uv} |
|
231 \qquad \forall u \in V \setminus \{s,t\}\f] |
|
232 \f[ \max \sum_{v\in\delta^{+}(s)}f_{uv} - \sum_{v\in\delta^{-}(s)}f_{vu}\f] |
|
233 |
|
234 LEMON contains several algorithms for solving maximum flow problems: |
|
235 - \ref lemon::EdmondsKarp "Edmonds-Karp" |
|
236 - \ref lemon::Preflow "Goldberg's Preflow algorithm" |
|
237 - \ref lemon::DinitzSleatorTarjan "Dinitz's blocking flow algorithm with dynamic trees" |
|
238 - \ref lemon::GoldbergTarjan "Preflow algorithm with dynamic trees" |
|
239 |
|
240 In most cases the \ref lemon::Preflow "Preflow" algorithm provides the |
|
241 fastest method to compute the maximum flow. All impelementations |
|
242 provides functions to query the minimum cut, which is the dual linear |
|
243 programming problem of the maximum flow. |
|
244 |
|
245 */ |
|
246 |
|
247 /** |
|
248 @defgroup min_cost_flow Minimum Cost Flow algorithms |
|
249 @ingroup algs |
|
250 |
|
251 \brief Algorithms for finding minimum cost flows and circulations. |
|
252 |
|
253 This group describes the algorithms for finding minimum cost flows and |
|
254 circulations. |
|
255 */ |
|
256 |
|
257 /** |
|
258 @defgroup min_cut Minimum Cut algorithms |
|
259 @ingroup algs |
|
260 |
|
261 \brief Algorithms for finding minimum cut in graphs. |
|
262 |
|
263 This group describes the algorithms for finding minimum cut in graphs. |
|
264 |
|
265 The minimum cut problem is to find a non-empty and non-complete |
|
266 \f$X\f$ subset of the vertices with minimum overall capacity on |
|
267 outgoing arcs. Formally, there is \f$G=(V,A)\f$ directed graph, an |
|
268 \f$c_a:A\rightarrow\mathbf{R}^+_0\f$ capacity function. The minimum |
|
269 cut is the \f$X\f$ solution of the next optimization problem: |
|
270 |
|
271 \f[ \min_{X \subset V, X\not\in \{\emptyset, V\}} |
|
272 \sum_{uv\in A, u\in X, v\not\in X}c_{uv}\f] |
|
273 |
|
274 LEMON contains several algorithms related to minimum cut problems: |
|
275 |
|
276 - \ref lemon::HaoOrlin "Hao-Orlin algorithm" to calculate minimum cut |
|
277 in directed graphs |
|
278 - \ref lemon::NagamochiIbaraki "Nagamochi-Ibaraki algorithm" to |
|
279 calculate minimum cut in undirected graphs |
|
280 - \ref lemon::GomoryHuTree "Gomory-Hu tree computation" to calculate all |
|
281 pairs minimum cut in undirected graphs |
|
282 |
|
283 If you want to find minimum cut just between two distinict nodes, |
|
284 please see the \ref max_flow "Maximum Flow page". |
|
285 |
|
286 */ |
|
287 |
|
288 /** |
|
289 @defgroup graph_prop Connectivity and other graph properties |
|
290 @ingroup algs |
|
291 \brief Algorithms for discovering the graph properties |
|
292 |
|
293 This group describes the algorithms for discovering the graph properties |
|
294 like connectivity, bipartiteness, euler property, simplicity etc. |
|
295 |
|
296 \image html edge_biconnected_components.png |
|
297 \image latex edge_biconnected_components.eps "bi-edge-connected components" width=\textwidth |
|
298 */ |
|
299 |
|
300 /** |
|
301 @defgroup planar Planarity embedding and drawing |
|
302 @ingroup algs |
|
303 \brief Algorithms for planarity checking, embedding and drawing |
|
304 |
|
305 This group describes the algorithms for planarity checking, |
|
306 embedding and drawing. |
|
307 |
|
308 \image html planar.png |
|
309 \image latex planar.eps "Plane graph" width=\textwidth |
|
310 */ |
|
311 |
|
312 /** |
|
313 @defgroup matching Matching algorithms |
|
314 @ingroup algs |
|
315 \brief Algorithms for finding matchings in graphs and bipartite graphs. |
|
316 |
|
317 This group contains algorithm objects and functions to calculate |
|
318 matchings in graphs and bipartite graphs. The general matching problem is |
|
319 finding a subset of the arcs which does not shares common endpoints. |
|
320 |
|
321 There are several different algorithms for calculate matchings in |
|
322 graphs. The matching problems in bipartite graphs are generally |
|
323 easier than in general graphs. The goal of the matching optimization |
|
324 can be the finding maximum cardinality, maximum weight or minimum cost |
|
325 matching. The search can be constrained to find perfect or |
|
326 maximum cardinality matching. |
|
327 |
|
328 LEMON contains the next algorithms: |
|
329 - \ref lemon::MaxBipartiteMatching "MaxBipartiteMatching" Hopcroft-Karp |
|
330 augmenting path algorithm for calculate maximum cardinality matching in |
|
331 bipartite graphs |
|
332 - \ref lemon::PrBipartiteMatching "PrBipartiteMatching" Push-Relabel |
|
333 algorithm for calculate maximum cardinality matching in bipartite graphs |
|
334 - \ref lemon::MaxWeightedBipartiteMatching "MaxWeightedBipartiteMatching" |
|
335 Successive shortest path algorithm for calculate maximum weighted matching |
|
336 and maximum weighted bipartite matching in bipartite graph |
|
337 - \ref lemon::MinCostMaxBipartiteMatching "MinCostMaxBipartiteMatching" |
|
338 Successive shortest path algorithm for calculate minimum cost maximum |
|
339 matching in bipartite graph |
|
340 - \ref lemon::MaxMatching "MaxMatching" Edmond's blossom shrinking algorithm |
|
341 for calculate maximum cardinality matching in general graph |
|
342 - \ref lemon::MaxWeightedMatching "MaxWeightedMatching" Edmond's blossom |
|
343 shrinking algorithm for calculate maximum weighted matching in general |
|
344 graph |
|
345 - \ref lemon::MaxWeightedPerfectMatching "MaxWeightedPerfectMatching" |
|
346 Edmond's blossom shrinking algorithm for calculate maximum weighted |
|
347 perfect matching in general graph |
|
348 |
|
349 \image html bipartite_matching.png |
|
350 \image latex bipartite_matching.eps "Bipartite Matching" width=\textwidth |
|
351 |
|
352 */ |
|
353 |
|
354 /** |
|
355 @defgroup spantree Minimum Spanning Tree algorithms |
186 @defgroup spantree Minimum Spanning Tree algorithms |
356 @ingroup algs |
187 @ingroup algs |
357 \brief Algorithms for finding a minimum cost spanning tree in a graph. |
188 \brief Algorithms for finding a minimum cost spanning tree in a graph. |
358 |
189 |
359 This group describes the algorithms for finding a minimum cost spanning |
190 This group describes the algorithms for finding a minimum cost spanning |
360 tree in a graph |
191 tree in a graph |
361 */ |
192 */ |
362 |
193 |
363 |
|
364 /** |
|
365 @defgroup auxalg Auxiliary algorithms |
|
366 @ingroup algs |
|
367 \brief Auxiliary algorithms implemented in LEMON. |
|
368 |
|
369 This group describes some algorithms implemented in LEMON |
|
370 in order to make it easier to implement complex algorithms. |
|
371 */ |
|
372 |
|
373 /** |
|
374 @defgroup approx Approximation algorithms |
|
375 \brief Approximation algorithms. |
|
376 |
|
377 This group describes the approximation and heuristic algorithms |
|
378 implemented in LEMON. |
|
379 */ |
|
380 |
|
381 /** |
|
382 @defgroup gen_opt_group General Optimization Tools |
|
383 \brief This group describes some general optimization frameworks |
|
384 implemented in LEMON. |
|
385 |
|
386 This group describes some general optimization frameworks |
|
387 implemented in LEMON. |
|
388 |
|
389 */ |
|
390 |
|
391 /** |
|
392 @defgroup lp_group Lp and Mip solvers |
|
393 @ingroup gen_opt_group |
|
394 \brief Lp and Mip solver interfaces for LEMON. |
|
395 |
|
396 This group describes Lp and Mip solver interfaces for LEMON. The |
|
397 various LP solvers could be used in the same manner with this |
|
398 interface. |
|
399 |
|
400 */ |
|
401 |
|
402 /** |
|
403 @defgroup lp_utils Tools for Lp and Mip solvers |
|
404 @ingroup lp_group |
|
405 \brief Helper tools to the Lp and Mip solvers. |
|
406 |
|
407 This group adds some helper tools to general optimization framework |
|
408 implemented in LEMON. |
|
409 */ |
|
410 |
|
411 /** |
|
412 @defgroup metah Metaheuristics |
|
413 @ingroup gen_opt_group |
|
414 \brief Metaheuristics for LEMON library. |
|
415 |
|
416 This group describes some metaheuristic optimization tools. |
|
417 */ |
|
418 |
|
419 /** |
194 /** |
420 @defgroup utils Tools and Utilities |
195 @defgroup utils Tools and Utilities |
421 \brief Tools and utilities for programming in LEMON |
196 \brief Tools and utilities for programming in LEMON |
422 |
197 |
423 Tools and utilities for programming in LEMON. |
198 Tools and utilities for programming in LEMON. |