doc/groups.dox
 changeset 314 2cc60866a0c9 parent 236 da953e387d31 child 318 1e2d6ca80793 child 327 12626fc94ccf
equal inserted replaced
9:687f577f60dc 10:c4469754715c
    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 representations.
    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 structure.

    58

    59 <b>See also:</b> \ref graph_concepts "Graph Structure Concepts".
    58 */
    60 */
    59
    61
    60 /**
    62 /**
    61 @defgroup semi_adaptors Semi-Adaptor Classes for Graphs
    63 @defgroup semi_adaptors Semi-Adaptor Classes for Graphs
    62 @ingroup graphs
    64 @ingroup graphs
    72 @ingroup datas
    74 @ingroup datas
    73 \brief Map structures implemented in LEMON.
    75 \brief Map structures implemented in LEMON.
    74
    76
    75 This group describes the map structures implemented in LEMON.
    77 This group describes the map structures implemented in LEMON.
    76
    78
    77 LEMON provides several special purpose maps that e.g. combine
    79 LEMON provides several special purpose maps and map adaptors that e.g. combine
    78 new maps from existing ones.
    80 new maps from existing ones.

    81

    82 <b>See also:</b> \ref map_concepts "Map Concepts".
    79 */
    83 */
    80
    84
    81 /**
    85 /**
    82 @defgroup graph_maps Graph Maps
    86 @defgroup graph_maps Graph Maps
    83 @ingroup maps
    87 @ingroup maps
    84 \brief Special graph-related maps.
    88 \brief Special graph-related maps.
    85
    89
    86 This group describes maps that are specifically designed to assign
    90 This group describes maps that are specifically designed to assign
    87 values to the nodes and arcs of graphs.
    91 values to the nodes and arcs of graphs.
    88 */
    92 */
    90
    93
    91 /**
    94 /**
    92 \defgroup map_adaptors Map Adaptors
    95 \defgroup map_adaptors Map Adaptors
    93 \ingroup maps
    96 \ingroup maps
    94 \brief Tools to create new maps from existing ones
    97 \brief Tools to create new maps from existing ones
   102 'not' etc.) or e.g. convert a map to another one of different Value type.
   105 'not' etc.) or e.g. convert a map to another one of different Value type.
   103
   106
   104 The typical usage of this classes is passing implicit maps to
   107 The typical usage of this classes is passing implicit maps to
   105 algorithms.  If a function type algorithm is called then the function
   108 algorithms.  If a function type algorithm is called then the function
   106 type map adaptors can be used comfortable. For example let's see the
   109 type map adaptors can be used comfortable. For example let's see the
   107 usage of map adaptors with the \c digraphToEps() function.
   110 usage of map adaptors with the \c graphToEps() function.
   108 \code
   111 \code
   109   Color nodeColor(int deg) {
   112   Color nodeColor(int deg) {
   110     if (deg >= 2) {
   113     if (deg >= 2) {
   111       return Color(0.5, 0.0, 0.5);
   114       return Color(0.5, 0.0, 0.5);
   112     } else if (deg == 1) {
   115     } else if (deg == 1) {
   116     }
   119     }
   117   }
   120   }
   118
   121
   119   Digraph::NodeMap<int> degree_map(graph);
   122   Digraph::NodeMap<int> degree_map(graph);
   120
   123
   121   digraphToEps(graph, "graph.eps")
   124   graphToEps(graph, "graph.eps")
   122     .coords(coords).scaleToA4().undirected()
   125     .coords(coords).scaleToA4().undirected()
   123     .nodeColors(composeMap(functorToMap(nodeColor), degree_map))
   126     .nodeColors(composeMap(functorToMap(nodeColor), degree_map))
   124     .run();
   127     .run();
   125 \endcode
   128 \endcode
   126 The \c functorToMap() function makes an \c int to \c Color map from the
   129 The \c functorToMap() function makes an \c int to \c Color map from the
   127 \e nodeColor() function. The \c composeMap() compose the \e degree_map
   130 \c nodeColor() function. The \c composeMap() compose the \c degree_map
   128 and the previously created map. The composed map is a proper function to
   131 and the previously created map. The composed map is a proper function to
   129 get the color of each node.
   132 get the color of each node.
   130
   133
   131 The usage with class type algorithms is little bit harder. In this
   134 The usage with class type algorithms is little bit harder. In this
   132 case the function type map adaptors can not be used, because the
   135 case the function type map adaptors can not be used, because the
   171 assignment operators and copy constructors. This makes it easy and
   174 assignment operators and copy constructors. This makes it easy and
   172 efficient to have e.g. the Dijkstra algorithm to store its result in
   175 efficient to have e.g. the Dijkstra algorithm to store its result in
   173 any kind of path structure.
   176 any kind of path structure.
   174
   177
   175 \sa lemon::concepts::Path
   178 \sa lemon::concepts::Path
   177 */
   179 */
   178
   180
   179 /**
   181 /**
   180 @defgroup auxdat Auxiliary Data Structures
   182 @defgroup auxdat Auxiliary Data Structures
   181 @ingroup datas
   183 @ingroup datas
   183
   185
   184 This group describes some data structures implemented in LEMON in
   186 This group describes some data structures implemented in LEMON in
   185 order to make it easier to implement combinatorial algorithms.
   187 order to make it easier to implement combinatorial algorithms.
   186 */
   188 */
   187
   189
   189 /**
   190 /**
   190 @defgroup algs Algorithms
   191 @defgroup algs Algorithms
   191 \brief This group describes the several algorithms
   192 \brief This group describes the several algorithms
   192 implemented in LEMON.
   193 implemented in LEMON.
   193
   194
   199 @defgroup search Graph Search
   200 @defgroup search Graph Search
   200 @ingroup algs
   201 @ingroup algs
   201 \brief Common graph search algorithms.
   202 \brief Common graph search algorithms.
   202
   203
   203 This group describes the common graph search algorithms like
   204 This group describes the common graph search algorithms like
   204 Breadth-first search (Bfs) and Depth-first search (Dfs).
   205 Breadth-First Search (BFS) and Depth-First Search (DFS).
   205 */
   206 */
   206
   207
   207 /**
   208 /**
   208 @defgroup shortest_path Shortest Path algorithms
   209 @defgroup shortest_path Shortest Path Algorithms
   209 @ingroup algs
   210 @ingroup algs
   210 \brief Algorithms for finding shortest paths.
   211 \brief Algorithms for finding shortest paths.
   211
   212
   212 This group describes the algorithms for finding shortest paths in graphs.
   213 This group describes the algorithms for finding shortest paths in graphs.
   213 */
   214 */
   214
   215
   215 /**
   216 /**
   216 @defgroup max_flow Maximum Flow algorithms
   217 @defgroup max_flow Maximum Flow Algorithms
   217 @ingroup algs
   218 @ingroup algs
   218 \brief Algorithms for finding maximum flows.
   219 \brief Algorithms for finding maximum flows.
   219
   220
   220 This group describes the algorithms for finding maximum flows and
   221 This group describes the algorithms for finding maximum flows and
   221 feasible circulations.
   222 feasible circulations.
   239
   240
   240 In most cases the \ref lemon::Preflow "Preflow" algorithm provides the
   241 In most cases the \ref lemon::Preflow "Preflow" algorithm provides the
   241 fastest method to compute the maximum flow. All impelementations
   242 fastest method to compute the maximum flow. All impelementations
   242 provides functions to query the minimum cut, which is the dual linear
   243 provides functions to query the minimum cut, which is the dual linear
   243 programming problem of the maximum flow.
   244 programming problem of the maximum flow.
   244
   245 */
   245 */
   246
   246
   247 /**
   247 /**
   248 @defgroup min_cost_flow Minimum Cost Flow Algorithms
   248 @defgroup min_cost_flow Minimum Cost Flow algorithms

   249 @ingroup algs
   249 @ingroup algs
   250
   250
   251 \brief Algorithms for finding minimum cost flows and circulations.
   251 \brief Algorithms for finding minimum cost flows and circulations.
   252
   252
   253 This group describes the algorithms for finding minimum cost flows and
   253 This group describes the algorithms for finding minimum cost flows and
   254 circulations.
   254 circulations.
   255 */
   255 */
   256
   256
   257 /**
   257 /**
   258 @defgroup min_cut Minimum Cut algorithms
   258 @defgroup min_cut Minimum Cut Algorithms
   259 @ingroup algs
   259 @ingroup algs
   260
   260
   261 \brief Algorithms for finding minimum cut in graphs.
   261 \brief Algorithms for finding minimum cut in graphs.
   262
   262
   263 This group describes the algorithms for finding minimum cut in graphs.
   263 This group describes the algorithms for finding minimum cut in graphs.
   280 - \ref lemon::GomoryHuTree "Gomory-Hu tree computation" to calculate all
   280 - \ref lemon::GomoryHuTree "Gomory-Hu tree computation" to calculate all
   281   pairs minimum cut in undirected graphs
   281   pairs minimum cut in undirected graphs
   282
   282
   283 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,
   284 please see the \ref max_flow "Maximum Flow page".
   284 please see the \ref max_flow "Maximum Flow page".
   285
   285 */
   286 */
   286
   287
   287 /**
   288 /**
   288 @defgroup graph_prop Connectivity and Other Graph Properties
   289 @defgroup graph_prop Connectivity and other graph properties

   290 @ingroup algs
   289 @ingroup algs
   291 \brief Algorithms for discovering the graph properties
   290 \brief Algorithms for discovering the graph properties
   292
   291
   293 This group describes the algorithms for discovering the graph properties
   292 This group describes the algorithms for discovering the graph properties
   294 like connectivity, bipartiteness, euler property, simplicity etc.
   293 like connectivity, bipartiteness, euler property, simplicity etc.
   296 \image html edge_biconnected_components.png
   295 \image html edge_biconnected_components.png
   297 \image latex edge_biconnected_components.eps "bi-edge-connected components" width=\textwidth
   296 \image latex edge_biconnected_components.eps "bi-edge-connected components" width=\textwidth
   298 */
   297 */
   299
   298
   300 /**
   299 /**
   301 @defgroup planar Planarity embedding and drawing
   300 @defgroup planar Planarity Embedding and Drawing
   302 @ingroup algs
   301 @ingroup algs
   303 \brief Algorithms for planarity checking, embedding and drawing
   302 \brief Algorithms for planarity checking, embedding and drawing
   304
   303
   305 This group describes the algorithms for planarity checking,
   304 This group describes the algorithms for planarity checking,
   306 embedding and drawing.
   305 embedding and drawing.
   308 \image html planar.png
   307 \image html planar.png
   309 \image latex planar.eps "Plane graph" width=\textwidth
   308 \image latex planar.eps "Plane graph" width=\textwidth
   310 */
   309 */
   311
   310
   312 /**
   311 /**
   313 @defgroup matching Matching algorithms
   312 @defgroup matching Matching Algorithms
   314 @ingroup algs
   313 @ingroup algs
   315 \brief Algorithms for finding matchings in graphs and bipartite graphs.
   314 \brief Algorithms for finding matchings in graphs and bipartite graphs.
   316
   315
   317 This group contains algorithm objects and functions to calculate
   316 This group contains algorithm objects and functions to calculate
   318 matchings in graphs and bipartite graphs. The general matching problem is
   317 matchings in graphs and bipartite graphs. The general matching problem is
   346   Edmond's blossom shrinking algorithm for calculate maximum weighted
   345   Edmond's blossom shrinking algorithm for calculate maximum weighted
   347   perfect matching in general graph
   346   perfect matching in general graph
   348
   347
   349 \image html bipartite_matching.png
   348 \image html bipartite_matching.png
   350 \image latex bipartite_matching.eps "Bipartite Matching" width=\textwidth
   349 \image latex bipartite_matching.eps "Bipartite Matching" width=\textwidth
   351
   350 */
   352 */
   351
   353
   352 /**
   354 /**
   353 @defgroup spantree Minimum Spanning Tree Algorithms
   355 @defgroup spantree Minimum Spanning Tree algorithms

   356 @ingroup algs
   354 @ingroup algs
   357 \brief Algorithms for finding a minimum cost spanning tree in a graph.
   355 \brief Algorithms for finding a minimum cost spanning tree in a graph.
   358
   356
   359 This group describes the algorithms for finding a minimum cost spanning
   357 This group describes the algorithms for finding a minimum cost spanning
   360 tree in a graph
   358 tree in a graph
   361 */
   359 */
   362
   360
   363
   361 /**
   364 /**
   362 @defgroup auxalg Auxiliary Algorithms
   365 @defgroup auxalg Auxiliary algorithms

   366 @ingroup algs
   363 @ingroup algs
   367 \brief Auxiliary algorithms implemented in LEMON.
   364 \brief Auxiliary algorithms implemented in LEMON.
   368
   365
   369 This group describes some algorithms implemented in LEMON
   366 This group describes some algorithms implemented in LEMON
   370 in order to make it easier to implement complex algorithms.
   367 in order to make it easier to implement complex algorithms.
   371 */
   368 */
   372
   369
   373 /**
   370 /**
   374 @defgroup approx Approximation algorithms
   371 @defgroup approx Approximation Algorithms

   372 @ingroup algs
   375 \brief Approximation algorithms.
   373 \brief Approximation algorithms.
   376
   374
   377 This group describes the approximation and heuristic algorithms
   375 This group describes the approximation and heuristic algorithms
   378 implemented in LEMON.
   376 implemented in LEMON.
   379 */
   377 */
   383 \brief This group describes some general optimization frameworks
   381 \brief This group describes some general optimization frameworks
   384 implemented in LEMON.
   382 implemented in LEMON.
   385
   383
   386 This group describes some general optimization frameworks
   384 This group describes some general optimization frameworks
   387 implemented in LEMON.
   385 implemented in LEMON.
   388
   386 */
   389 */
   387
   390
   388 /**
   391 /**
   389 @defgroup lp_group Lp and Mip Solvers
   392 @defgroup lp_group Lp and Mip solvers

   393 @ingroup gen_opt_group
   390 @ingroup gen_opt_group
   394 \brief Lp and Mip solver interfaces for LEMON.
   391 \brief Lp and Mip solver interfaces for LEMON.
   395
   392
   396 This group describes Lp and Mip solver interfaces for LEMON. The
   393 This group describes Lp and Mip solver interfaces for LEMON. The
   397 various LP solvers could be used in the same manner with this
   394 various LP solvers could be used in the same manner with this
   398 interface.
   395 interface.
   399
   396 */
   400 */
   397
   401
   398 /**
   402 /**
   399 @defgroup lp_utils Tools for Lp and Mip Solvers
   403 @defgroup lp_utils Tools for Lp and Mip solvers

   404 @ingroup lp_group
   400 @ingroup lp_group
   405 \brief Helper tools to the Lp and Mip solvers.
   401 \brief Helper tools to the Lp and Mip solvers.
   406
   402
   407 This group adds some helper tools to general optimization framework
   403 This group adds some helper tools to general optimization framework
   408 implemented in LEMON.
   404 implemented in LEMON.
   439 This group describes several useful tools for development,
   435 This group describes several useful tools for development,
   440 debugging and testing.
   436 debugging and testing.
   441 */
   437 */
   442
   438
   443 /**
   439 /**
   444 @defgroup timecount Time measuring and Counting
   440 @defgroup timecount Time Measuring and Counting
   445 @ingroup misc
   441 @ingroup misc
   446 \brief Simple tools for measuring the performance of algorithms.
   442 \brief Simple tools for measuring the performance of algorithms.
   447
   443
   448 This group describes simple tools for measuring the performance
   444 This group describes simple tools for measuring the performance
   449 of algorithms.
   445 of algorithms.
   459 */
   446 */
   460
   447
   461 /**
   448 /**
   462 @defgroup exceptions Exceptions
   449 @defgroup exceptions Exceptions
   463 @ingroup utils
   450 @ingroup utils
   469 /**
   456 /**
   470 @defgroup io_group Input-Output
   457 @defgroup io_group Input-Output
   471 \brief Graph Input-Output methods
   458 \brief Graph Input-Output methods
   472
   459
   473 This group describes the tools for importing and exporting graphs
   460 This group describes the tools for importing and exporting graphs
   474 and graph related data. Now it supports the LEMON format, the
   461 and graph related data. Now it supports the \ref lgf-format
   475 \c DIMACS format and the encapsulated postscript (EPS) format.
   462 "LEMON Graph Format", the \c DIMACS format and the encapsulated

   463 postscript (EPS) format.
   476 */
   464 */
   477
   465
   478 /**
   466 /**
   479 @defgroup lemon_io LEMON Input-Output
   467 @defgroup lemon_io LEMON Input-Output
   480 @ingroup io_group
   468 @ingroup io_group
   481 \brief Reading and writing \ref lgf-format "LEMON Graph Format".
   469 \brief Reading and writing LEMON Graph Format.
   482
   470
   483 This group describes methods for reading and writing
   471 This group describes methods for reading and writing
   484 \ref lgf-format "LEMON Graph Format".
   472 \ref lgf-format "LEMON Graph Format".
   485 */
   473 */
   486
   474
   487 /**
   475 /**
   488 @defgroup eps_io Postscript exporting
   476 @defgroup eps_io Postscript Exporting
   489 @ingroup io_group
   477 @ingroup io_group
   490 \brief General \c EPS drawer and graph exporter
   478 \brief General \c EPS drawer and graph exporter
   491
   479
   492 This group describes general \c EPS drawing methods and special
   480 This group describes general \c EPS drawing methods and special
   493 graph exporting tools.
   481 graph exporting tools.
   494 */
   482 */
   496
   483
   497 /**
   484 /**
   498 @defgroup concept Concepts
   485 @defgroup concept Concepts
   499 \brief Skeleton classes and concept checking classes
   486 \brief Skeleton classes and concept checking classes
   500
   487
   519 - The concept descriptor classes also provide a <em>checker class</em>
   506 - The concept descriptor classes also provide a <em>checker class</em>
   520   that makes it possible to check whether a certain implementation of a
   507   that makes it possible to check whether a certain implementation of a
   521   concept indeed provides all the required features.
   508   concept indeed provides all the required features.
   522
   509
   523 - Finally, They can serve as a skeleton of a new implementation of a concept.
   510 - Finally, They can serve as a skeleton of a new implementation of a concept.
   524
   511 */
   525 */

   526

   527
   512
   528 /**
   513 /**
   529 @defgroup graph_concepts Graph Structure Concepts
   514 @defgroup graph_concepts Graph Structure Concepts
   530 @ingroup concept
   515 @ingroup concept
   531 \brief Skeleton and concept checking classes for graph structures
   516 \brief Skeleton and concept checking classes for graph structures
   532
   517
   533 This group describes the skeletons and concept checking classes of LEMON's
   518 This group describes the skeletons and concept checking classes of LEMON's
   534 graph structures and helper classes used to implement these.
   519 graph structures and helper classes used to implement these.
   535 */
   520 */
   536
   521
   537 /* --- Unused group
   522 /**
   538 @defgroup experimental Experimental Structures and Algorithms
   523 @defgroup map_concepts Map Concepts
   539 This group describes some Experimental structures and algorithms.
   524 @ingroup concept
   540 The stuff here is subject to change.
   525 \brief Skeleton and concept checking classes for maps

   526

   527 This group describes the skeletons and concept checking classes of maps.
   541 */
   528 */
   542
   529
   543 /**
   530 /**
   544 \anchor demoprograms
   531 \anchor demoprograms
   545
   532