Changeset 953:d8ea85825e02 in lemon for doc
- Timestamp:
- 03/16/10 21:27:35 (15 years ago)
- Branch:
- default
- Parents:
- 952:23da1b807280 (diff), 951:41d7ac528c3a (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
r948 r953 281 281 282 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 /** 283 305 @defgroup algs Algorithms 284 306 \brief This group contains the several algorithms … … 295 317 296 318 This group contains the common graph search algorithms, namely 297 \e breadth-first \e search (BFS) and \e depth-first \e search (DFS). 319 \e breadth-first \e search (BFS) and \e depth-first \e search (DFS) 320 \ref clrs01algorithms. 298 321 */ 299 322 … … 303 326 \brief Algorithms for finding shortest paths. 304 327 305 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. 306 330 307 331 - \ref Dijkstra algorithm for finding shortest paths from a source node … … 320 344 321 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 /** 322 355 @defgroup max_flow Maximum Flow Algorithms 323 356 @ingroup algs … … 325 358 326 359 This group contains the algorithms for finding maximum flows and 327 feasible circulations .360 feasible circulations \ref clrs01algorithms, \ref amo93networkflows. 328 361 329 362 The \e maximum \e flow \e problem is to find a flow of maximum value between … … 340 373 341 374 LEMON contains several algorithms for solving maximum flow problems: 342 - \ref EdmondsKarp Edmonds-Karp algorithm. 343 - \ref Preflow Goldberg-Tarjan's preflow push-relabel algorithm. 344 - \ref DinitzSleatorTarjan Dinitz's blocking flow algorithm with dynamic trees. 345 - \ref GoldbergTarjan Preflow push-relabel algorithm with dynamic trees. 346 347 In most cases the \ref Preflow "Preflow" algorithm provides the 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 348 385 fastest method for computing a maximum flow. All implementations 349 386 also provide functions to query the minimum cut, which is the dual … … 363 400 364 401 This group contains the algorithms for finding minimum cost flows and 365 circulations. For more information about this problem and its dual 366 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". 367 405 368 406 LEMON contains several algorithms for this problem. 369 407 - \ref NetworkSimplex Primal Network Simplex algorithm with various 370 pivot strategies. 371 - \ref CostScaling Push-Relabel and Augment-Relabel algorithms based on 372 cost scaling. 373 - \ref CapacityScaling Successive Shortest %Path algorithm with optional 374 capacity scaling. 375 - \ref CancelAndTighten The Cancel and Tighten algorithm. 376 - \ref CycleCanceling Cycle-Canceling algorithms. 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. 377 416 378 417 In general NetworkSimplex is the most efficient implementation, … … 397 436 398 437 \f[ \min_{X \subset V, X\not\in \{\emptyset, V\}} 399 \sum_{uv\in A ,u\in X, v\not\in X}cap(uv) \f]438 \sum_{uv\in A: u\in X, v\not\in X}cap(uv) \f] 400 439 401 440 LEMON contains several algorithms related to minimum cut problems: … … 413 452 414 453 /** 415 @defgroup graph_properties Connectivity and Other Graph Properties 416 @ingroup algs 417 \brief Algorithms for discovering the graph properties 418 419 This group contains the algorithms for discovering the graph properties 420 like connectivity, bipartiteness, euler property, simplicity etc. 421 422 \image html edge_biconnected_components.png 423 \image latex edge_biconnected_components.eps "bi-edge-connected components" width=\textwidth 424 */ 425 426 /** 427 @defgroup planar Planarity Embedding and Drawing 428 @ingroup algs 429 \brief Algorithms for planarity checking, embedding and drawing 430 431 This group contains the algorithms for planarity checking, 432 embedding and drawing. 433 434 \image html planar.png 435 \image latex planar.eps "Plane graph" width=\textwidth 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. 436 488 */ 437 489 … … 479 531 perfect fractional matching in general graphs. 480 532 481 \image html bipartite_matching.png 482 \image latex bipartite_matching.eps "Bipartite Matching" width=\textwidth 483 */ 484 485 /** 486 @defgroup spantree Minimum Spanning Tree Algorithms 487 @ingroup algs 488 \brief Algorithms for finding minimum cost spanning trees and arborescences. 489 490 This group contains the algorithms for finding minimum cost spanning 491 trees and arborescences. 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 559 */ 560 561 /** 562 @defgroup approx Approximation Algorithms 563 @ingroup algs 564 \brief Approximation algorithms. 565 566 This group contains the approximation and heuristic algorithms 567 implemented in LEMON. 492 568 */ 493 569 … … 499 575 This group contains some algorithms implemented in LEMON 500 576 in order to make it easier to implement complex algorithms. 501 */502 503 /**504 @defgroup approx Approximation Algorithms505 @ingroup algs506 \brief Approximation algorithms.507 508 This group contains the approximation and heuristic algorithms509 implemented in LEMON.510 577 */ 511 578 … … 520 587 521 588 /** 522 @defgroup lp_group L p and MipSolvers589 @defgroup lp_group LP and MIP Solvers 523 590 @ingroup gen_opt_group 524 \brief Lp and Mip solver interfaces for LEMON. 525 526 This group contains Lp and Mip solver interfaces for LEMON. The 527 various LP solvers could be used in the same manner with this 528 interface. 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. 529 599 */ 530 600 … … 616 686 617 687 /** 618 @defgroup dimacs_group DIMACS format688 @defgroup dimacs_group DIMACS Format 619 689 @ingroup io_group 620 690 \brief Read and write files in DIMACS format … … 665 735 \brief Skeleton and concept checking classes for graph structures 666 736 667 This group contains the skeletons and concept checking classes of LEMON's668 graph structures and helper classes used to implement these.737 This group contains the skeletons and concept checking classes of 738 graph structures. 669 739 */ 670 740 … … 678 748 679 749 /** 750 @defgroup tools Standalone Utility Applications 751 752 Some utility applications are listed here. 753 754 The standard compilation procedure (<tt>./configure;make</tt>) will compile 755 them, as well. 756 */ 757 758 /** 680 759 \anchor demoprograms 681 760 … … 689 768 */ 690 769 691 /**692 @defgroup tools Standalone Utility Applications693 694 Some utility applications are listed here.695 696 The standard compilation procedure (<tt>./configure;make</tt>) will compile697 them, as well.698 */699 700 770 } -
doc/groups.dox
r952 r953 387 387 problem of maximum flow. 388 388 389 \ref Circulation is a preflow push-relabel algorithm implemented directly 389 \ref Circulation is a preflow push-relabel algorithm implemented directly 390 390 for finding feasible circulations, which is a somewhat different problem, 391 391 but it is strongly related to maximum flow. … … 523 523 Edmond's blossom shrinking algorithm for calculating maximum weighted 524 524 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. 525 532 526 533 \image html matching.png
Note: See TracChangeset
for help on using the changeset viewer.