Changes in doc/groups.dox [1280:fbdde70389da:959:38213abd2911] in lemon
- File:
-
- 1 edited
Legend:
- Unmodified
- Added
- Removed
-
doc/groups.dox
r1280 r959 3 3 * This file is a part of LEMON, a generic C++ optimization library. 4 4 * 5 * Copyright (C) 2003-201 35 * Copyright (C) 2003-2010 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 adaptor118 is applied on a digraph and \ref Undirector is applied on the subgraph.119 120 \image html adaptors2.png121 \image latex adaptors2.eps "Using graph adaptors" width=\textwidth122 123 115 The behavior of graph adaptors can be very different. Some of them keep 124 116 capabilities of the original graph while in other cases this would be … … 295 287 296 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 /** 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 breadth-first \e search (BFS) and \e depth-first \e search (DFS) 312 \ citeclrs01algorithms.312 \ref clrs01algorithms. 313 313 */ 314 314 … … 319 319 320 320 This group contains the algorithms for finding shortest paths in digraphs 321 \ citeclrs01algorithms.321 \ref 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 "Floyd-Warshall" and \ref Johnson "Johnson" algorithms 330 for solving the \e all-pairs \e shortest \e paths \e problem when arc 331 lenghts can be either positive or negative, but the digraph should 332 not contain directed cycles with negative total length. 329 333 - \ref Suurballe A successive shortest path algorithm for finding 330 334 arc-disjoint paths between two nodes having minimum total length. … … 337 341 338 342 This group contains the algorithms for finding minimum cost spanning 339 trees and arborescences \ citeclrs01algorithms.343 trees and arborescences \ref clrs01algorithms. 340 344 */ 341 345 … … 346 350 347 351 This group contains the algorithms for finding maximum flows and 348 feasible circulations \ cite clrs01algorithms, \citeamo93networkflows.352 feasible circulations \ref clrs01algorithms, \ref amo93networkflows. 349 353 350 354 The \e maximum \e flow \e problem is to find a flow of maximum value between … … 360 364 \f[ 0 \leq f(uv) \leq cap(uv) \quad \forall uv\in A \f] 361 365 362 \ref Preflow is an efficient implementation of Goldberg-Tarjan's 363 preflow push-relabel 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. 366 LEMON contains several algorithms for solving maximum flow problems: 367 - \ref EdmondsKarp Edmonds-Karp algorithm 368 \ref edmondskarp72theoretical. 369 - \ref Preflow Goldberg-Tarjan's preflow push-relabel algorithm 370 \ref goldberg88newapproach. 371 - \ref DinitzSleatorTarjan Dinitz's blocking flow algorithm with dynamic trees 372 \ref dinic70algorithm, \ref sleator83dynamic. 373 - \ref GoldbergTarjan !Preflow push-relabel 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. 366 380 367 381 \ref Circulation is a preflow push-relabel algorithm implemented directly … … 378 392 379 393 This group contains the algorithms for finding minimum cost flows and 380 circulations \ citeamo93networkflows. For more information about this381 problem and its dual solution, see :\ref min_cost_flow394 circulations \ref amo93networkflows. For more information about this 395 problem and its dual solution, see \ref min_cost_flow 382 396 "Minimum Cost Flow Problem". 383 397 384 398 LEMON contains several algorithms for this problem. 385 399 - \ref NetworkSimplex Primal Network Simplex algorithm with various 386 pivot strategies \ cite dantzig63linearprog, \citekellyoneill91netsimplex.400 pivot strategies \ref dantzig63linearprog, \ref kellyoneill91netsimplex. 387 401 - \ref CostScaling Cost Scaling algorithm based on push/augment and 388 relabel operations \ cite goldberg90approximation, \citegoldberg97efficient,389 \ citebunnagel98efficient.402 relabel operations \ref goldberg90approximation, \ref goldberg97efficient, 403 \ref bunnagel98efficient. 390 404 - \ref CapacityScaling Capacity Scaling algorithm based on the successive 391 shortest path method \ citeedmondskarp72theoretical.405 shortest path method \ref edmondskarp72theoretical. 392 406 - \ref CycleCanceling Cycle-Canceling algorithms, two of which are 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. 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. 402 411 For example, if the total supply and/or capacities are rather small, 403 \ref CapacityScaling is usually the fastest algorithm 404 (without effective scaling). 405 406 These classes are intended to be used with integer-valued input data 407 (capacities, supply values, and costs), except for \ref CapacityScaling, 408 which is capable of handling real-valued 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. 412 CapacityScaling is usually the fastest algorithm (without effective scaling). 415 413 */ 416 414 … … 451 449 452 450 This group contains the algorithms for finding minimum mean cycles 453 \ cite amo93networkflows, \cite karp78characterization.451 \ref clrs01algorithms, \ref amo93networkflows. 454 452 455 453 The \e minimum \e mean \e cycle \e problem is to find a directed cycle … … 467 465 468 466 LEMON contains three algorithms for solving the minimum mean cycle problem: 469 - \ref KarpMmc Karp's original algorithm \cite karp78characterization. 467 - \ref KarpMmc Karp's original algorithm \ref amo93networkflows, 468 \ref dasdan98minmeancycle. 470 469 - \ref HartmannOrlinMmc Hartmann-Orlin's algorithm, which is an improved 471 version of Karp's algorithm \ cite hartmann93finding.470 version of Karp's algorithm \ref dasdan98minmeancycle. 472 471 - \ref HowardMmc Howard's policy iteration algorithm 473 \ cite dasdan98minmeancycle, \cite dasdan04experimental.474 475 In practice, the \ref HowardMmc "Howard" algorithm turned outto be by far the472 \ref dasdan98minmeancycle. 473 474 In practice, the \ref HowardMmc "Howard" algorithm proved to be by far the 476 475 most efficient one, though the best known theoretical bound on its running 477 476 time is exponential. 478 477 Both \ref KarpMmc "Karp" and \ref HartmannOrlinMmc "Hartmann-Orlin" algorithms 479 run in time O(nm) and use space O(n<sup>2</sup>+m). 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. 480 480 */ 481 481 … … 498 498 499 499 The matching algorithms implemented in LEMON: 500 - \ref MaxBipartiteMatching Hopcroft-Karp augmenting path algorithm 501 for calculating maximum cardinality matching in bipartite graphs. 502 - \ref PrBipartiteMatching Push-relabel algorithm 503 for calculating maximum cardinality matching in bipartite graphs. 504 - \ref MaxWeightedBipartiteMatching 505 Successive shortest path algorithm for calculating maximum weighted 506 matching and maximum weighted bipartite matching in bipartite graphs. 507 - \ref MinCostMaxBipartiteMatching 508 Successive shortest path algorithm for calculating minimum cost maximum 509 matching in bipartite graphs. 500 510 - \ref MaxMatching Edmond's blossom shrinking algorithm for calculating 501 511 maximum cardinality matching in general graphs. … … 530 540 531 541 /** 532 @defgroup planar Planar Embedding and Drawing542 @defgroup planar Planarity Embedding and Drawing 533 543 @ingroup algs 534 544 \brief Algorithms for planarity checking, embedding and drawing … … 542 552 543 553 /** 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 well-known 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 2-opt 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 554 @defgroup approx Approximation Algorithms 581 555 @ingroup algs 582 556 \brief Approximation algorithms. … … 584 558 This group contains the approximation and heuristic algorithms 585 559 implemented in LEMON. 586 587 <b>Maximum Clique Problem</b>588 - \ref GrossoLocatelliPullanMc An efficient heuristic algorithm of589 Grosso, Locatelli, and Pullan.590 560 */ 591 561 … … 617 587 high-level interface. 618 588 619 The currently supported solvers are \cite glpk, \cite clp, \cite cbc, 620 \cite cplex, \cite soplex. 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. 621 608 */ 622 609 … … 688 675 This group contains general \c EPS drawing methods and special 689 676 graph exporting tools. 690 691 \image html graph_to_eps.png692 677 */ 693 678
Note: See TracChangeset
for help on using the changeset viewer.