Changes in doc/groups.dox [956:141f9c0db4a3:710:8b0df68370a4] in lemon
- File:
-
- 1 edited
Legend:
- Unmodified
- Added
- Removed
-
doc/groups.dox
r956 r710 3 3 * This file is a part of LEMON, a generic C++ optimization library. 4 4 * 5 * Copyright (C) 2003-20 105 * Copyright (C) 2003-2009 6 6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport 7 7 * (Egervary Research Group on Combinatorial Optimization, EGRES). … … 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 /** 229 237 @defgroup paths Path Structures 230 238 @ingroup datas … … 239 247 any kind of path structure. 240 248 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. 249 \sa lemon::concepts::Path 271 250 */ 272 251 … … 281 260 282 261 /** 283 @defgroup geomdat Geometric Data Structures284 @ingroup auxdat285 \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 dimensional290 vector with the usual operations.291 - \ref lemon::dim2::Box "dim2::Box" can be used to determine the292 rectangular bounding box of a set of \ref lemon::dim2::Point293 "dim2::Point"'s.294 */295 296 /**297 @defgroup matrices Matrices298 @ingroup auxdat299 \brief Two dimensional data storages implemented in LEMON.300 301 This group contains two dimensional data storages implemented in LEMON.302 */303 304 /**305 262 @defgroup algs Algorithms 306 263 \brief This group contains the several algorithms … … 317 274 318 275 This group contains the common graph search algorithms, namely 319 \e breadth-first \e search (BFS) and \e depth-first \e search (DFS) 320 \ref clrs01algorithms. 276 \e breadth-first \e search (BFS) and \e depth-first \e search (DFS). 321 277 */ 322 278 … … 326 282 \brief Algorithms for finding shortest paths. 327 283 328 This group contains the algorithms for finding shortest paths in digraphs 329 \ref clrs01algorithms. 284 This group contains the algorithms for finding shortest paths in digraphs. 330 285 331 286 - \ref Dijkstra algorithm for finding shortest paths from a source node … … 344 299 345 300 /** 346 @defgroup spantree Minimum Spanning Tree Algorithms347 @ingroup algs348 \brief Algorithms for finding minimum cost spanning trees and arborescences.349 350 This group contains the algorithms for finding minimum cost spanning351 trees and arborescences \ref clrs01algorithms.352 */353 354 /**355 301 @defgroup max_flow Maximum Flow Algorithms 356 302 @ingroup algs … … 358 304 359 305 This group contains the algorithms for finding maximum flows and 360 feasible circulations \ref clrs01algorithms, \ref amo93networkflows.306 feasible circulations. 361 307 362 308 The \e maximum \e flow \e problem is to find a flow of maximum value between … … 373 319 374 320 LEMON contains several algorithms for solving maximum flow problems: 375 - \ref EdmondsKarp Edmonds-Karp algorithm 376 \ref edmondskarp72theoretical. 377 - \ref Preflow Goldberg-Tarjan's preflow push-relabel algorithm 378 \ref goldberg88newapproach. 379 - \ref DinitzSleatorTarjan Dinitz's blocking flow algorithm with dynamic trees 380 \ref dinic70algorithm, \ref sleator83dynamic. 381 - \ref GoldbergTarjan !Preflow push-relabel algorithm with dynamic trees 382 \ref goldberg88newapproach, \ref sleator83dynamic. 383 384 In most cases the \ref Preflow algorithm provides the 321 - \ref EdmondsKarp Edmonds-Karp algorithm. 322 - \ref Preflow Goldberg-Tarjan's preflow push-relabel algorithm. 323 - \ref DinitzSleatorTarjan Dinitz's blocking flow algorithm with dynamic trees. 324 - \ref GoldbergTarjan Preflow push-relabel algorithm with dynamic trees. 325 326 In most cases the \ref Preflow "Preflow" algorithm provides the 385 327 fastest method for computing a maximum flow. All implementations 386 328 also provide functions to query the minimum cut, which is the dual 387 329 problem of maximum flow. 388 330 389 \ref Circulation is a preflow push-relabel algorithm implemented directly 331 \ref Circulation is a preflow push-relabel algorithm implemented directly 390 332 for finding feasible circulations, which is a somewhat different problem, 391 333 but it is strongly related to maximum flow. … … 400 342 401 343 This group contains the algorithms for finding minimum cost flows and 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". 344 circulations. For more information about this problem and its dual 345 solution see \ref min_cost_flow "Minimum Cost Flow Problem". 405 346 406 347 LEMON contains several algorithms for this problem. 407 348 - \ref NetworkSimplex Primal Network Simplex algorithm with various 408 pivot strategies \ref dantzig63linearprog, \ref kellyoneill91netsimplex. 409 - \ref CostScaling Cost Scaling algorithm based on push/augment and 410 relabel operations \ref goldberg90approximation, \ref goldberg97efficient, 411 \ref bunnagel98efficient. 412 - \ref CapacityScaling Capacity Scaling algorithm based on the successive 413 shortest path method \ref edmondskarp72theoretical. 414 - \ref CycleCanceling Cycle-Canceling algorithms, two of which are 415 strongly polynomial \ref klein67primal, \ref goldberg89cyclecanceling. 349 pivot strategies. 350 - \ref CostScaling Push-Relabel and Augment-Relabel 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 Cycle-Canceling algorithms. 416 356 417 357 In general NetworkSimplex is the most efficient implementation, … … 436 376 437 377 \f[ \min_{X \subset V, X\not\in \{\emptyset, V\}} 438 \sum_{uv\in A :u\in X, v\not\in X}cap(uv) \f]378 \sum_{uv\in A, u\in X, v\not\in X}cap(uv) \f] 439 379 440 380 LEMON contains several algorithms related to minimum cut problems: … … 452 392 453 393 /** 454 @defgroup min_mean_cycle Minimum Mean Cycle Algorithms 455 @ingroup algs 456 \brief Algorithms for finding minimum mean cycles. 457 458 This group contains the algorithms for finding minimum mean cycles 459 \ref clrs01algorithms, \ref amo93networkflows. 460 461 The \e minimum \e mean \e cycle \e problem is to find a directed cycle 462 of minimum mean length (cost) in a digraph. 463 The mean length of a cycle is the average length of its arcs, i.e. the 464 ratio between the total length of the cycle and the number of arcs on it. 465 466 This problem has an important connection to \e conservative \e length 467 \e functions, too. A length function on the arcs of a digraph is called 468 conservative if and only if there is no directed cycle of negative total 469 length. For an arbitrary length function, the negative of the minimum 470 cycle mean is the smallest \f$\epsilon\f$ value so that increasing the 471 arc lengths uniformly by \f$\epsilon\f$ results in a conservative length 472 function. 473 474 LEMON contains three algorithms for solving the minimum mean cycle problem: 475 - \ref Karp "Karp"'s original algorithm \ref amo93networkflows, 476 \ref dasdan98minmeancycle. 477 - \ref HartmannOrlin "Hartmann-Orlin"'s algorithm, which is an improved 478 version of Karp's algorithm \ref dasdan98minmeancycle. 479 - \ref Howard "Howard"'s policy iteration algorithm 480 \ref dasdan98minmeancycle. 481 482 In practice, the Howard algorithm proved to be by far the most efficient 483 one, though the best known theoretical bound on its running time is 484 exponential. 485 Both Karp and HartmannOrlin algorithms run in time O(ne) and use space 486 O(n<sup>2</sup>+e), but the latter one is typically faster due to the 487 applied early termination scheme. 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 488 415 */ 489 416 … … 523 450 Edmond's blossom shrinking algorithm for calculating maximum weighted 524 451 perfect matching in general graphs. 525 - \ref MaxFractionalMatching Push-relabel algorithm for calculating 526 maximum cardinality fractional matching in general graphs. 527 - \ref MaxWeightedFractionalMatching Augmenting path algorithm for calculating 528 maximum weighted fractional matching in general graphs. 529 - \ref MaxWeightedPerfectFractionalMatching 530 Augmenting path algorithm for calculating maximum weighted 531 perfect fractional matching in general graphs. 532 533 \image html matching.png 534 \image latex matching.eps "Min Cost Perfect Matching" width=\textwidth 535 */ 536 537 /** 538 @defgroup graph_properties Connectivity and Other Graph Properties 539 @ingroup algs 540 \brief Algorithms for discovering the graph properties 541 542 This group contains the algorithms for discovering the graph properties 543 like connectivity, bipartiteness, euler property, simplicity etc. 544 545 \image html connected_components.png 546 \image latex connected_components.eps "Connected components" width=\textwidth 547 */ 548 549 /** 550 @defgroup planar Planarity Embedding and Drawing 551 @ingroup algs 552 \brief Algorithms for planarity checking, embedding and drawing 553 554 This group contains the algorithms for planarity checking, 555 embedding and drawing. 556 557 \image html planar.png 558 \image latex planar.eps "Plane graph" width=\textwidth 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. 464 */ 465 466 /** 467 @defgroup auxalg Auxiliary Algorithms 468 @ingroup algs 469 \brief Auxiliary algorithms implemented in LEMON. 470 471 This group contains some algorithms implemented in LEMON 472 in order to make it easier to implement complex algorithms. 559 473 */ 560 474 … … 566 480 This group contains the approximation and heuristic algorithms 567 481 implemented in LEMON. 568 */569 570 /**571 @defgroup auxalg Auxiliary Algorithms572 @ingroup algs573 \brief Auxiliary algorithms implemented in LEMON.574 575 This group contains some algorithms implemented in LEMON576 in order to make it easier to implement complex algorithms.577 482 */ 578 483 … … 587 492 588 493 /** 589 @defgroup lp_group L P and MIPSolvers494 @defgroup lp_group Lp and Mip Solvers 590 495 @ingroup gen_opt_group 591 \brief LP and MIP solver interfaces for LEMON. 592 593 This group contains LP and MIP solver interfaces for LEMON. 594 Various LP solvers could be used in the same manner with this 595 high-level interface. 596 597 The currently supported solvers are \ref glpk, \ref clp, \ref cbc, 598 \ref cplex, \ref soplex. 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. 599 501 */ 600 502 … … 686 588 687 589 /** 688 @defgroup dimacs_group DIMACS Format590 @defgroup dimacs_group DIMACS format 689 591 @ingroup io_group 690 592 \brief Read and write files in DIMACS format … … 735 637 \brief Skeleton and concept checking classes for graph structures 736 638 737 This group contains the skeletons and concept checking classes of 738 graph structures .639 This group contains the skeletons and concept checking classes of LEMON's 640 graph structures and helper classes used to implement these. 739 641 */ 740 642 … … 748 650 749 651 /** 652 \anchor demoprograms 653 654 @defgroup demos Demo Programs 655 656 Some demo programs are listed here. Their full source codes can be found in 657 the \c demo subdirectory of the source tree. 658 659 In order to compile them, use the <tt>make demo</tt> or the 660 <tt>make check</tt> commands. 661 */ 662 663 /** 750 664 @defgroup tools Standalone Utility Applications 751 665 … … 756 670 */ 757 671 758 /**759 \anchor demoprograms760 761 @defgroup demos Demo Programs762 763 Some demo programs are listed here. Their full source codes can be found in764 the \c demo subdirectory of the source tree.765 766 In order to compile them, use the <tt>make demo</tt> or the767 <tt>make check</tt> commands.768 */769 770 672 }
Note: See TracChangeset
for help on using the changeset viewer.