COIN-OR::LEMON - Graph Library

Ignore:
File:
1 edited

Legend:

Unmodified
Added
Removed
  • doc/groups.dox

    r1280 r959  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2013
     5 * Copyright (C) 2003-2010
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
     
    113113detailed documentation of particular adaptors.
    114114
    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 
    123115The behavior of graph adaptors can be very different. Some of them keep
    124116capabilities of the original graph while in other cases this would be
     
    295287
    296288/**
     289@defgroup matrices Matrices
     290@ingroup auxdat
     291\brief Two dimensional data storages implemented in LEMON.
     292
     293This group contains two dimensional data storages implemented in LEMON.
     294*/
     295
     296/**
    297297@defgroup algs Algorithms
    298298\brief This group contains the several algorithms
     
    310310This group contains the common graph search algorithms, namely
    311311\e breadth-first \e search (BFS) and \e depth-first \e search (DFS)
    312 \cite clrs01algorithms.
     312\ref clrs01algorithms.
    313313*/
    314314
     
    319319
    320320This group contains the algorithms for finding shortest paths in digraphs
    321 \cite clrs01algorithms.
     321\ref clrs01algorithms.
    322322
    323323 - \ref Dijkstra algorithm for finding shortest paths from a source node
     
    327327   but the digraph should not contain directed cycles with negative total
    328328   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.
    329333 - \ref Suurballe A successive shortest path algorithm for finding
    330334   arc-disjoint paths between two nodes having minimum total length.
     
    337341
    338342This group contains the algorithms for finding minimum cost spanning
    339 trees and arborescences \cite clrs01algorithms.
     343trees and arborescences \ref clrs01algorithms.
    340344*/
    341345
     
    346350
    347351This group contains the algorithms for finding maximum flows and
    348 feasible circulations \cite clrs01algorithms, \cite amo93networkflows.
     352feasible circulations \ref clrs01algorithms, \ref amo93networkflows.
    349353
    350354The \e maximum \e flow \e problem is to find a flow of maximum value between
     
    360364\f[ 0 \leq f(uv) \leq cap(uv) \quad \forall uv\in A \f]
    361365
    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.
     366LEMON 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
     376In most cases the \ref Preflow algorithm provides the
     377fastest method for computing a maximum flow. All implementations
     378also provide functions to query the minimum cut, which is the dual
     379problem of maximum flow.
    366380
    367381\ref Circulation is a preflow push-relabel algorithm implemented directly
     
    378392
    379393This group contains the algorithms for finding minimum cost flows and
    380 circulations \cite amo93networkflows. For more information about this
    381 problem and its dual solution, see: \ref min_cost_flow
     394circulations \ref amo93networkflows. For more information about this
     395problem and its dual solution, see \ref min_cost_flow
    382396"Minimum Cost Flow Problem".
    383397
    384398LEMON contains several algorithms for this problem.
    385399 - \ref NetworkSimplex Primal Network Simplex algorithm with various
    386    pivot strategies \cite dantzig63linearprog, \cite kellyoneill91netsimplex.
     400   pivot strategies \ref dantzig63linearprog, \ref kellyoneill91netsimplex.
    387401 - \ref CostScaling Cost Scaling algorithm based on push/augment and
    388    relabel operations \cite goldberg90approximation, \cite goldberg97efficient,
    389    \cite bunnagel98efficient.
     402   relabel operations \ref goldberg90approximation, \ref goldberg97efficient,
     403   \ref bunnagel98efficient.
    390404 - \ref CapacityScaling Capacity Scaling algorithm based on the successive
    391    shortest path method \cite edmondskarp72theoretical.
     405   shortest path method \ref edmondskarp72theoretical.
    392406 - \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
     409In general NetworkSimplex is the most efficient implementation,
     410but in special cases other algorithms could be faster.
    402411For 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.
     412CapacityScaling is usually the fastest algorithm (without effective scaling).
    415413*/
    416414
     
    451449
    452450This group contains the algorithms for finding minimum mean cycles
    453 \cite amo93networkflows, \cite karp78characterization.
     451\ref clrs01algorithms, \ref amo93networkflows.
    454452
    455453The \e minimum \e mean \e cycle \e problem is to find a directed cycle
     
    467465
    468466LEMON 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.
    470469- \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.
    472471- \ref HowardMmc Howard's policy iteration algorithm
    473   \cite dasdan98minmeancycle, \cite dasdan04experimental.
    474 
    475 In practice, the \ref HowardMmc "Howard" algorithm turned out to be by far the
     472  \ref dasdan98minmeancycle.
     473
     474In practice, the \ref HowardMmc "Howard" algorithm proved to be by far the
    476475most efficient one, though the best known theoretical bound on its running
    477476time is exponential.
    478477Both \ref KarpMmc "Karp" and \ref HartmannOrlinMmc "Hartmann-Orlin" algorithms
    479 run in time O(nm) and use space O(n<sup>2</sup>+m).
     478run in time O(ne) and use space O(n<sup>2</sup>+e), but the latter one is
     479typically faster due to the applied early termination scheme.
    480480*/
    481481
     
    498498
    499499The 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.
    500510- \ref MaxMatching Edmond's blossom shrinking algorithm for calculating
    501511  maximum cardinality matching in general graphs.
     
    530540
    531541/**
    532 @defgroup planar Planar Embedding and Drawing
     542@defgroup planar Planarity Embedding and Drawing
    533543@ingroup algs
    534544\brief Algorithms for planarity checking, embedding and drawing
     
    542552
    543553/**
    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
    581555@ingroup algs
    582556\brief Approximation algorithms.
     
    584558This group contains the approximation and heuristic algorithms
    585559implemented in LEMON.
    586 
    587 <b>Maximum Clique Problem</b>
    588   - \ref GrossoLocatelliPullanMc An efficient heuristic algorithm of
    589     Grosso, Locatelli, and Pullan.
    590560*/
    591561
     
    617587high-level interface.
    618588
    619 The currently supported solvers are \cite glpk, \cite clp, \cite cbc,
    620 \cite cplex, \cite soplex.
     589The 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
     598This group adds some helper tools to general optimization framework
     599implemented in LEMON.
     600*/
     601
     602/**
     603@defgroup metah Metaheuristics
     604@ingroup gen_opt_group
     605\brief Metaheuristics for LEMON library.
     606
     607This group contains some metaheuristic optimization tools.
    621608*/
    622609
     
    688675This group contains general \c EPS drawing methods and special
    689676graph exporting tools.
    690 
    691 \image html graph_to_eps.png
    692677*/
    693678
Note: See TracChangeset for help on using the changeset viewer.