COIN-OR::LEMON - Graph Library

Ignore:
Timestamp:
01/30/12 23:24:40 (8 years ago)
Author:
Peter Kovacs <kpeter@…>
Branch:
default
Phase:
public
Message:

Doc improvements for min cost flow algorithms (#437)

File:
1 edited

Legend:

Unmodified
Added
Removed
  • lemon/cycle_canceling.h

    r1026 r1165  
    4949  /// \ref amo93networkflows, \ref klein67primal,
    5050  /// \ref goldberg89cyclecanceling.
    51   /// The most efficent one (both theoretically and practically)
    52   /// is the \ref CANCEL_AND_TIGHTEN "Cancel and Tighten" algorithm,
    53   /// thus it is the default method.
    54   /// It is strongly polynomial, but in practice, it is typically much
    55   /// slower than the scaling algorithms and NetworkSimplex.
     51  /// The most efficent one is the \ref CANCEL_AND_TIGHTEN
     52  /// "Cancel-and-Tighten" algorithm, thus it is the default method.
     53  /// It runs in strongly polynomial time, but in practice, it is typically
     54  /// orders of magnitude slower than the scaling algorithms and
     55  /// \ref NetworkSimplex.
     56  /// (For more information, see \ref min_cost_flow_algs "the module page".)
    5657  ///
    5758  /// Most of the parameters of the problem (except for the digraph)
     
    117118    ///
    118119    /// \ref CycleCanceling provides three different cycle-canceling
    119     /// methods. By default, \ref CANCEL_AND_TIGHTEN "Cancel and Tighten"
     120    /// methods. By default, \ref CANCEL_AND_TIGHTEN "Cancel-and-Tighten"
    120121    /// is used, which is by far the most efficient and the most robust.
    121122    /// However, the other methods can be selected using the \ref run()
     
    123124    enum Method {
    124125      /// A simple cycle-canceling method, which uses the
    125       /// \ref BellmanFord "Bellman-Ford" algorithm with limited iteration
    126       /// number for detecting negative cycles in the residual network.
     126      /// \ref BellmanFord "Bellman-Ford" algorithm for detecting negative
     127      /// cycles in the residual network.
     128      /// The number of Bellman-Ford iterations is bounded by a successively
     129      /// increased limit.
    127130      SIMPLE_CYCLE_CANCELING,
    128131      /// The "Minimum Mean Cycle-Canceling" algorithm, which is a
     
    130133      /// \ref goldberg89cyclecanceling. It improves along a
    131134      /// \ref min_mean_cycle "minimum mean cycle" in each iteration.
    132       /// Its running time complexity is O(n<sup>2</sup>m<sup>3</sup>log(n)).
     135      /// Its running time complexity is O(n<sup>2</sup>e<sup>3</sup>log(n)).
    133136      MINIMUM_MEAN_CYCLE_CANCELING,
    134       /// The "Cancel And Tighten" algorithm, which can be viewed as an
     137      /// The "Cancel-and-Tighten" algorithm, which can be viewed as an
    135138      /// improved version of the previous method
    136139      /// \ref goldberg89cyclecanceling.
    137140      /// It is faster both in theory and in practice, its running time
    138       /// complexity is O(n<sup>2</sup>m<sup>2</sup>log(n)).
     141      /// complexity is O(n<sup>2</sup>e<sup>2</sup>log(n)).
    139142      CANCEL_AND_TIGHTEN
    140143    };
     
    611614    }
    612615
    613     /// \brief Return the flow map (the primal solution).
     616    /// \brief Copy the flow values (the primal solution) into the
     617    /// given map.
    614618    ///
    615619    /// This function copies the flow value on each arc into the given
     
    635639    }
    636640
    637     /// \brief Return the potential map (the dual solution).
     641    /// \brief Copy the potential values (the dual solution) into the
     642    /// given map.
    638643    ///
    639644    /// This function copies the potential (dual value) of each node
     
    955960    }
    956961
    957     // Execute the "Cancel And Tighten" method
     962    // Execute the "Cancel-and-Tighten" method
    958963    void startCancelAndTighten() {
    959964      // Constants for the min mean cycle computations
Note: See TracChangeset for help on using the changeset viewer.