Changes in doc/groups.dox [959:38213abd2911:1271:fb1c7da561ce] in lemon
- File:
-
- 1 edited
Legend:
- Unmodified
- Added
- Removed
-
doc/groups.dox
r959 r1271 3 3 * This file is a part of LEMON, a generic C++ optimization library. 4 4 * 5 * Copyright (C) 2003-201 05 * Copyright (C) 2003-2013 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 … … 310 318 This group contains the common graph search algorithms, namely 311 319 \e breadth-first \e search (BFS) and \e depth-first \e search (DFS) 312 \ refclrs01algorithms.320 \cite clrs01algorithms. 313 321 */ 314 322 … … 319 327 320 328 This group contains the algorithms for finding shortest paths in digraphs 321 \ refclrs01algorithms.329 \cite clrs01algorithms. 322 330 323 331 - \ref Dijkstra algorithm for finding shortest paths from a source node … … 341 349 342 350 This group contains the algorithms for finding minimum cost spanning 343 trees and arborescences \ refclrs01algorithms.351 trees and arborescences \cite clrs01algorithms. 344 352 */ 345 353 … … 350 358 351 359 This group contains the algorithms for finding maximum flows and 352 feasible circulations \ ref clrs01algorithms, \refamo93networkflows.360 feasible circulations \cite clrs01algorithms, \cite amo93networkflows. 353 361 354 362 The \e maximum \e flow \e problem is to find a flow of maximum value between … … 366 374 LEMON contains several algorithms for solving maximum flow problems: 367 375 - \ref EdmondsKarp Edmonds-Karp algorithm 368 \ refedmondskarp72theoretical.376 \cite edmondskarp72theoretical. 369 377 - \ref Preflow Goldberg-Tarjan's preflow push-relabel algorithm 370 \ refgoldberg88newapproach.378 \cite goldberg88newapproach. 371 379 - \ref DinitzSleatorTarjan Dinitz's blocking flow algorithm with dynamic trees 372 \ ref dinic70algorithm, \refsleator83dynamic.380 \cite dinic70algorithm, \cite sleator83dynamic. 373 381 - \ref GoldbergTarjan !Preflow push-relabel algorithm with dynamic trees 374 \ ref goldberg88newapproach, \refsleator83dynamic.382 \cite goldberg88newapproach, \cite sleator83dynamic. 375 383 376 384 In most cases the \ref Preflow algorithm provides the … … 392 400 393 401 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_flow402 circulations \cite amo93networkflows. For more information about this 403 problem and its dual solution, see: \ref min_cost_flow 396 404 "Minimum Cost Flow Problem". 397 405 398 406 LEMON contains several algorithms for this problem. 399 407 - \ref NetworkSimplex Primal Network Simplex algorithm with various 400 pivot strategies \ ref dantzig63linearprog, \refkellyoneill91netsimplex.408 pivot strategies \cite dantzig63linearprog, \cite kellyoneill91netsimplex. 401 409 - \ref CostScaling Cost Scaling algorithm based on push/augment and 402 relabel operations \ ref goldberg90approximation, \refgoldberg97efficient,403 \ refbunnagel98efficient.410 relabel operations \cite goldberg90approximation, \cite goldberg97efficient, 411 \cite bunnagel98efficient. 404 412 - \ref CapacityScaling Capacity Scaling algorithm based on the successive 405 shortest path method \ refedmondskarp72theoretical.413 shortest path method \cite edmondskarp72theoretical. 406 414 - \ref CycleCanceling Cycle-Canceling 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. 415 strongly polynomial \cite klein67primal, \cite goldberg89cyclecanceling. 416 417 In general, \ref NetworkSimplex and \ref CostScaling are the most efficient 418 implementations. 419 \ref NetworkSimplex is usually the fastest on relatively small graphs (up to 420 several thousands of nodes) and on dense graphs, while \ref CostScaling is 421 typically more efficient on large graphs (e.g. hundreds of thousands of 422 nodes or above), especially if they are sparse. 423 However, other algorithms could be faster in special cases. 411 424 For example, if the total supply and/or capacities are rather small, 412 CapacityScaling is usually the fastest algorithm (without effective scaling). 425 \ref CapacityScaling is usually the fastest algorithm 426 (without effective scaling). 427 428 These classes are intended to be used with integer-valued input data 429 (capacities, supply values, and costs), except for \ref CapacityScaling, 430 which is capable of handling real-valued arc costs (other numerical 431 data are required to be integer). 432 433 For more details about these implementations and for a comprehensive 434 experimental study, see the paper \cite KiralyKovacs12MCF. 435 It also compares these codes to other publicly available 436 minimum cost flow solvers. 413 437 */ 414 438 … … 449 473 450 474 This group contains the algorithms for finding minimum mean cycles 451 \ ref clrs01algorithms, \ref amo93networkflows.475 \cite amo93networkflows, \cite karp78characterization. 452 476 453 477 The \e minimum \e mean \e cycle \e problem is to find a directed cycle … … 465 489 466 490 LEMON contains three algorithms for solving the minimum mean cycle problem: 467 - \ref KarpMmc Karp's original algorithm \ref amo93networkflows, 468 \ref dasdan98minmeancycle. 491 - \ref KarpMmc Karp's original algorithm \cite karp78characterization. 469 492 - \ref HartmannOrlinMmc Hartmann-Orlin's algorithm, which is an improved 470 version of Karp's algorithm \ ref dasdan98minmeancycle.493 version of Karp's algorithm \cite hartmann93finding. 471 494 - \ref HowardMmc Howard's policy iteration algorithm 472 \ ref dasdan98minmeancycle.473 474 In practice, the \ref HowardMmc "Howard" algorithm provedto be by far the495 \cite dasdan98minmeancycle, \cite dasdan04experimental. 496 497 In practice, the \ref HowardMmc "Howard" algorithm turned out to be by far the 475 498 most efficient one, though the best known theoretical bound on its running 476 499 time is exponential. 477 500 Both \ref KarpMmc "Karp" and \ref HartmannOrlinMmc "Hartmann-Orlin" 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. 501 run in time O(nm) and use space O(n<sup>2</sup>+m). 480 502 */ 481 503 … … 540 562 541 563 /** 542 @defgroup planar Planar ityEmbedding and Drawing564 @defgroup planar Planar Embedding and Drawing 543 565 @ingroup algs 544 566 \brief Algorithms for planarity checking, embedding and drawing … … 552 574 553 575 /** 554 @defgroup approx Approximation Algorithms 576 @defgroup tsp Traveling Salesman Problem 577 @ingroup algs 578 \brief Algorithms for the symmetric traveling salesman problem 579 580 This group contains basic heuristic algorithms for the the symmetric 581 \e traveling \e salesman \e problem (TSP). 582 Given an \ref FullGraph "undirected full graph" with a cost map on its edges, 583 the problem is to find a shortest possible tour that visits each node exactly 584 once (i.e. the minimum cost Hamiltonian cycle). 585 586 These TSP algorithms are intended to be used with a \e metric \e cost 587 \e function, i.e. the edge costs should satisfy the triangle inequality. 588 Otherwise the algorithms could yield worse results. 589 590 LEMON provides five well-known heuristics for solving symmetric TSP: 591 - \ref NearestNeighborTsp Neareast neighbor algorithm 592 - \ref GreedyTsp Greedy algorithm 593 - \ref InsertionTsp Insertion heuristic (with four selection methods) 594 - \ref ChristofidesTsp Christofides algorithm 595 - \ref Opt2Tsp 2-opt algorithm 596 597 \ref NearestNeighborTsp, \ref GreedyTsp, and \ref InsertionTsp are the fastest 598 solution methods. Furthermore, \ref InsertionTsp is usually quite effective. 599 600 \ref ChristofidesTsp is somewhat slower, but it has the best guaranteed 601 approximation factor: 3/2. 602 603 \ref Opt2Tsp usually provides the best results in practice, but 604 it is the slowest method. It can also be used to improve given tours, 605 for example, the results of other algorithms. 606 607 \image html tsp.png 608 \image latex tsp.eps "Traveling salesman problem" width=\textwidth 609 */ 610 611 /** 612 @defgroup approx_algs Approximation Algorithms 555 613 @ingroup algs 556 614 \brief Approximation algorithms. … … 558 616 This group contains the approximation and heuristic algorithms 559 617 implemented in LEMON. 618 619 <b>Maximum Clique Problem</b> 620 - \ref GrossoLocatelliPullanMc An efficient heuristic algorithm of 621 Grosso, Locatelli, and Pullan. 560 622 */ 561 623 … … 587 649 high-level interface. 588 650 589 The currently supported solvers are \ ref glpk, \ref clp, \refcbc,590 \ ref cplex, \refsoplex.651 The currently supported solvers are \cite glpk, \cite clp, \cite cbc, 652 \cite cplex, \cite soplex. 591 653 */ 592 654 … … 675 737 This group contains general \c EPS drawing methods and special 676 738 graph exporting tools. 739 740 \image html graph_to_eps.png 677 741 */ 678 742
Note: See TracChangeset
for help on using the changeset viewer.