COIN-OR::LEMON - Graph Library

Ignore:
Files:
2 edited

Legend:

Unmodified
Added
Removed
  • doc/groups.dox

    r710 r844  
    227227
    228228/**
    229 @defgroup matrices Matrices
    230 @ingroup datas
    231 \brief Two dimensional data storages implemented in LEMON.
    232 
    233 This group contains two dimensional data storages implemented in LEMON.
    234 */
    235 
    236 /**
    237229@defgroup paths Path Structures
    238230@ingroup datas
     
    284276This group contains the algorithms for finding shortest paths in digraphs.
    285277
    286  - \ref Dijkstra algorithm for finding shortest paths from a source node
    287    when all arc lengths are non-negative.
    288  - \ref BellmanFord "Bellman-Ford" algorithm for finding shortest paths
    289    from a source node when arc lenghts can be either positive or negative,
    290    but the digraph should not contain directed cycles with negative total
    291    length.
    292  - \ref FloydWarshall "Floyd-Warshall" and \ref Johnson "Johnson" algorithms
    293    for solving the \e all-pairs \e shortest \e paths \e problem when arc
    294    lenghts can be either positive or negative, but the digraph should
    295    not contain directed cycles with negative total length.
     278 - \ref Dijkstra Dijkstra's algorithm for finding shortest paths from a
     279   source node when all arc lengths are non-negative.
    296280 - \ref Suurballe A successive shortest path algorithm for finding
    297281   arc-disjoint paths between two nodes having minimum total length.
     
    318302\f[ 0 \leq f(uv) \leq cap(uv) \quad \forall uv\in A \f]
    319303
    320 LEMON contains several algorithms for solving maximum flow problems:
    321 - \ref EdmondsKarp Edmonds-Karp algorithm.
    322 - \ref Preflow Goldberg-Tarjan's preflow push-relabel algorithm.
    323 - \ref DinitzSleatorTarjan Dinitz's blocking flow algorithm with dynamic trees.
    324 - \ref GoldbergTarjan Preflow push-relabel algorithm with dynamic trees.
    325 
    326 In most cases the \ref Preflow "Preflow" algorithm provides the
    327 fastest method for computing a maximum flow. All implementations
    328 also provide functions to query the minimum cut, which is the dual
    329 problem of maximum flow.
     304\ref Preflow implements the preflow push-relabel algorithm of Goldberg and
     305Tarjan for solving this problem. It also provides functions to query the
     306minimum cut, which is the dual problem of maximum flow.
     307
    330308
    331309\ref Circulation is a preflow push-relabel algorithm implemented directly
     
    345323solution see \ref min_cost_flow "Minimum Cost Flow Problem".
    346324
    347 LEMON contains several algorithms for this problem.
    348  - \ref NetworkSimplex Primal Network Simplex algorithm with various
    349    pivot strategies.
    350  - \ref CostScaling Push-Relabel and Augment-Relabel algorithms based on
    351    cost scaling.
    352  - \ref CapacityScaling Successive Shortest %Path algorithm with optional
    353    capacity scaling.
    354  - \ref CancelAndTighten The Cancel and Tighten algorithm.
    355  - \ref CycleCanceling Cycle-Canceling algorithms.
    356 
    357 In general NetworkSimplex is the most efficient implementation,
    358 but in special cases other algorithms could be faster.
    359 For example, if the total supply and/or capacities are rather small,
    360 CapacityScaling is usually the fastest algorithm (without effective scaling).
     325\ref NetworkSimplex is an efficient implementation of the primal Network
     326Simplex algorithm for finding minimum cost flows. It also provides dual
     327solution (node potentials), if an optimal flow is found.
    361328*/
    362329
     
    382349- \ref HaoOrlin "Hao-Orlin algorithm" for calculating minimum cut
    383350  in directed graphs.
    384 - \ref NagamochiIbaraki "Nagamochi-Ibaraki algorithm" for
    385   calculating minimum cut in undirected graphs.
    386351- \ref GomoryHu "Gomory-Hu tree computation" for calculating
    387352  all-pairs minimum cut in undirected graphs.
     
    404369
    405370/**
    406 @defgroup planar Planarity Embedding and Drawing
    407 @ingroup algs
    408 \brief Algorithms for planarity checking, embedding and drawing
    409 
    410 This group contains the algorithms for planarity checking,
    411 embedding and drawing.
    412 
    413 \image html planar.png
    414 \image latex planar.eps "Plane graph" width=\textwidth
    415 */
    416 
    417 /**
    418371@defgroup matching Matching Algorithms
    419372@ingroup algs
    420373\brief Algorithms for finding matchings in graphs and bipartite graphs.
    421374
    422 This group contains the algorithms for calculating
    423 matchings in graphs and bipartite graphs. The general matching problem is
    424 finding a subset of the edges for which each node has at most one incident
    425 edge.
     375This group contains the algorithms for calculating matchings in graphs.
     376The general matching problem is finding a subset of the edges for which
     377each node has at most one incident edge.
    426378
    427379There are several different algorithms for calculate matchings in
    428 graphs.  The matching problems in bipartite graphs are generally
    429 easier than in general graphs. The goal of the matching optimization
     380graphs. The goal of the matching optimization
    430381can be finding maximum cardinality, maximum weight or minimum cost
    431382matching. The search can be constrained to find perfect or
     
    433384
    434385The matching algorithms implemented in LEMON:
    435 - \ref MaxBipartiteMatching Hopcroft-Karp augmenting path algorithm
    436   for calculating maximum cardinality matching in bipartite graphs.
    437 - \ref PrBipartiteMatching Push-relabel algorithm
    438   for calculating maximum cardinality matching in bipartite graphs.
    439 - \ref MaxWeightedBipartiteMatching
    440   Successive shortest path algorithm for calculating maximum weighted
    441   matching and maximum weighted bipartite matching in bipartite graphs.
    442 - \ref MinCostMaxBipartiteMatching
    443   Successive shortest path algorithm for calculating minimum cost maximum
    444   matching in bipartite graphs.
    445386- \ref MaxMatching Edmond's blossom shrinking algorithm for calculating
    446387  maximum cardinality matching in general graphs.
     
    474415
    475416/**
    476 @defgroup approx Approximation Algorithms
    477 @ingroup algs
    478 \brief Approximation algorithms.
    479 
    480 This group contains the approximation and heuristic algorithms
    481 implemented in LEMON.
    482 */
    483 
    484 /**
    485417@defgroup gen_opt_group General Optimization Tools
    486418\brief This group contains some general optimization frameworks
     
    499431various LP solvers could be used in the same manner with this
    500432interface.
    501 */
    502 
    503 /**
    504 @defgroup lp_utils Tools for Lp and Mip Solvers
    505 @ingroup lp_group
    506 \brief Helper tools to the Lp and Mip solvers.
    507 
    508 This group adds some helper tools to general optimization framework
    509 implemented in LEMON.
    510 */
    511 
    512 /**
    513 @defgroup metah Metaheuristics
    514 @ingroup gen_opt_group
    515 \brief Metaheuristics for LEMON library.
    516 
    517 This group contains some metaheuristic optimization tools.
    518433*/
    519434
  • lemon/suurballe.h

    r670 r843  
    4646  /// Note that this problem is a special case of the \ref min_cost_flow
    4747  /// "minimum cost flow problem". This implementation is actually an
    48   /// efficient specialized version of the \ref CapacityScaling
    49   /// "Successive Shortest Path" algorithm directly for this problem.
     48  /// efficient specialized version of the Successive Shortest Path
     49  /// algorithm directly for this problem.
    5050  /// Therefore this class provides query functions for flow values and
    5151  /// node potentials (the dual solution) just like the minimum cost flow
Note: See TracChangeset for help on using the changeset viewer.