doc/groups.dox
changeset 754 2de0fc630899
parent 735 853fcddcf282
parent 715 ece80147fb08
child 755 134852d7fb0a
equal deleted inserted replaced
34:ed61b4178786 35:ac0ff3b0658b
   224 class. We use the implicit minimum time map as the length map of the
   224 class. We use the implicit minimum time map as the length map of the
   225 \c Dijkstra algorithm.
   225 \c Dijkstra algorithm.
   226 */
   226 */
   227 
   227 
   228 /**
   228 /**
   229 @defgroup matrices Matrices
       
   230 @ingroup datas
       
   231 \brief Two dimensional data storages implemented in LEMON.
       
   232 
       
   233 This group contains two dimensional data storages implemented in LEMON.
       
   234 */
       
   235 
       
   236 /**
       
   237 @defgroup paths Path Structures
   229 @defgroup paths Path Structures
   238 @ingroup datas
   230 @ingroup datas
   239 \brief %Path structures implemented in LEMON.
   231 \brief %Path structures implemented in LEMON.
   240 
   232 
   241 This group contains the path structures implemented in LEMON.
   233 This group contains the path structures implemented in LEMON.
   244 All of them have similar interfaces and they can be copied easily with
   236 All of them have similar interfaces and they can be copied easily with
   245 assignment operators and copy constructors. This makes it easy and
   237 assignment operators and copy constructors. This makes it easy and
   246 efficient to have e.g. the Dijkstra algorithm to store its result in
   238 efficient to have e.g. the Dijkstra algorithm to store its result in
   247 any kind of path structure.
   239 any kind of path structure.
   248 
   240 
   249 \sa lemon::concepts::Path
   241 \sa \ref concepts::Path "Path concept"
       
   242 */
       
   243 
       
   244 /**
       
   245 @defgroup heaps Heap Structures
       
   246 @ingroup datas
       
   247 \brief %Heap structures implemented in LEMON.
       
   248 
       
   249 This group contains the heap structures implemented in LEMON.
       
   250 
       
   251 LEMON provides several heap classes. They are efficient implementations
       
   252 of the abstract data type \e priority \e queue. They store items with
       
   253 specified values called \e priorities in such a way that finding and
       
   254 removing the item with minimum priority are efficient.
       
   255 The basic operations are adding and erasing items, changing the priority
       
   256 of an item, etc.
       
   257 
       
   258 Heaps are crucial in several algorithms, such as Dijkstra and Prim.
       
   259 The heap implementations have the same interface, thus any of them can be
       
   260 used easily in such algorithms.
       
   261 
       
   262 \sa \ref concepts::Heap "Heap concept"
       
   263 */
       
   264 
       
   265 /**
       
   266 @defgroup matrices Matrices
       
   267 @ingroup datas
       
   268 \brief Two dimensional data storages implemented in LEMON.
       
   269 
       
   270 This group contains two dimensional data storages implemented in LEMON.
   250 */
   271 */
   251 
   272 
   252 /**
   273 /**
   253 @defgroup auxdat Auxiliary Data Structures
   274 @defgroup auxdat Auxiliary Data Structures
   254 @ingroup datas
   275 @ingroup datas
   255 \brief Auxiliary data structures implemented in LEMON.
   276 \brief Auxiliary data structures implemented in LEMON.
   256 
   277 
   257 This group contains some data structures implemented in LEMON in
   278 This group contains some data structures implemented in LEMON in
   258 order to make it easier to implement combinatorial algorithms.
   279 order to make it easier to implement combinatorial algorithms.
       
   280 */
       
   281 
       
   282 /**
       
   283 @defgroup geomdat Geometric Data Structures
       
   284 @ingroup auxdat
       
   285 \brief Geometric data structures implemented in LEMON.
       
   286 
       
   287 This group contains geometric data structures implemented in LEMON.
       
   288 
       
   289  - \ref lemon::dim2::Point "dim2::Point" implements a two dimensional
       
   290    vector with the usual operations.
       
   291  - \ref lemon::dim2::Box "dim2::Box" can be used to determine the
       
   292    rectangular bounding box of a set of \ref lemon::dim2::Point
       
   293    "dim2::Point"'s.
       
   294 */
       
   295 
       
   296 /**
       
   297 @defgroup matrices Matrices
       
   298 @ingroup auxdat
       
   299 \brief Two dimensional data storages implemented in LEMON.
       
   300 
       
   301 This group contains two dimensional data storages implemented in LEMON.
   259 */
   302 */
   260 
   303 
   261 /**
   304 /**
   262 @defgroup algs Algorithms
   305 @defgroup algs Algorithms
   263 \brief This group contains the several algorithms
   306 \brief This group contains the several algorithms
   296  - \ref Suurballe A successive shortest path algorithm for finding
   339  - \ref Suurballe A successive shortest path algorithm for finding
   297    arc-disjoint paths between two nodes having minimum total length.
   340    arc-disjoint paths between two nodes having minimum total length.
   298 */
   341 */
   299 
   342 
   300 /**
   343 /**
       
   344 @defgroup spantree Minimum Spanning Tree Algorithms
       
   345 @ingroup algs
       
   346 \brief Algorithms for finding minimum cost spanning trees and arborescences.
       
   347 
       
   348 This group contains the algorithms for finding minimum cost spanning
       
   349 trees and arborescences.
       
   350 */
       
   351 
       
   352 /**
   301 @defgroup max_flow Maximum Flow Algorithms
   353 @defgroup max_flow Maximum Flow Algorithms
   302 @ingroup algs
   354 @ingroup algs
   303 \brief Algorithms for finding maximum flows.
   355 \brief Algorithms for finding maximum flows.
   304 
   356 
   305 This group contains the algorithms for finding maximum flows and
   357 This group contains the algorithms for finding maximum flows and
   373 outgoing arcs. Formally, there is a \f$G=(V,A)\f$ digraph, a
   425 outgoing arcs. Formally, there is a \f$G=(V,A)\f$ digraph, a
   374 \f$cap: A\rightarrow\mathbf{R}^+_0\f$ capacity function. The minimum
   426 \f$cap: A\rightarrow\mathbf{R}^+_0\f$ capacity function. The minimum
   375 cut is the \f$X\f$ solution of the next optimization problem:
   427 cut is the \f$X\f$ solution of the next optimization problem:
   376 
   428 
   377 \f[ \min_{X \subset V, X\not\in \{\emptyset, V\}}
   429 \f[ \min_{X \subset V, X\not\in \{\emptyset, V\}}
   378     \sum_{uv\in A, u\in X, v\not\in X}cap(uv) \f]
   430     \sum_{uv\in A: u\in X, v\not\in X}cap(uv) \f]
   379 
   431 
   380 LEMON contains several algorithms related to minimum cut problems:
   432 LEMON contains several algorithms related to minimum cut problems:
   381 
   433 
   382 - \ref HaoOrlin "Hao-Orlin algorithm" for calculating minimum cut
   434 - \ref HaoOrlin "Hao-Orlin algorithm" for calculating minimum cut
   383   in directed graphs.
   435   in directed graphs.
   386 - \ref GomoryHu "Gomory-Hu tree computation" for calculating
   438 - \ref GomoryHu "Gomory-Hu tree computation" for calculating
   387   all-pairs minimum cut in undirected graphs.
   439   all-pairs minimum cut in undirected graphs.
   388 
   440 
   389 If you want to find minimum cut just between two distinict nodes,
   441 If you want to find minimum cut just between two distinict nodes,
   390 see the \ref max_flow "maximum flow problem".
   442 see the \ref max_flow "maximum flow problem".
   391 */
       
   392 
       
   393 /**
       
   394 @defgroup graph_properties Connectivity and Other Graph Properties
       
   395 @ingroup algs
       
   396 \brief Algorithms for discovering the graph properties
       
   397 
       
   398 This group contains the algorithms for discovering the graph properties
       
   399 like connectivity, bipartiteness, euler property, simplicity etc.
       
   400 
       
   401 \image html edge_biconnected_components.png
       
   402 \image latex edge_biconnected_components.eps "bi-edge-connected components" width=\textwidth
       
   403 */
       
   404 
       
   405 /**
       
   406 @defgroup planar Planarity Embedding and Drawing
       
   407 @ingroup algs
       
   408 \brief Algorithms for planarity checking, embedding and drawing
       
   409 
       
   410 This group contains the algorithms for planarity checking,
       
   411 embedding and drawing.
       
   412 
       
   413 \image html planar.png
       
   414 \image latex planar.eps "Plane graph" width=\textwidth
       
   415 */
   443 */
   416 
   444 
   417 /**
   445 /**
   418 @defgroup matching Matching Algorithms
   446 @defgroup matching Matching Algorithms
   419 @ingroup algs
   447 @ingroup algs
   453 \image html bipartite_matching.png
   481 \image html bipartite_matching.png
   454 \image latex bipartite_matching.eps "Bipartite Matching" width=\textwidth
   482 \image latex bipartite_matching.eps "Bipartite Matching" width=\textwidth
   455 */
   483 */
   456 
   484 
   457 /**
   485 /**
   458 @defgroup spantree Minimum Spanning Tree Algorithms
   486 @defgroup graph_properties Connectivity and Other Graph Properties
   459 @ingroup algs
   487 @ingroup algs
   460 \brief Algorithms for finding minimum cost spanning trees and arborescences.
   488 \brief Algorithms for discovering the graph properties
   461 
   489 
   462 This group contains the algorithms for finding minimum cost spanning
   490 This group contains the algorithms for discovering the graph properties
   463 trees and arborescences.
   491 like connectivity, bipartiteness, euler property, simplicity etc.
       
   492 
       
   493 \image html connected_components.png
       
   494 \image latex connected_components.eps "Connected components" width=\textwidth
       
   495 */
       
   496 
       
   497 /**
       
   498 @defgroup planar Planarity Embedding and Drawing
       
   499 @ingroup algs
       
   500 \brief Algorithms for planarity checking, embedding and drawing
       
   501 
       
   502 This group contains the algorithms for planarity checking,
       
   503 embedding and drawing.
       
   504 
       
   505 \image html planar.png
       
   506 \image latex planar.eps "Plane graph" width=\textwidth
       
   507 */
       
   508 
       
   509 /**
       
   510 @defgroup approx Approximation Algorithms
       
   511 @ingroup algs
       
   512 \brief Approximation algorithms.
       
   513 
       
   514 This group contains the approximation and heuristic algorithms
       
   515 implemented in LEMON.
   464 */
   516 */
   465 
   517 
   466 /**
   518 /**
   467 @defgroup auxalg Auxiliary Algorithms
   519 @defgroup auxalg Auxiliary Algorithms
   468 @ingroup algs
   520 @ingroup algs
   469 \brief Auxiliary algorithms implemented in LEMON.
   521 \brief Auxiliary algorithms implemented in LEMON.
   470 
   522 
   471 This group contains some algorithms implemented in LEMON
   523 This group contains some algorithms implemented in LEMON
   472 in order to make it easier to implement complex algorithms.
   524 in order to make it easier to implement complex algorithms.
   473 */
       
   474 
       
   475 /**
       
   476 @defgroup approx Approximation Algorithms
       
   477 @ingroup algs
       
   478 \brief Approximation algorithms.
       
   479 
       
   480 This group contains the approximation and heuristic algorithms
       
   481 implemented in LEMON.
       
   482 */
   525 */
   483 
   526 
   484 /**
   527 /**
   485 @defgroup gen_opt_group General Optimization Tools
   528 @defgroup gen_opt_group General Optimization Tools
   486 \brief This group contains some general optimization frameworks
   529 \brief This group contains some general optimization frameworks
   585 This group contains general \c EPS drawing methods and special
   628 This group contains general \c EPS drawing methods and special
   586 graph exporting tools.
   629 graph exporting tools.
   587 */
   630 */
   588 
   631 
   589 /**
   632 /**
   590 @defgroup dimacs_group DIMACS format
   633 @defgroup dimacs_group DIMACS Format
   591 @ingroup io_group
   634 @ingroup io_group
   592 \brief Read and write files in DIMACS format
   635 \brief Read and write files in DIMACS format
   593 
   636 
   594 Tools to read a digraph from or write it to a file in DIMACS format data.
   637 Tools to read a digraph from or write it to a file in DIMACS format data.
   595 */
   638 */
   647 
   690 
   648 This group contains the skeletons and concept checking classes of maps.
   691 This group contains the skeletons and concept checking classes of maps.
   649 */
   692 */
   650 
   693 
   651 /**
   694 /**
       
   695 @defgroup tools Standalone Utility Applications
       
   696 
       
   697 Some utility applications are listed here.
       
   698 
       
   699 The standard compilation procedure (<tt>./configure;make</tt>) will compile
       
   700 them, as well.
       
   701 */
       
   702 
       
   703 /**
   652 \anchor demoprograms
   704 \anchor demoprograms
   653 
   705 
   654 @defgroup demos Demo Programs
   706 @defgroup demos Demo Programs
   655 
   707 
   656 Some demo programs are listed here. Their full source codes can be found in
   708 Some demo programs are listed here. Their full source codes can be found in
   658 
   710 
   659 In order to compile them, use the <tt>make demo</tt> or the
   711 In order to compile them, use the <tt>make demo</tt> or the
   660 <tt>make check</tt> commands.
   712 <tt>make check</tt> commands.
   661 */
   713 */
   662 
   714 
   663 /**
       
   664 @defgroup tools Standalone Utility Applications
       
   665 
       
   666 Some utility applications are listed here.
       
   667 
       
   668 The standard compilation procedure (<tt>./configure;make</tt>) will compile
       
   669 them, as well.
       
   670 */
       
   671 
       
   672 }
   715 }