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 nodeset 
49 the residual graph can be accessed by another algorithm, or a nodeset 
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 SemiAdaptors Classes for Graphs 
61 @defgroup semi_adaptors SemiAdaptor 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 lightweight structures as the adaptors. 
67 On the other hand they are not lightweight 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 GraphRelated Maps. 
84 \brief Special GraphRelated 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 Breadthfirst search (Bfs) and Depthfirst 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 singlesource and 
225 The maximum flow problem is to find a flow between a single source and 
227 singletarget 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 "EdmondsKarp" 
236  \ref lemon::EdmondsKarp "EdmondsKarp" 
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 nonempty and noncomplete 
266 The minimum cut problem is to find a nonempty and noncomplete 
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 "HaoOrlin algorithm" for calculate minimum cut 
276  \ref lemon::HaoOrlin "HaoOrlin algorithm" to calculate minimum cut 
280 in directed graphs 
277 in directed graphs 
281  \ref lemon::NagamochiIbaraki "NagamochiIbaraki algorithm" for 
278  \ref lemon::NagamochiIbaraki "NagamochiIbaraki algorithm" to 
282 calculate minimum cut in undirected graphs 
279 calculate minimum cut in undirected graphs 
283  \ref lemon::GomoryHuTree "GomoryHu tree computation" for calculate all 
280  \ref lemon::GomoryHuTree "GomoryHu 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 "biedgeconnected components" width=\textwidth 
297 \image latex edge_biconnected_components.eps "biedgeconnected 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 InputOutput 
469 @defgroup io_group InputOutput 
471 \brief Several Graph InputOutput methods 
470 \brief Graph InputOutput 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 InputOutput 
478 @defgroup lemon_io Lemon InputOutput 
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 graphiopage "Graph InputOutput" 
483 You can find more about this format on the \ref graphiopage "Graph InputOutput" 
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 InputOutput. 
490 \brief Section readers and writers for lemon InputOutput. 
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 