COIN-OR::LEMON - Graph Library

Ignore:
Files:
2 edited

Legend:

Unmodified
Added
Removed
  • doc/groups.dox

    r844 r710  
    227227
    228228/**
     229@defgroup matrices Matrices
     230@ingroup datas
     231\brief Two dimensional data storages implemented in LEMON.
     232
     233This group contains two dimensional data storages implemented in LEMON.
     234*/
     235
     236/**
    229237@defgroup paths Path Structures
    230238@ingroup datas
     
    276284This group contains the algorithms for finding shortest paths in digraphs.
    277285
    278  - \ref Dijkstra Dijkstra's algorithm for finding shortest paths from a
    279    source node when all arc lengths are non-negative.
     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.
    280296 - \ref Suurballe A successive shortest path algorithm for finding
    281297   arc-disjoint paths between two nodes having minimum total length.
     
    302318\f[ 0 \leq f(uv) \leq cap(uv) \quad \forall uv\in A \f]
    303319
    304 \ref Preflow implements the preflow push-relabel algorithm of Goldberg and
    305 Tarjan for solving this problem. It also provides functions to query the
    306 minimum cut, which is the dual problem of maximum flow.
    307 
     320LEMON 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
     326In most cases the \ref Preflow "Preflow" algorithm provides the
     327fastest method for computing a maximum flow. All implementations
     328also provide functions to query the minimum cut, which is the dual
     329problem of maximum flow.
    308330
    309331\ref Circulation is a preflow push-relabel algorithm implemented directly
     
    323345solution see \ref min_cost_flow "Minimum Cost Flow Problem".
    324346
    325 \ref NetworkSimplex is an efficient implementation of the primal Network
    326 Simplex algorithm for finding minimum cost flows. It also provides dual
    327 solution (node potentials), if an optimal flow is found.
     347LEMON 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
     357In general NetworkSimplex is the most efficient implementation,
     358but in special cases other algorithms could be faster.
     359For example, if the total supply and/or capacities are rather small,
     360CapacityScaling is usually the fastest algorithm (without effective scaling).
    328361*/
    329362
     
    349382- \ref HaoOrlin "Hao-Orlin algorithm" for calculating minimum cut
    350383  in directed graphs.
     384- \ref NagamochiIbaraki "Nagamochi-Ibaraki algorithm" for
     385  calculating minimum cut in undirected graphs.
    351386- \ref GomoryHu "Gomory-Hu tree computation" for calculating
    352387  all-pairs minimum cut in undirected graphs.
     
    369404
    370405/**
     406@defgroup planar Planarity Embedding and Drawing
     407@ingroup algs
     408\brief Algorithms for planarity checking, embedding and drawing
     409
     410This group contains the algorithms for planarity checking,
     411embedding and drawing.
     412
     413\image html planar.png
     414\image latex planar.eps "Plane graph" width=\textwidth
     415*/
     416
     417/**
    371418@defgroup matching Matching Algorithms
    372419@ingroup algs
    373420\brief Algorithms for finding matchings in graphs and bipartite graphs.
    374421
    375 This group contains the algorithms for calculating matchings in graphs.
    376 The general matching problem is finding a subset of the edges for which
    377 each node has at most one incident edge.
     422This group contains the algorithms for calculating
     423matchings in graphs and bipartite graphs. The general matching problem is
     424finding a subset of the edges for which each node has at most one incident
     425edge.
    378426
    379427There are several different algorithms for calculate matchings in
    380 graphs. The goal of the matching optimization
     428graphs.  The matching problems in bipartite graphs are generally
     429easier than in general graphs. The goal of the matching optimization
    381430can be finding maximum cardinality, maximum weight or minimum cost
    382431matching. The search can be constrained to find perfect or
     
    384433
    385434The 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.
    386445- \ref MaxMatching Edmond's blossom shrinking algorithm for calculating
    387446  maximum cardinality matching in general graphs.
     
    415474
    416475/**
     476@defgroup approx Approximation Algorithms
     477@ingroup algs
     478\brief Approximation algorithms.
     479
     480This group contains the approximation and heuristic algorithms
     481implemented in LEMON.
     482*/
     483
     484/**
    417485@defgroup gen_opt_group General Optimization Tools
    418486\brief This group contains some general optimization frameworks
     
    431499various LP solvers could be used in the same manner with this
    432500interface.
     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
     508This group adds some helper tools to general optimization framework
     509implemented in LEMON.
     510*/
     511
     512/**
     513@defgroup metah Metaheuristics
     514@ingroup gen_opt_group
     515\brief Metaheuristics for LEMON library.
     516
     517This group contains some metaheuristic optimization tools.
    433518*/
    434519
  • lemon/suurballe.h

    r843 r670  
    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 Successive Shortest Path
    49   /// algorithm directly for this problem.
     48  /// efficient specialized version of the \ref CapacityScaling
     49  /// "Successive Shortest Path" 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.