doc/groups.dox
changeset 314 2cc60866a0c9
parent 236 da953e387d31
child 318 1e2d6ca80793
equal deleted 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 */
    89 
       
    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
   176 
       
   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 
   188 
       
   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.
   450 */
       
   451 
       
   452 /**
       
   453 @defgroup graphbits Tools for Graph Implementation
       
   454 @ingroup utils
       
   455 \brief Tools to make it easier to create graphs.
       
   456 
       
   457 This group describes the tools that makes it easier to create graphs and
       
   458 the maps that dynamically update with the graph changes.
       
   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 */
   495 
       
   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