COIN-OR::LEMON - Graph Library

1 edited


  • doc/groups.dox

    r959 r1280  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2010
     5 * Copyright (C) 2003-2013
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
    113113detailed documentation of particular adaptors.
     115Since the adaptor classes conform to the \ref graph_concepts "graph concepts",
     116an adaptor can even be applied to another one.
     117The following image illustrates a situation when a \ref SubDigraph adaptor
     118is applied on a digraph and \ref Undirector is applied on the subgraph.
     120\image html adaptors2.png
     121\image latex adaptors2.eps "Using graph adaptors" width=\textwidth
    115123The behavior of graph adaptors can be very different. Some of them keep
    116124capabilities of the original graph while in other cases this would be
    289 @defgroup matrices Matrices
    290 @ingroup auxdat
    291 \brief Two dimensional data storages implemented in LEMON.
    293 This group contains two dimensional data storages implemented in LEMON.
    294 */
    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 \ref clrs01algorithms.
     312\cite clrs01algorithms.
    320320This group contains the algorithms for finding shortest paths in digraphs
    321 \ref clrs01algorithms.
     321\cite clrs01algorithms.
    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.
    333329 - \ref Suurballe A successive shortest path algorithm for finding
    334330   arc-disjoint paths between two nodes having minimum total length.
    342338This group contains the algorithms for finding minimum cost spanning
    343 trees and arborescences \ref clrs01algorithms.
     339trees and arborescences \cite clrs01algorithms.
    351347This group contains the algorithms for finding maximum flows and
    352 feasible circulations \ref clrs01algorithms, \ref amo93networkflows.
     348feasible circulations \cite clrs01algorithms, \cite amo93networkflows.
    354350The \e maximum \e flow \e problem is to find a flow of maximum value between
    364360\f[ 0 \leq f(uv) \leq cap(uv) \quad \forall uv\in A \f]
    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.
    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 Goldberg-Tarjan's
     363preflow push-relabel algorithm \cite goldberg88newapproach for finding
     364maximum flows. It also provides functions to query the minimum cut,
     365which is the dual problem of maximum flow.
    381367\ref Circulation is a preflow push-relabel algorithm implemented directly
    393379This group contains the algorithms for finding minimum cost flows and
    394 circulations \ref amo93networkflows. For more information about this
    395 problem and its dual solution, see \ref min_cost_flow
     380circulations \cite amo93networkflows. For more information about this
     381problem and its dual solution, see: \ref min_cost_flow
    396382"Minimum Cost Flow Problem".
    398384LEMON contains several algorithms for this problem.
    399385 - \ref NetworkSimplex Primal Network Simplex algorithm with various
    400    pivot strategies \ref dantzig63linearprog, \ref kellyoneill91netsimplex.
     386   pivot strategies \cite dantzig63linearprog, \cite kellyoneill91netsimplex.
    401387 - \ref CostScaling Cost Scaling algorithm based on push/augment and
    402    relabel operations \ref goldberg90approximation, \ref goldberg97efficient,
    403    \ref bunnagel98efficient.
     388   relabel operations \cite goldberg90approximation, \cite goldberg97efficient,
     389   \cite bunnagel98efficient.
    404390 - \ref CapacityScaling Capacity Scaling algorithm based on the successive
    405    shortest path method \ref edmondskarp72theoretical.
     391   shortest path method \cite edmondskarp72theoretical.
    406392 - \ref CycleCanceling Cycle-Canceling algorithms, two of which are
    407    strongly polynomial \ref klein67primal, \ref goldberg89cyclecanceling.
    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.
     395In general, \ref NetworkSimplex and \ref CostScaling are the most efficient
     397\ref NetworkSimplex is usually the fastest on relatively small graphs (up to
     398several thousands of nodes) and on dense graphs, while \ref CostScaling is
     399typically more efficient on large graphs (e.g. hundreds of thousands of
     400nodes or above), especially if they are sparse.
     401However, other algorithms could be faster in special cases.
    411402For 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).
     406These classes are intended to be used with integer-valued input data
     407(capacities, supply values, and costs), except for \ref CapacityScaling,
     408which is capable of handling real-valued arc costs (other numerical
     409data are required to be integer).
     411For more details about these implementations and for a comprehensive
     412experimental study, see the paper \cite KiralyKovacs12MCF.
     413It also compares these codes to other publicly available
     414minimum cost flow solvers.
    450452This group contains the algorithms for finding minimum mean cycles
    451 \ref clrs01algorithms, \ref amo93networkflows.
     453\cite amo93networkflows, \cite karp78characterization.
    453455The \e minimum \e mean \e cycle \e problem is to find a directed cycle
    466468LEMON 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.
    469470- \ref HartmannOrlinMmc Hartmann-Orlin's algorithm, which is an improved
    470   version of Karp's algorithm \ref dasdan98minmeancycle.
     471  version of Karp's algorithm \cite hartmann93finding.
    471472- \ref HowardMmc Howard's policy iteration algorithm
    472   \ref dasdan98minmeancycle.
    474 In practice, the \ref HowardMmc "Howard" algorithm proved to be by far the
     473  \cite dasdan98minmeancycle, \cite dasdan04experimental.
     475In practice, the \ref HowardMmc "Howard" algorithm turned out to be by far the
    475476most efficient one, though the best known theoretical bound on its running
    476477time is exponential.
    477478Both \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.
     479run in time O(nm) and use space O(n<sup>2</sup>+m).
    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.
    510500- \ref MaxMatching Edmond's blossom shrinking algorithm for calculating
    511501  maximum cardinality matching in general graphs.
    542 @defgroup planar Planarity Embedding and Drawing
     532@defgroup planar Planar Embedding and Drawing
    543533@ingroup algs
    544534\brief Algorithms for planarity checking, embedding and drawing
    554 @defgroup approx Approximation Algorithms
     544@defgroup tsp Traveling Salesman Problem
     545@ingroup algs
     546\brief Algorithms for the symmetric traveling salesman problem
     548This group contains basic heuristic algorithms for the the symmetric
     549\e traveling \e salesman \e problem (TSP).
     550Given an \ref FullGraph "undirected full graph" with a cost map on its edges,
     551the problem is to find a shortest possible tour that visits each node exactly
     552once (i.e. the minimum cost Hamiltonian cycle).
     554These 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.
     556Otherwise the algorithms could yield worse results.
     558LEMON 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
     565\ref NearestNeighborTsp, \ref GreedyTsp, and \ref InsertionTsp are the fastest
     566solution methods. Furthermore, \ref InsertionTsp is usually quite effective.
     568\ref ChristofidesTsp is somewhat slower, but it has the best guaranteed
     569approximation factor: 3/2.
     571\ref Opt2Tsp usually provides the best results in practice, but
     572it is the slowest method. It can also be used to improve given tours,
     573for example, the results of other algorithms.
     575\image html tsp.png
     576\image latex tsp.eps "Traveling salesman problem" width=\textwidth
     580@defgroup approx_algs Approximation Algorithms
    555581@ingroup algs
    556582\brief Approximation algorithms.
    558584This group contains the approximation and heuristic algorithms
    559585implemented in LEMON.
     587<b>Maximum Clique Problem</b>
     588  - \ref GrossoLocatelliPullanMc An efficient heuristic algorithm of
     589    Grosso, Locatelli, and Pullan.
    587617high-level interface.
    589 The currently supported solvers are \ref glpk, \ref clp, \ref cbc,
    590 \ref cplex, \ref soplex.
    591 */
    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.
    598 This group adds some helper tools to general optimization framework
    599 implemented in LEMON.
    600 */
    602 /**
    603 @defgroup metah Metaheuristics
    604 @ingroup gen_opt_group
    605 \brief Metaheuristics for LEMON library.
    607 This group contains some metaheuristic optimization tools.
     619The currently supported solvers are \cite glpk, \cite clp, \cite cbc,
     620\cite cplex, \cite soplex.
    675688This group contains general \c EPS drawing methods and special
    676689graph exporting tools.
     691\image html graph_to_eps.png
Note: See TracChangeset for help on using the changeset viewer.