COIN-OR::LEMON - Graph Library

Changeset 884:3ed8f7c8bed8 in lemon-1.2


Ignore:
Timestamp:
03/18/10 14:50:32 (14 years ago)
Author:
Alpar Juttner <alpar@…>
Branch:
1.2
Parents:
882:7af2ae7c1428 (diff), 883:87569cb5734d (diff)
Note: this is a merge changeset, the changes displayed below correspond to the merge itself.
Use the (diff) links above to see all the changes relative to each parent.
Phase:
public
Tags:
r1.2
Message:

Merge #341, #360, #51, #359 to branch 1.2

Files:
2 edited

Legend:

Unmodified
Added
Removed
  • doc/groups.dox

    r882 r884  
    264264
    265265/**
    266 @defgroup matrices Matrices
    267 @ingroup datas
    268 \brief Two dimensional data storages implemented in LEMON.
    269 
    270 This group contains two dimensional data storages implemented in LEMON.
    271 */
    272 
    273 /**
    274266@defgroup auxdat Auxiliary Data Structures
    275267@ingroup datas
     
    449441
    450442LEMON contains three algorithms for solving the minimum mean cycle problem:
    451 - \ref Karp "Karp"'s original algorithm \ref amo93networkflows,
     443- \ref KarpMmc Karp's original algorithm \ref amo93networkflows,
    452444  \ref dasdan98minmeancycle.
    453 - \ref HartmannOrlin "Hartmann-Orlin"'s algorithm, which is an improved
     445- \ref HartmannOrlinMmc Hartmann-Orlin's algorithm, which is an improved
    454446  version of Karp's algorithm \ref dasdan98minmeancycle.
    455 - \ref Howard "Howard"'s policy iteration algorithm
     447- \ref HowardMmc Howard's policy iteration algorithm
    456448  \ref dasdan98minmeancycle.
    457449
    458 In practice, the Howard algorithm proved to be by far the most efficient
    459 one, though the best known theoretical bound on its running time is
    460 exponential.
    461 Both Karp and HartmannOrlin algorithms run in time O(ne) and use space
    462 O(n<sup>2</sup>+e), but the latter one is typically faster due to the
    463 applied early termination scheme.
     450In practice, the \ref HowardMmc "Howard" algorithm proved to be by far the
     451most efficient one, though the best known theoretical bound on its running
     452time is exponential.
     453Both \ref KarpMmc "Karp" and \ref HartmannOrlinMmc "Hartmann-Orlin" algorithms
     454run in time O(ne) and use space O(n<sup>2</sup>+e), but the latter one is
     455typically faster due to the applied early termination scheme.
    464456*/
    465457
  • doc/groups.dox

    r880 r884  
    287287
    288288/**
    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 /**
    297289@defgroup algs Algorithms
    298290\brief This group contains the several algorithms
     
    327319   but the digraph should not contain directed cycles with negative total
    328320   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.
    333321 - \ref Suurballe A successive shortest path algorithm for finding
    334322   arc-disjoint paths between two nodes having minimum total length.
     
    364352\f[ 0 \leq f(uv) \leq cap(uv) \quad \forall uv\in A \f]
    365353
    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.
     354\ref Preflow is an efficient implementation of Goldberg-Tarjan's
     355preflow push-relabel algorithm \ref goldberg88newapproach for finding
     356maximum flows. It also provides functions to query the minimum cut,
     357which is the dual problem of maximum flow.
    380358
    381359\ref Circulation is a preflow push-relabel algorithm implemented directly
     
    434412- \ref HaoOrlin "Hao-Orlin algorithm" for calculating minimum cut
    435413  in directed graphs.
    436 - \ref NagamochiIbaraki "Nagamochi-Ibaraki algorithm" for
    437   calculating minimum cut in undirected graphs.
    438414- \ref GomoryHu "Gomory-Hu tree computation" for calculating
    439415  all-pairs minimum cut in undirected graphs.
     
    498474
    499475The 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.
    510476- \ref MaxMatching Edmond's blossom shrinking algorithm for calculating
    511477  maximum cardinality matching in general graphs.
     
    552518
    553519/**
    554 @defgroup approx Approximation Algorithms
    555 @ingroup algs
    556 \brief Approximation algorithms.
    557 
    558 This group contains the approximation and heuristic algorithms
    559 implemented in LEMON.
    560 */
    561 
    562 /**
    563520@defgroup auxalg Auxiliary Algorithms
    564521@ingroup algs
     
    589546The currently supported solvers are \ref glpk, \ref clp, \ref cbc,
    590547\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.
    608548*/
    609549
Note: See TracChangeset for help on using the changeset viewer.