Changes in doc/groups.dox [959:38213abd2911:1280:fbdde70389da] in lemon
 File:

 1 edited
Legend:
 Unmodified
 Added
 Removed

doc/groups.dox
r959 r1280 3 3 * This file is a part of LEMON, a generic C++ optimization library. 4 4 * 5 * Copyright (C) 2003201 05 * Copyright (C) 20032013 6 6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport 7 7 * (Egervary Research Group on Combinatorial Optimization, EGRES). … … 113 113 detailed documentation of particular adaptors. 114 114 115 Since the adaptor classes conform to the \ref graph_concepts "graph concepts", 116 an adaptor can even be applied to another one. 117 The following image illustrates a situation when a \ref SubDigraph adaptor 118 is applied on a digraph and \ref Undirector is applied on the subgraph. 119 120 \image html adaptors2.png 121 \image latex adaptors2.eps "Using graph adaptors" width=\textwidth 122 115 123 The behavior of graph adaptors can be very different. Some of them keep 116 124 capabilities of the original graph while in other cases this would be … … 287 295 288 296 /** 289 @defgroup matrices Matrices290 @ingroup auxdat291 \brief Two dimensional data storages implemented in LEMON.292 293 This group contains two dimensional data storages implemented in LEMON.294 */295 296 /**297 297 @defgroup algs Algorithms 298 298 \brief This group contains the several algorithms … … 310 310 This group contains the common graph search algorithms, namely 311 311 \e breadthfirst \e search (BFS) and \e depthfirst \e search (DFS) 312 \ refclrs01algorithms.312 \cite clrs01algorithms. 313 313 */ 314 314 … … 319 319 320 320 This group contains the algorithms for finding shortest paths in digraphs 321 \ refclrs01algorithms.321 \cite clrs01algorithms. 322 322 323 323  \ref Dijkstra algorithm for finding shortest paths from a source node … … 327 327 but the digraph should not contain directed cycles with negative total 328 328 length. 329  \ref FloydWarshall "FloydWarshall" and \ref Johnson "Johnson" algorithms330 for solving the \e allpairs \e shortest \e paths \e problem when arc331 lenghts can be either positive or negative, but the digraph should332 not contain directed cycles with negative total length.333 329  \ref Suurballe A successive shortest path algorithm for finding 334 330 arcdisjoint paths between two nodes having minimum total length. … … 341 337 342 338 This group contains the algorithms for finding minimum cost spanning 343 trees and arborescences \ refclrs01algorithms.339 trees and arborescences \cite clrs01algorithms. 344 340 */ 345 341 … … 350 346 351 347 This group contains the algorithms for finding maximum flows and 352 feasible circulations \ ref clrs01algorithms, \refamo93networkflows.348 feasible circulations \cite clrs01algorithms, \cite amo93networkflows. 353 349 354 350 The \e maximum \e flow \e problem is to find a flow of maximum value between … … 364 360 \f[ 0 \leq f(uv) \leq cap(uv) \quad \forall uv\in A \f] 365 361 366 LEMON contains several algorithms for solving maximum flow problems: 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 377 fastest method for computing a maximum flow. All implementations 378 also provide functions to query the minimum cut, which is the dual 379 problem of maximum flow. 362 \ref Preflow is an efficient implementation of GoldbergTarjan's 363 preflow pushrelabel algorithm \cite goldberg88newapproach for finding 364 maximum flows. It also provides functions to query the minimum cut, 365 which is the dual problem of maximum flow. 380 366 381 367 \ref Circulation is a preflow pushrelabel algorithm implemented directly … … 392 378 393 379 This group contains the algorithms for finding minimum cost flows and 394 circulations \ refamo93networkflows. For more information about this395 problem and its dual solution, see \ref min_cost_flow380 circulations \cite amo93networkflows. For more information about this 381 problem and its dual solution, see: \ref min_cost_flow 396 382 "Minimum Cost Flow Problem". 397 383 398 384 LEMON contains several algorithms for this problem. 399 385  \ref NetworkSimplex Primal Network Simplex algorithm with various 400 pivot strategies \ ref dantzig63linearprog, \refkellyoneill91netsimplex.386 pivot strategies \cite dantzig63linearprog, \cite kellyoneill91netsimplex. 401 387  \ref CostScaling Cost Scaling algorithm based on push/augment and 402 relabel operations \ ref goldberg90approximation, \refgoldberg97efficient,403 \ refbunnagel98efficient.388 relabel operations \cite goldberg90approximation, \cite goldberg97efficient, 389 \cite bunnagel98efficient. 404 390  \ref CapacityScaling Capacity Scaling algorithm based on the successive 405 shortest path method \ refedmondskarp72theoretical.391 shortest path method \cite edmondskarp72theoretical. 406 392  \ref CycleCanceling CycleCanceling algorithms, two of which are 407 strongly polynomial \ref klein67primal, \ref goldberg89cyclecanceling. 408 409 In general NetworkSimplex is the most efficient implementation, 410 but in special cases other algorithms could be faster. 393 strongly polynomial \cite klein67primal, \cite goldberg89cyclecanceling. 394 395 In general, \ref NetworkSimplex and \ref CostScaling are the most efficient 396 implementations. 397 \ref NetworkSimplex is usually the fastest on relatively small graphs (up to 398 several thousands of nodes) and on dense graphs, while \ref CostScaling is 399 typically more efficient on large graphs (e.g. hundreds of thousands of 400 nodes or above), especially if they are sparse. 401 However, other algorithms could be faster in special cases. 411 402 For example, if the total supply and/or capacities are rather small, 412 CapacityScaling is usually the fastest algorithm (without effective scaling). 403 \ref CapacityScaling is usually the fastest algorithm 404 (without effective scaling). 405 406 These classes are intended to be used with integervalued input data 407 (capacities, supply values, and costs), except for \ref CapacityScaling, 408 which is capable of handling realvalued arc costs (other numerical 409 data are required to be integer). 410 411 For more details about these implementations and for a comprehensive 412 experimental study, see the paper \cite KiralyKovacs12MCF. 413 It also compares these codes to other publicly available 414 minimum cost flow solvers. 413 415 */ 414 416 … … 449 451 450 452 This group contains the algorithms for finding minimum mean cycles 451 \ ref clrs01algorithms, \ref amo93networkflows.453 \cite amo93networkflows, \cite karp78characterization. 452 454 453 455 The \e minimum \e mean \e cycle \e problem is to find a directed cycle … … 465 467 466 468 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 KarpMmc Karp's original algorithm \cite karp78characterization. 469 470  \ref HartmannOrlinMmc HartmannOrlin's algorithm, which is an improved 470 version of Karp's algorithm \ ref dasdan98minmeancycle.471 version of Karp's algorithm \cite hartmann93finding. 471 472  \ref HowardMmc Howard's policy iteration algorithm 472 \ ref dasdan98minmeancycle.473 474 In practice, the \ref HowardMmc "Howard" algorithm provedto be by far the473 \cite dasdan98minmeancycle, \cite dasdan04experimental. 474 475 In practice, the \ref HowardMmc "Howard" algorithm turned out to be by far the 475 476 most efficient one, though the best known theoretical bound on its running 476 477 time is exponential. 477 478 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. 479 run in time O(nm) and use space O(n<sup>2</sup>+m). 480 480 */ 481 481 … … 498 498 499 499 The matching algorithms implemented in LEMON: 500  \ref MaxBipartiteMatching HopcroftKarp augmenting path algorithm501 for calculating maximum cardinality matching in bipartite graphs.502  \ref PrBipartiteMatching Pushrelabel algorithm503 for calculating maximum cardinality matching in bipartite graphs.504  \ref MaxWeightedBipartiteMatching505 Successive shortest path algorithm for calculating maximum weighted506 matching and maximum weighted bipartite matching in bipartite graphs.507  \ref MinCostMaxBipartiteMatching508 Successive shortest path algorithm for calculating minimum cost maximum509 matching in bipartite graphs.510 500  \ref MaxMatching Edmond's blossom shrinking algorithm for calculating 511 501 maximum cardinality matching in general graphs. … … 540 530 541 531 /** 542 @defgroup planar Planar ityEmbedding and Drawing532 @defgroup planar Planar Embedding and Drawing 543 533 @ingroup algs 544 534 \brief Algorithms for planarity checking, embedding and drawing … … 552 542 553 543 /** 554 @defgroup approx Approximation Algorithms 544 @defgroup tsp Traveling Salesman Problem 545 @ingroup algs 546 \brief Algorithms for the symmetric traveling salesman problem 547 548 This group contains basic heuristic algorithms for the the symmetric 549 \e traveling \e salesman \e problem (TSP). 550 Given an \ref FullGraph "undirected full graph" with a cost map on its edges, 551 the problem is to find a shortest possible tour that visits each node exactly 552 once (i.e. the minimum cost Hamiltonian cycle). 553 554 These TSP algorithms are intended to be used with a \e metric \e cost 555 \e function, i.e. the edge costs should satisfy the triangle inequality. 556 Otherwise the algorithms could yield worse results. 557 558 LEMON provides five wellknown heuristics for solving symmetric TSP: 559  \ref NearestNeighborTsp Neareast neighbor algorithm 560  \ref GreedyTsp Greedy algorithm 561  \ref InsertionTsp Insertion heuristic (with four selection methods) 562  \ref ChristofidesTsp Christofides algorithm 563  \ref Opt2Tsp 2opt algorithm 564 565 \ref NearestNeighborTsp, \ref GreedyTsp, and \ref InsertionTsp are the fastest 566 solution methods. Furthermore, \ref InsertionTsp is usually quite effective. 567 568 \ref ChristofidesTsp is somewhat slower, but it has the best guaranteed 569 approximation factor: 3/2. 570 571 \ref Opt2Tsp usually provides the best results in practice, but 572 it is the slowest method. It can also be used to improve given tours, 573 for example, the results of other algorithms. 574 575 \image html tsp.png 576 \image latex tsp.eps "Traveling salesman problem" width=\textwidth 577 */ 578 579 /** 580 @defgroup approx_algs Approximation Algorithms 555 581 @ingroup algs 556 582 \brief Approximation algorithms. … … 558 584 This group contains the approximation and heuristic algorithms 559 585 implemented in LEMON. 586 587 <b>Maximum Clique Problem</b> 588  \ref GrossoLocatelliPullanMc An efficient heuristic algorithm of 589 Grosso, Locatelli, and Pullan. 560 590 */ 561 591 … … 587 617 highlevel interface. 588 618 589 The currently supported solvers are \ref glpk, \ref clp, \ref cbc, 590 \ref cplex, \ref soplex. 591 */ 592 593 /** 594 @defgroup lp_utils Tools for Lp and Mip Solvers 595 @ingroup lp_group 596 \brief Helper tools to the Lp and Mip solvers. 597 598 This group adds some helper tools to general optimization framework 599 implemented in LEMON. 600 */ 601 602 /** 603 @defgroup metah Metaheuristics 604 @ingroup gen_opt_group 605 \brief Metaheuristics for LEMON library. 606 607 This group contains some metaheuristic optimization tools. 619 The currently supported solvers are \cite glpk, \cite clp, \cite cbc, 620 \cite cplex, \cite soplex. 608 621 */ 609 622 … … 675 688 This group contains general \c EPS drawing methods and special 676 689 graph exporting tools. 690 691 \image html graph_to_eps.png 677 692 */ 678 693
Note: See TracChangeset
for help on using the changeset viewer.