Changeset 817:432c54cec63c in lemon for doc/groups.dox
 Timestamp:
 11/05/09 08:39:49 (10 years ago)
 Branch:
 default
 Parents:
 816:e746fb14e680 (diff), 804:9fbbd802020f (diff)
Note: this is a merge changeset, the changes displayed below correspond to the merge itself.
Use the (diff) links above to see all the changes relative to each parent.  Phase:
 public
 Files:

 2 edited
Legend:
 Unmodified
 Added
 Removed

doc/groups.dox
r802 r817 454 454 455 455 /** 456 @defgroup min_mean_cycle Minimum Mean Cycle Algorithms 457 @ingroup algs 458 \brief Algorithms for finding minimum mean cycles. 459 460 This group contains the algorithms for finding minimum mean cycles. 461 462 The \e minimum \e mean \e cycle \e problem is to find a directed cycle 463 of minimum mean length (cost) in a digraph. 464 The mean length of a cycle is the average length of its arcs, i.e. the 465 ratio between the total length of the cycle and the number of arcs on it. 466 467 This problem has an important connection to \e conservative \e length 468 \e functions, too. A length function on the arcs of a digraph is called 469 conservative if and only if there is no directed cycle of negative total 470 length. For an arbitrary length function, the negative of the minimum 471 cycle mean is the smallest \f$\epsilon\f$ value so that increasing the 472 arc lengths uniformly by \f$\epsilon\f$ results in a conservative length 473 function. 474 475 LEMON contains three algorithms for solving the minimum mean cycle problem: 476  \ref Karp "Karp"'s original algorithm. 477  \ref HartmannOrlin "HartmannOrlin"'s algorithm, which is an improved 478 version of Karp's algorithm. 479  \ref Howard "Howard"'s policy iteration algorithm. 480 481 In practice, the Howard algorithm proved to be by far the most efficient 482 one, though the best known theoretical bound on its running time is 483 exponential. 484 Both Karp and HartmannOrlin algorithms run in time O(ne) and use space 485 O(n<sup>2</sup>+e), but the latter one is typically faster due to the 486 applied early termination scheme. 487 */ 488 489 /** 456 490 @defgroup matching Matching Algorithms 457 491 @ingroup algs 
doc/groups.dox
r815 r817 227 227 228 228 /** 229 @defgroup matrices Matrices230 @ingroup datas231 \brief Two dimensional data storages implemented in LEMON.232 233 This group contains two dimensional data storages implemented in LEMON.234 */235 236 /**237 229 @defgroup paths Path Structures 238 230 @ingroup datas … … 247 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 … … 260 281 261 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. 302 */ 303 304 /** 262 305 @defgroup algs Algorithms 263 306 \brief This group contains the several algorithms … … 274 317 275 318 This group contains the common graph search algorithms, namely 276 \e breadthfirst \e search (BFS) and \e depthfirst \e search (DFS). 319 \e breadthfirst \e search (BFS) and \e depthfirst \e search (DFS) 320 \ref clrs01algorithms. 277 321 */ 278 322 … … 282 326 \brief Algorithms for finding shortest paths. 283 327 284 This group contains the algorithms for finding shortest paths in digraphs. 328 This group contains the algorithms for finding shortest paths in digraphs 329 \ref clrs01algorithms. 285 330 286 331  \ref Dijkstra algorithm for finding shortest paths from a source node … … 299 344 300 345 /** 346 @defgroup spantree Minimum Spanning Tree Algorithms 347 @ingroup algs 348 \brief Algorithms for finding minimum cost spanning trees and arborescences. 349 350 This group contains the algorithms for finding minimum cost spanning 351 trees and arborescences \ref clrs01algorithms. 352 */ 353 354 /** 301 355 @defgroup max_flow Maximum Flow Algorithms 302 356 @ingroup algs … … 304 358 305 359 This group contains the algorithms for finding maximum flows and 306 feasible circulations .360 feasible circulations \ref clrs01algorithms, \ref amo93networkflows. 307 361 308 362 The \e maximum \e flow \e problem is to find a flow of maximum value between … … 319 373 320 374 LEMON contains several algorithms for solving maximum flow problems: 321  \ref EdmondsKarp EdmondsKarp algorithm. 322  \ref Preflow GoldbergTarjan's preflow pushrelabel algorithm. 323  \ref DinitzSleatorTarjan Dinitz's blocking flow algorithm with dynamic trees. 324  \ref GoldbergTarjan Preflow pushrelabel algorithm with dynamic trees. 325 326 In most cases the \ref Preflow "Preflow" algorithm provides the 375  \ref EdmondsKarp EdmondsKarp algorithm 376 \ref edmondskarp72theoretical. 377  \ref Preflow GoldbergTarjan's preflow pushrelabel algorithm 378 \ref goldberg88newapproach. 379  \ref DinitzSleatorTarjan Dinitz's blocking flow algorithm with dynamic trees 380 \ref dinic70algorithm, \ref sleator83dynamic. 381  \ref GoldbergTarjan !Preflow pushrelabel algorithm with dynamic trees 382 \ref goldberg88newapproach, \ref sleator83dynamic. 383 384 In most cases the \ref Preflow algorithm provides the 327 385 fastest method for computing a maximum flow. All implementations 328 386 also provide functions to query the minimum cut, which is the dual … … 342 400 343 401 This group contains the algorithms for finding minimum cost flows and 344 circulations. For more information about this problem and its dual 345 solution see \ref min_cost_flow "Minimum Cost Flow Problem". 402 circulations \ref amo93networkflows. For more information about this 403 problem and its dual solution, see \ref min_cost_flow 404 "Minimum Cost Flow Problem". 346 405 347 406 LEMON contains several algorithms for this problem. 348 407  \ref NetworkSimplex Primal Network Simplex algorithm with various 349 pivot strategies .408 pivot strategies \ref dantzig63linearprog, \ref kellyoneill91netsimplex. 350 409  \ref CostScaling PushRelabel and AugmentRelabel algorithms based on 351 cost scaling. 410 cost scaling \ref goldberg90approximation, \ref goldberg97efficient, 411 \ref bunnagel98efficient. 352 412  \ref CapacityScaling Successive Shortest %Path algorithm with optional 353 capacity scaling. 354  \ref CancelAndTighten The Cancel and Tighten algorithm. 355  \ref CycleCanceling CycleCanceling algorithms. 413 capacity scaling \ref edmondskarp72theoretical. 414  \ref CancelAndTighten The Cancel and Tighten algorithm 415 \ref goldberg89cyclecanceling. 416  \ref CycleCanceling CycleCanceling algorithms 417 \ref klein67primal, \ref goldberg89cyclecanceling. 356 418 357 419 In general NetworkSimplex is the most efficient implementation, … … 376 438 377 439 \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]440 \sum_{uv\in A: u\in X, v\not\in X}cap(uv) \f] 379 441 380 442 LEMON contains several algorithms related to minimum cut problems: … … 423 485 O(n<sup>2</sup>+e), but the latter one is typically faster due to the 424 486 applied early termination scheme. 425 */426 427 /**428 @defgroup graph_properties Connectivity and Other Graph Properties429 @ingroup algs430 \brief Algorithms for discovering the graph properties431 432 This group contains the algorithms for discovering the graph properties433 like connectivity, bipartiteness, euler property, simplicity etc.434 435 \image html edge_biconnected_components.png436 \image latex edge_biconnected_components.eps "biedgeconnected components" width=\textwidth437 */438 439 /**440 @defgroup planar Planarity Embedding and Drawing441 @ingroup algs442 \brief Algorithms for planarity checking, embedding and drawing443 444 This group contains the algorithms for planarity checking,445 embedding and drawing.446 447 \image html planar.png448 \image latex planar.eps "Plane graph" width=\textwidth449 487 */ 450 488 … … 490 528 491 529 /** 492 @defgroup spantree Minimum Spanning Tree Algorithms 493 @ingroup algs 494 \brief Algorithms for finding minimum cost spanning trees and arborescences. 495 496 This group contains the algorithms for finding minimum cost spanning 497 trees and arborescences. 530 @defgroup graph_properties Connectivity and Other Graph Properties 531 @ingroup algs 532 \brief Algorithms for discovering the graph properties 533 534 This group contains the algorithms for discovering the graph properties 535 like connectivity, bipartiteness, euler property, simplicity etc. 536 537 \image html connected_components.png 538 \image latex connected_components.eps "Connected components" width=\textwidth 539 */ 540 541 /** 542 @defgroup planar Planarity Embedding and Drawing 543 @ingroup algs 544 \brief Algorithms for planarity checking, embedding and drawing 545 546 This group contains the algorithms for planarity checking, 547 embedding and drawing. 548 549 \image html planar.png 550 \image latex planar.eps "Plane graph" width=\textwidth 551 */ 552 553 /** 554 @defgroup approx Approximation Algorithms 555 @ingroup algs 556 \brief Approximation algorithms. 557 558 This group contains the approximation and heuristic algorithms 559 implemented in LEMON. 498 560 */ 499 561 … … 505 567 This group contains some algorithms implemented in LEMON 506 568 in order to make it easier to implement complex algorithms. 507 */508 509 /**510 @defgroup approx Approximation Algorithms511 @ingroup algs512 \brief Approximation algorithms.513 514 This group contains the approximation and heuristic algorithms515 implemented in LEMON.516 569 */ 517 570 … … 526 579 527 580 /** 528 @defgroup lp_group L p and MipSolvers581 @defgroup lp_group LP and MIP Solvers 529 582 @ingroup gen_opt_group 530 \brief Lp and Mip solver interfaces for LEMON. 531 532 This group contains Lp and Mip solver interfaces for LEMON. The 533 various LP solvers could be used in the same manner with this 534 interface. 583 \brief LP and MIP solver interfaces for LEMON. 584 585 This group contains LP and MIP solver interfaces for LEMON. 586 Various LP solvers could be used in the same manner with this 587 highlevel interface. 588 589 The currently supported solvers are \ref glpk, \ref clp, \ref cbc, 590 \ref cplex, \ref soplex. 535 591 */ 536 592 … … 622 678 623 679 /** 624 @defgroup dimacs_group DIMACS format680 @defgroup dimacs_group DIMACS Format 625 681 @ingroup io_group 626 682 \brief Read and write files in DIMACS format … … 671 727 \brief Skeleton and concept checking classes for graph structures 672 728 673 This group contains the skeletons and concept checking classes of LEMON's674 graph structures and helper classes used to implement these.729 This group contains the skeletons and concept checking classes of 730 graph structures. 675 731 */ 676 732 … … 684 740 685 741 /** 742 @defgroup tools Standalone Utility Applications 743 744 Some utility applications are listed here. 745 746 The standard compilation procedure (<tt>./configure;make</tt>) will compile 747 them, as well. 748 */ 749 750 /** 686 751 \anchor demoprograms 687 752 … … 695 760 */ 696 761 697 /**698 @defgroup tools Standalone Utility Applications699 700 Some utility applications are listed here.701 702 The standard compilation procedure (<tt>./configure;make</tt>) will compile703 them, as well.704 */705 706 762 }
Note: See TracChangeset
for help on using the changeset viewer.