48 this is the case. It also may happen that in a flow implementation |
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 |
49 the residual graph can be accessed by another algorithm, or a node-set |
50 is to be shrunk for another algorithm. |
50 is to be shrunk for another algorithm. |
51 LEMON also provides a variety of graphs for these requirements called |
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 |
52 \ref graph_adaptors "graph adaptors". Adaptors cannot be used alone but only |
53 in conjunction with other graph representation. |
53 in conjunction with other graph representations. |
54 |
54 |
55 You are free to use the graph structure that fit your requirements |
55 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 |
56 the best, most graph algorithms and auxiliary data structures can be used |
57 with any graph structures. |
57 with any graph structures. |
58 */ |
58 */ |
59 |
59 |
60 /** |
60 /** |
61 @defgroup semi_adaptors Semi-Adaptors Classes for Graphs |
61 @defgroup semi_adaptors Semi-Adaptor Classes for Graphs |
62 @ingroup graphs |
62 @ingroup graphs |
63 \brief Graph types between real graphs and graph adaptors. |
63 \brief Graph types between real graphs and graph adaptors. |
64 |
64 |
65 Graph types between real graphs and graph adaptors. These classes wrap |
65 This group describes some graph types between real graphs and graph adaptors. |
66 graphs to give new functionality as the adaptors do it. On the other |
66 These classes wrap graphs to give new functionality as the adaptors do it. |
67 hand they are not light-weight structures as the adaptors. |
67 On the other hand they are not light-weight structures as the adaptors. |
68 */ |
68 */ |
69 |
69 |
70 /** |
70 /** |
71 @defgroup maps Maps |
71 @defgroup maps Maps |
72 @ingroup datas |
72 @ingroup datas |
73 \brief Some special purpose map to make life easier. |
73 \brief Map structures implemented in LEMON. |
74 |
74 |
75 LEMON provides several special maps that e.g. combine |
75 This group describes the map structures implemented in LEMON. |
|
76 |
|
77 LEMON provides several special purpose maps that e.g. combine |
76 new maps from existing ones. |
78 new maps from existing ones. |
77 */ |
79 */ |
78 |
80 |
79 /** |
81 /** |
80 @defgroup graph_maps Graph Maps |
82 @defgroup graph_maps Graph Maps |
81 @ingroup maps |
83 @ingroup maps |
82 \brief Special Graph-Related Maps. |
84 \brief Special Graph-Related Maps. |
83 |
85 |
84 These maps are specifically designed to assign values to the nodes and edges of |
86 This group describes maps that are specifically designed to assign |
85 graphs. |
87 values to the nodes and edges of graphs. |
86 */ |
88 */ |
87 |
89 |
88 |
90 |
89 /** |
91 /** |
90 \defgroup map_adaptors Map Adaptors |
92 \defgroup map_adaptors Map Adaptors |
91 \ingroup maps |
93 \ingroup maps |
92 \brief Tools to create new maps from existing ones |
94 \brief Tools to create new maps from existing ones |
93 |
95 |
94 Map adaptors are used to create "implicit" maps from other maps. |
96 This group describes map adaptors that are used to create "implicit" |
|
97 maps from other maps. |
95 |
98 |
96 Most of them are \ref lemon::concepts::ReadMap "ReadMap"s. They can |
99 Most of them are \ref lemon::concepts::ReadMap "ReadMap"s. They can |
97 make arithmetic operations between one or two maps (negation, scaling, |
100 make arithmetic operations between one or two maps (negation, scaling, |
98 addition, multiplication etc.) or e.g. convert a map to another one |
101 addition, multiplication etc.) or e.g. convert a map to another one |
99 of different Value type. |
102 of different Value type. |
100 |
103 |
101 The typical usage of this classes is the passing implicit maps to |
104 The typical usage of this classes is passing implicit maps to |
102 algorithms. If a function type algorithm is called then the function |
105 algorithms. If a function type algorithm is called then the function |
103 type map adaptors can be used comfortable. For example let's see the |
106 type map adaptors can be used comfortable. For example let's see the |
104 usage of map adaptors with the \c graphToEps() function: |
107 usage of map adaptors with the \c graphToEps() function: |
105 \code |
108 \code |
106 Color nodeColor(int deg) { |
109 Color nodeColor(int deg) { |
195 */ |
198 */ |
196 |
199 |
197 /** |
200 /** |
198 @defgroup search Graph Search |
201 @defgroup search Graph Search |
199 @ingroup algs |
202 @ingroup algs |
200 \brief This group contains the common graph |
203 \brief Common graph search algorithms. |
201 search algorithms. |
204 |
202 |
205 This group describes the common graph search algorithms like |
203 This group contains the common graph |
206 Breadth-first search (Bfs) and Depth-first search (Dfs). |
204 search algorithms like Bfs and Dfs. |
|
205 */ |
207 */ |
206 |
208 |
207 /** |
209 /** |
208 @defgroup shortest_path Shortest Path algorithms |
210 @defgroup shortest_path Shortest Path algorithms |
209 @ingroup algs |
211 @ingroup algs |
210 \brief This group describes the algorithms |
212 \brief Algorithms for finding shortest paths. |
211 for finding shortest paths. |
213 |
212 |
214 This group describes the algorithms for finding shortest paths in graphs. |
213 This group describes the algorithms for finding shortest paths in |
|
214 graphs. |
|
215 |
|
216 */ |
215 */ |
217 |
216 |
218 /** |
217 /** |
219 @defgroup max_flow Maximum Flow algorithms |
218 @defgroup max_flow Maximum Flow algorithms |
220 @ingroup algs |
219 @ingroup algs |
221 \brief This group describes the algorithms for finding maximum flows. |
220 \brief Algorithms for finding maximum flows. |
222 |
221 |
223 This group describes the algorithms for finding maximum flows and |
222 This group describes the algorithms for finding maximum flows and |
224 feasible circulations. |
223 feasible circulations. |
225 |
224 |
226 The maximum flow problem is to find a flow between a single-source and |
225 The maximum flow problem is to find a flow between a single source and |
227 single-target that is maximum. Formally, there is \f$G=(V,A)\f$ |
226 a single target that is maximum. Formally, there is a \f$G=(V,A)\f$ |
228 directed graph, an \f$c_a:A\rightarrow\mathbf{R}^+_0\f$ capacity |
227 directed graph, an \f$c_a:A\rightarrow\mathbf{R}^+_0\f$ capacity |
229 function and given \f$s, t \in V\f$ source and target node. The |
228 function and given \f$s, t \in V\f$ source and target node. The |
230 maximum flow is the solution of the next optimization problem: |
229 maximum flow is the \f$f_a\f$ solution of the next optimization problem: |
231 |
230 |
232 \f[ 0 \le f_a \le c_a \f] |
231 \f[ 0 \le f_a \le c_a \f] |
233 \f[ \sum_{v\in\delta^{-}(u)}f_{vu}=\sum_{v\in\delta^{+}(u)}f_{uv} \quad u \in V \setminus \{s,t\}\f] |
232 \f[ \sum_{v\in\delta^{-}(u)}f_{vu}=\sum_{v\in\delta^{+}(u)}f_{uv} \qquad \forall u \in V \setminus \{s,t\}\f] |
234 \f[ \max \sum_{v\in\delta^{+}(s)}f_{uv} - \sum_{v\in\delta^{-}(s)}f_{vu}\f] |
233 \f[ \max \sum_{v\in\delta^{+}(s)}f_{uv} - \sum_{v\in\delta^{-}(s)}f_{vu}\f] |
235 |
234 |
236 The lemon contains several algorithms for solve maximum flow problems: |
235 LEMON contains several algorithms for solving maximum flow problems: |
237 - \ref lemon::EdmondsKarp "Edmonds-Karp" |
236 - \ref lemon::EdmondsKarp "Edmonds-Karp" |
238 - \ref lemon::Preflow "Goldberg's Preflow algorithm" |
237 - \ref lemon::Preflow "Goldberg's Preflow algorithm" |
239 - \ref lemon::DinitzSleatorTarjan "Dinitz's blocking flow algorithm with dynamic tree" |
238 - \ref lemon::DinitzSleatorTarjan "Dinitz's blocking flow algorithm with dynamic trees" |
240 - \ref lemon::GoldbergTarjan "Preflow algorithm with dynamic trees" |
239 - \ref lemon::GoldbergTarjan "Preflow algorithm with dynamic trees" |
241 |
240 |
242 In most cases the \ref lemon::Preflow "preflow" algorithm provides the |
241 In most cases the \ref lemon::Preflow "Preflow" algorithm provides the |
243 fastest method to compute the maximum flow. All impelementations |
242 fastest method to compute the maximum flow. All impelementations |
244 provides functions for query the minimum cut, which is the dual linear |
243 provides functions to query the minimum cut, which is the dual linear |
245 programming probelm of the maximum flow. |
244 programming problem of the maximum flow. |
246 |
245 |
247 */ |
246 */ |
248 |
247 |
249 /** |
248 /** |
250 @defgroup min_cost_flow Minimum Cost Flow algorithms |
249 @defgroup min_cost_flow Minimum Cost Flow algorithms |
251 @ingroup algs |
250 @ingroup algs |
252 |
251 |
253 \brief This group describes the algorithms |
252 \brief Algorithms for finding minimum cost flows and circulations. |
254 for finding minimum cost flows and circulations. |
|
255 |
253 |
256 This group describes the algorithms for finding minimum cost flows and |
254 This group describes the algorithms for finding minimum cost flows and |
257 circulations. |
255 circulations. |
258 */ |
256 */ |
259 |
257 |
260 /** |
258 /** |
261 @defgroup min_cut Minimum Cut algorithms |
259 @defgroup min_cut Minimum Cut algorithms |
262 @ingroup algs |
260 @ingroup algs |
263 |
261 |
264 \brief This group describes the algorithms for finding minimum cut in |
262 \brief Algorithms for finding minimum cut in graphs. |
265 graphs. |
|
266 |
263 |
267 This group describes the algorithms for finding minimum cut in graphs. |
264 This group describes the algorithms for finding minimum cut in graphs. |
268 |
265 |
269 The minimum cut problem is to find a non-empty and non-complete |
266 The minimum cut problem is to find a non-empty and non-complete |
270 \f$X\f$ subset of the vertices with minimum overall capacity on |
267 \f$X\f$ subset of the vertices with minimum overall capacity on |
271 outgoing arcs. Formally, there is \f$G=(V,A)\f$ directed graph, an |
268 outgoing arcs. Formally, there is \f$G=(V,A)\f$ directed graph, an |
272 \f$c_a:A\rightarrow\mathbf{R}^+_0\f$ capacity function. The minimum |
269 \f$c_a:A\rightarrow\mathbf{R}^+_0\f$ capacity function. The minimum |
273 cut is the solution of the next optimization problem: |
270 cut is the \f$X\f$ solution of the next optimization problem: |
274 |
271 |
275 \f[ \min_{X \subset V, X\not\in \{\emptyset, V\}}\sum_{uv\in A, u\in X, v\not\in X}c_{uv}\f] |
272 \f[ \min_{X \subset V, X\not\in \{\emptyset, V\}}\sum_{uv\in A, u\in X, v\not\in X}c_{uv}\f] |
276 |
273 |
277 The lemon contains several algorithms related to minimum cut problems: |
274 LEMON contains several algorithms related to minimum cut problems: |
278 |
275 |
279 - \ref lemon::HaoOrlin "Hao-Orlin algorithm" for calculate minimum cut |
276 - \ref lemon::HaoOrlin "Hao-Orlin algorithm" to calculate minimum cut |
280 in directed graphs |
277 in directed graphs |
281 - \ref lemon::NagamochiIbaraki "Nagamochi-Ibaraki algorithm" for |
278 - \ref lemon::NagamochiIbaraki "Nagamochi-Ibaraki algorithm" to |
282 calculate minimum cut in undirected graphs |
279 calculate minimum cut in undirected graphs |
283 - \ref lemon::GomoryHuTree "Gomory-Hu tree computation" for calculate all |
280 - \ref lemon::GomoryHuTree "Gomory-Hu tree computation" to calculate all |
284 pairs minimum cut in undirected graphs |
281 pairs minimum cut in undirected graphs |
285 |
282 |
286 If you want to find minimum cut just between two distinict nodes, |
283 If you want to find minimum cut just between two distinict nodes, |
287 please see the \ref max_flow "Maximum Flow page". |
284 please see the \ref max_flow "Maximum Flow page". |
288 |
285 |
289 */ |
286 */ |
290 |
287 |
291 /** |
288 /** |
292 @defgroup graph_prop Connectivity and other graph properties |
289 @defgroup graph_prop Connectivity and other graph properties |
293 @ingroup algs |
290 @ingroup algs |
294 \brief This group describes the algorithms |
291 \brief Algorithms for discovering the graph properties |
295 for discover the graph properties |
292 |
296 |
293 This group describes the algorithms for discovering the graph properties |
297 This group describes the algorithms for discover the graph properties |
294 like connectivity, bipartiteness, euler property, simplicity etc. |
298 like connectivity, bipartiteness, euler property, simplicity, etc... |
|
299 |
295 |
300 \image html edge_biconnected_components.png |
296 \image html edge_biconnected_components.png |
301 \image latex edge_biconnected_components.eps "bi-edge-connected components" width=\textwidth |
297 \image latex edge_biconnected_components.eps "bi-edge-connected components" width=\textwidth |
302 */ |
298 */ |
303 |
299 |
304 /** |
300 /** |
305 @defgroup planar Planarity embedding and drawing |
301 @defgroup planar Planarity embedding and drawing |
306 @ingroup algs |
302 @ingroup algs |
307 \brief This group contains algorithms for planarity embedding and drawing |
303 \brief Algorithms for planarity checking, embedding and drawing |
308 |
304 |
309 This group contains algorithms for planarity checking, embedding and drawing. |
305 This group describes the algorithms for planarity checking, embedding and drawing. |
310 |
306 |
311 \image html planar.png |
307 \image html planar.png |
312 \image latex planar.eps "Plane graph" width=\textwidth |
308 \image latex planar.eps "Plane graph" width=\textwidth |
313 */ |
309 */ |
314 |
310 |
315 /** |
311 /** |
316 @defgroup matching Matching algorithms |
312 @defgroup matching Matching algorithms |
317 @ingroup algs |
313 @ingroup algs |
318 \brief This group describes the algorithms |
314 \brief Algorithms for finding matchings in graphs and bipartite graphs. |
319 for find matchings in graphs and bipartite graphs. |
315 |
320 |
316 This group contains algorithm objects and functions to calculate |
321 This group provides some algorithm objects and function to calculate |
|
322 matchings in graphs and bipartite graphs. The general matching problem is |
317 matchings in graphs and bipartite graphs. The general matching problem is |
323 finding a subset of the edges which does not shares common endpoints. |
318 finding a subset of the edges which does not shares common endpoints. |
324 |
319 |
325 There are several different algorithms for calculate matchings in |
320 There are several different algorithms for calculate matchings in |
326 graphs. The matching problems in bipartite graphs are generally |
321 graphs. The matching problems in bipartite graphs are generally |
404 */ |
399 */ |
405 |
400 |
406 /** |
401 /** |
407 @defgroup lp_utils Tools for Lp and Mip solvers |
402 @defgroup lp_utils Tools for Lp and Mip solvers |
408 @ingroup lp_group |
403 @ingroup lp_group |
409 \brief This group adds some helper tools to the Lp and Mip solvers |
404 \brief Helper tools to the Lp and Mip solvers. |
410 implemented in LEMON. |
|
411 |
405 |
412 This group adds some helper tools to general optimization framework |
406 This group adds some helper tools to general optimization framework |
413 implemented in LEMON. |
407 implemented in LEMON. |
414 */ |
408 */ |
415 |
409 |
416 /** |
410 /** |
417 @defgroup metah Metaheuristics |
411 @defgroup metah Metaheuristics |
418 @ingroup gen_opt_group |
412 @ingroup gen_opt_group |
419 \brief Metaheuristics for LEMON library. |
413 \brief Metaheuristics for LEMON library. |
420 |
414 |
421 This group contains some metaheuristic optimization tools. |
415 This group describes some metaheuristic optimization tools. |
422 */ |
416 */ |
423 |
417 |
424 /** |
418 /** |
425 @defgroup utils Tools and Utilities |
419 @defgroup utils Tools and Utilities |
426 \brief Tools and Utilities for Programming in LEMON |
420 \brief Tools and utilities for programming in LEMON |
427 |
421 |
428 Tools and Utilities for Programming in LEMON |
422 Tools and utilities for programming in LEMON. |
429 */ |
423 */ |
430 |
424 |
431 /** |
425 /** |
432 @defgroup gutils Basic Graph Utilities |
426 @defgroup gutils Basic Graph Utilities |
433 @ingroup utils |
427 @ingroup utils |
434 \brief This group describes some simple basic graph utilities. |
428 \brief Simple basic graph utilities. |
435 |
429 |
436 This group describes some simple basic graph utilities. |
430 This group describes some simple basic graph utilities. |
437 */ |
431 */ |
438 |
432 |
439 /** |
433 /** |
440 @defgroup misc Miscellaneous Tools |
434 @defgroup misc Miscellaneous Tools |
441 @ingroup utils |
435 @ingroup utils |
442 Here you can find several useful tools for development, |
436 \brief Tools for development, debugging and testing. |
|
437 |
|
438 This group describes several useful tools for development, |
443 debugging and testing. |
439 debugging and testing. |
444 */ |
440 */ |
445 |
|
446 |
441 |
447 /** |
442 /** |
448 @defgroup timecount Time measuring and Counting |
443 @defgroup timecount Time measuring and Counting |
449 @ingroup misc |
444 @ingroup misc |
450 Here you can find simple tools for measuring the performance |
445 \brief Simple tools for measuring the performance of algorithms. |
|
446 |
|
447 This group describes simple tools for measuring the performance |
451 of algorithms. |
448 of algorithms. |
452 */ |
449 */ |
453 |
450 |
454 /** |
451 /** |
455 @defgroup graphbits Tools for Graph Implementation |
452 @defgroup graphbits Tools for Graph Implementation |
456 @ingroup utils |
453 @ingroup utils |
457 \brief Tools to Make It Easier to Make Graphs. |
454 \brief Tools to make it easier to create graphs. |
458 |
455 |
459 This group describes the tools that makes it easier to make graphs and |
456 This group describes the tools that makes it easier to create graphs and |
460 the maps that dynamically update with the graph changes. |
457 the maps that dynamically update with the graph changes. |
461 */ |
458 */ |
462 |
459 |
463 /** |
460 /** |
464 @defgroup exceptions Exceptions |
461 @defgroup exceptions Exceptions |
465 @ingroup utils |
462 @ingroup utils |
466 This group contains the exceptions thrown by LEMON library |
463 \brief Exceptions defined in LEMON. |
|
464 |
|
465 This group describes the exceptions defined in LEMON. |
467 */ |
466 */ |
468 |
467 |
469 /** |
468 /** |
470 @defgroup io_group Input-Output |
469 @defgroup io_group Input-Output |
471 \brief Several Graph Input-Output methods |
470 \brief Graph Input-Output methods |
472 |
471 |
473 Here you can find tools for importing and exporting graphs |
472 This group describes the tools for importing and exporting graphs |
474 and graph related data. Now it supports the LEMON format, the |
473 and graph related data. Now it supports the LEMON format, the |
475 \c DIMACS format and the encapsulated postscript format. |
474 \c DIMACS format and the encapsulated postscript (EPS) format. |
476 */ |
475 */ |
477 |
476 |
478 /** |
477 /** |
479 @defgroup lemon_io Lemon Input-Output |
478 @defgroup lemon_io Lemon Input-Output |
480 @ingroup io_group |
479 @ingroup io_group |
481 \brief Reading and writing LEMON format |
480 \brief Reading and writing LEMON format |
482 |
481 |
483 Methods for reading and writing LEMON format. More about this |
482 This group describes methods for reading and writing LEMON format. |
484 format you can find on the \ref graph-io-page "Graph Input-Output" |
483 You can find more about this format on the \ref graph-io-page "Graph Input-Output" |
485 tutorial pages. |
484 tutorial pages. |
486 */ |
485 */ |
487 |
486 |
488 /** |
487 /** |
489 @defgroup section_io Section readers and writers |
488 @defgroup section_io Section readers and writers |
490 @ingroup lemon_io |
489 @ingroup lemon_io |
491 \brief Section readers and writers for lemon Input-Output. |
490 \brief Section readers and writers for lemon Input-Output. |
492 |
491 |
493 Here you can find which section readers and writers can attach to |
492 This group describes section readers and writers that can be attached to |
494 the LemonReader and LemonWriter. |
493 \ref LemonReader and \ref LemonWriter. |
495 */ |
494 */ |
496 |
495 |
497 /** |
496 /** |
498 @defgroup item_io Item Readers and Writers |
497 @defgroup item_io Item Readers and Writers |
499 @ingroup lemon_io |
498 @ingroup lemon_io |