Changes in doc/groups.dox [710:8b0df68370a4:1023:e0cef67fe565] in lemon
 File:

 1 edited
Legend:
 Unmodified
 Added
 Removed

doc/groups.dox
r710 r1023 3 3 * This file is a part of LEMON, a generic C++ optimization library. 4 4 * 5 * Copyright (C) 200320 095 * Copyright (C) 20032010 6 6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport 7 7 * (Egervary Research Group on Combinatorial Optimization, EGRES). … … 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" 250 263 */ 251 264 … … 260 273 261 274 /** 275 @defgroup geomdat Geometric Data Structures 276 @ingroup auxdat 277 \brief Geometric data structures implemented in LEMON. 278 279 This group contains geometric data structures implemented in LEMON. 280 281  \ref lemon::dim2::Point "dim2::Point" implements a two dimensional 282 vector with the usual operations. 283  \ref lemon::dim2::Box "dim2::Box" can be used to determine the 284 rectangular bounding box of a set of \ref lemon::dim2::Point 285 "dim2::Point"'s. 286 */ 287 288 /** 289 @defgroup matrices Matrices 290 @ingroup auxdat 291 \brief Two dimensional data storages implemented in LEMON. 292 293 This group contains two dimensional data storages implemented in LEMON. 294 */ 295 296 /** 262 297 @defgroup algs Algorithms 263 298 \brief This group contains the several algorithms … … 274 309 275 310 This group contains the common graph search algorithms, namely 276 \e breadthfirst \e search (BFS) and \e depthfirst \e search (DFS). 311 \e breadthfirst \e search (BFS) and \e depthfirst \e search (DFS) 312 \ref clrs01algorithms. 277 313 */ 278 314 … … 282 318 \brief Algorithms for finding shortest paths. 283 319 284 This group contains the algorithms for finding shortest paths in digraphs. 320 This group contains the algorithms for finding shortest paths in digraphs 321 \ref clrs01algorithms. 285 322 286 323  \ref Dijkstra algorithm for finding shortest paths from a source node … … 299 336 300 337 /** 338 @defgroup spantree Minimum Spanning Tree Algorithms 339 @ingroup algs 340 \brief Algorithms for finding minimum cost spanning trees and arborescences. 341 342 This group contains the algorithms for finding minimum cost spanning 343 trees and arborescences \ref clrs01algorithms. 344 */ 345 346 /** 301 347 @defgroup max_flow Maximum Flow Algorithms 302 348 @ingroup algs … … 304 350 305 351 This group contains the algorithms for finding maximum flows and 306 feasible circulations .352 feasible circulations \ref clrs01algorithms, \ref amo93networkflows. 307 353 308 354 The \e maximum \e flow \e problem is to find a flow of maximum value between … … 319 365 320 366 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 367  \ref EdmondsKarp EdmondsKarp algorithm 368 \ref edmondskarp72theoretical. 369  \ref Preflow GoldbergTarjan's preflow pushrelabel algorithm 370 \ref goldberg88newapproach. 371  \ref DinitzSleatorTarjan Dinitz's blocking flow algorithm with dynamic trees 372 \ref dinic70algorithm, \ref sleator83dynamic. 373  \ref GoldbergTarjan !Preflow pushrelabel algorithm with dynamic trees 374 \ref goldberg88newapproach, \ref sleator83dynamic. 375 376 In most cases the \ref Preflow algorithm provides the 327 377 fastest method for computing a maximum flow. All implementations 328 378 also provide functions to query the minimum cut, which is the dual 329 379 problem of maximum flow. 330 380 331 \ref Circulation is a preflow pushrelabel algorithm implemented directly 381 \ref Circulation is a preflow pushrelabel algorithm implemented directly 332 382 for finding feasible circulations, which is a somewhat different problem, 333 383 but it is strongly related to maximum flow. … … 342 392 343 393 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". 394 circulations \ref amo93networkflows. For more information about this 395 problem and its dual solution, see \ref min_cost_flow 396 "Minimum Cost Flow Problem". 346 397 347 398 LEMON contains several algorithms for this problem. 348 399  \ref NetworkSimplex Primal Network Simplex algorithm with various 349 pivot strategies. 350  \ref CostScaling PushRelabel and AugmentRelabel algorithms based on 351 cost scaling. 352  \ref CapacityScaling Successive Shortest %Path algorithm with optional 353 capacity scaling. 354  \ref CancelAndTighten The Cancel and Tighten algorithm. 355  \ref CycleCanceling CycleCanceling algorithms. 356 357 In general NetworkSimplex is the most efficient implementation, 358 but in special cases other algorithms could be faster. 400 pivot strategies \ref dantzig63linearprog, \ref kellyoneill91netsimplex. 401  \ref CostScaling Cost Scaling algorithm based on push/augment and 402 relabel operations \ref goldberg90approximation, \ref goldberg97efficient, 403 \ref bunnagel98efficient. 404  \ref CapacityScaling Capacity Scaling algorithm based on the successive 405 shortest path method \ref edmondskarp72theoretical. 406  \ref CycleCanceling CycleCanceling algorithms, two of which are 407 strongly polynomial \ref klein67primal, \ref goldberg89cyclecanceling. 408 409 In general, \ref NetworkSimplex and \ref CostScaling are the most efficient 410 implementations, but the other two algorithms could be faster in special cases. 359 411 For example, if the total supply and/or capacities are rather small, 360 CapacityScaling is usually the fastest algorithm (without effective scaling).412 \ref CapacityScaling is usually the fastest algorithm (without effective scaling). 361 413 */ 362 414 … … 376 428 377 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 432 LEMON contains several algorithms related to minimum cut problems: … … 392 444 393 445 /** 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 "biedgeconnected 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 446 @defgroup min_mean_cycle Minimum Mean Cycle Algorithms 447 @ingroup algs 448 \brief Algorithms for finding minimum mean cycles. 449 450 This group contains the algorithms for finding minimum mean cycles 451 \ref clrs01algorithms, \ref amo93networkflows. 452 453 The \e minimum \e mean \e cycle \e problem is to find a directed cycle 454 of minimum mean length (cost) in a digraph. 455 The mean length of a cycle is the average length of its arcs, i.e. the 456 ratio between the total length of the cycle and the number of arcs on it. 457 458 This problem has an important connection to \e conservative \e length 459 \e functions, too. A length function on the arcs of a digraph is called 460 conservative if and only if there is no directed cycle of negative total 461 length. For an arbitrary length function, the negative of the minimum 462 cycle mean is the smallest \f$\epsilon\f$ value so that increasing the 463 arc lengths uniformly by \f$\epsilon\f$ results in a conservative length 464 function. 465 466 LEMON contains three algorithms for solving the minimum mean cycle problem: 467  \ref KarpMmc Karp's original algorithm \ref amo93networkflows, 468 \ref dasdan98minmeancycle. 469  \ref HartmannOrlinMmc HartmannOrlin's algorithm, which is an improved 470 version of Karp's algorithm \ref dasdan98minmeancycle. 471  \ref HowardMmc Howard's policy iteration algorithm 472 \ref dasdan98minmeancycle. 473 474 In practice, the \ref HowardMmc "Howard" algorithm turned out to be by far the 475 most efficient one, though the best known theoretical bound on its running 476 time is exponential. 477 Both \ref KarpMmc "Karp" and \ref HartmannOrlinMmc "HartmannOrlin" algorithms 478 run in time O(ne) and use space O(n<sup>2</sup>+e), but the latter one is 479 typically faster due to the applied early termination scheme. 415 480 */ 416 481 … … 450 515 Edmond's blossom shrinking algorithm for calculating maximum weighted 451 516 perfect matching in general graphs. 452 453 \image html bipartite_matching.png 454 \image latex bipartite_matching.eps "Bipartite Matching" width=\textwidth 455 */ 456 457 /** 458 @defgroup spantree Minimum Spanning Tree Algorithms 459 @ingroup algs 460 \brief Algorithms for finding minimum cost spanning trees and arborescences. 461 462 This group contains the algorithms for finding minimum cost spanning 463 trees and arborescences. 517  \ref MaxFractionalMatching Pushrelabel algorithm for calculating 518 maximum cardinality fractional matching in general graphs. 519  \ref MaxWeightedFractionalMatching Augmenting path algorithm for calculating 520 maximum weighted fractional matching in general graphs. 521  \ref MaxWeightedPerfectFractionalMatching 522 Augmenting path algorithm for calculating maximum weighted 523 perfect fractional matching in general graphs. 524 525 \image html matching.png 526 \image latex matching.eps "Min Cost Perfect Matching" width=\textwidth 527 */ 528 529 /** 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 Planar 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_algs Approximation Algorithms 555 @ingroup algs 556 \brief Approximation algorithms. 557 558 This group contains the approximation and heuristic algorithms 559 implemented in LEMON. 560 561 <b>Maximum Clique Problem</b> 562  \ref GrossoLocatelliPullanMc An efficient heuristic algorithm of 563 Grosso, Locatelli, and Pullan. 464 564 */ 465 565 … … 471 571 This group contains some algorithms implemented in LEMON 472 572 in order to make it easier to implement complex algorithms. 473 */474 475 /**476 @defgroup approx Approximation Algorithms477 @ingroup algs478 \brief Approximation algorithms.479 480 This group contains the approximation and heuristic algorithms481 implemented in LEMON.482 573 */ 483 574 … … 492 583 493 584 /** 494 @defgroup lp_group L p and MipSolvers585 @defgroup lp_group LP and MIP Solvers 495 586 @ingroup gen_opt_group 496 \brief Lp and Mip solver interfaces for LEMON. 497 498 This group contains Lp and Mip solver interfaces for LEMON. The 499 various LP solvers could be used in the same manner with this 500 interface. 587 \brief LP and MIP solver interfaces for LEMON. 588 589 This group contains LP and MIP solver interfaces for LEMON. 590 Various LP solvers could be used in the same manner with this 591 highlevel interface. 592 593 The currently supported solvers are \ref glpk, \ref clp, \ref cbc, 594 \ref cplex, \ref soplex. 501 595 */ 502 596 … … 588 682 589 683 /** 590 @defgroup dimacs_group DIMACS format684 @defgroup dimacs_group DIMACS Format 591 685 @ingroup io_group 592 686 \brief Read and write files in DIMACS format … … 637 731 \brief Skeleton and concept checking classes for graph structures 638 732 639 This group contains the skeletons and concept checking classes of LEMON's640 graph structures and helper classes used to implement these.733 This group contains the skeletons and concept checking classes of 734 graph structures. 641 735 */ 642 736 … … 650 744 651 745 /** 746 @defgroup tools Standalone Utility Applications 747 748 Some utility applications are listed here. 749 750 The standard compilation procedure (<tt>./configure;make</tt>) will compile 751 them, as well. 752 */ 753 754 /** 652 755 \anchor demoprograms 653 756 … … 661 764 */ 662 765 663 /**664 @defgroup tools Standalone Utility Applications665 666 Some utility applications are listed here.667 668 The standard compilation procedure (<tt>./configure;make</tt>) will compile669 them, as well.670 */671 672 766 }
Note: See TracChangeset
for help on using the changeset viewer.