COIN-OR::LEMON - Graph Library

Changeset 1165:16f55008c863 in lemon for lemon


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)

Location:
lemon
Files:
4 edited

Legend:

Unmodified
Added
Removed
  • lemon/capacity_scaling.h

    r1026 r1165  
    7070  /// \ref edmondskarp72theoretical. It is an efficient dual
    7171  /// solution method.
     72  ///
     73  /// This algorithm is typically slower than \ref CostScaling and
     74  /// \ref NetworkSimplex, but in special cases, it can be more
     75  /// efficient than them.
     76  /// (For more information, see \ref min_cost_flow_algs "the module page".)
    7277  ///
    7378  /// Most of the parameters of the problem (except for the digraph)
     
    677682    }
    678683
    679     /// \brief Return the flow map (the primal solution).
     684    /// \brief Copy the flow values (the primal solution) into the
     685    /// given map.
    680686    ///
    681687    /// This function copies the flow value on each arc into the given
     
    701707    }
    702708
    703     /// \brief Return the potential map (the dual solution).
     709    /// \brief Copy the potential values (the dual solution) into the
     710    /// given map.
    704711    ///
    705712    /// This function copies the potential (dual value) of each node
  • lemon/cost_scaling.h

    r1049 r1165  
    9999  ///
    100100  /// In general, \ref NetworkSimplex and \ref CostScaling are the fastest
    101   /// implementations available in LEMON for this problem.
     101  /// implementations available in LEMON for solving this problem.
     102  /// (For more information, see \ref min_cost_flow_algs "the module page".)
    102103  ///
    103104  /// Most of the parameters of the problem (except for the digraph)
     
    705706    }
    706707
    707     /// \brief Return the flow map (the primal solution).
     708    /// \brief Copy the flow values (the primal solution) into the
     709    /// given map.
    708710    ///
    709711    /// This function copies the flow value on each arc into the given
     
    729731    }
    730732
    731     /// \brief Return the potential map (the dual solution).
     733    /// \brief Copy the potential values (the dual solution) into the
     734    /// given map.
    732735    ///
    733736    /// This function copies the potential (dual value) of each node
  • 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
  • lemon/network_simplex.h

    r1026 r1165  
    4949  ///
    5050  /// In general, \ref NetworkSimplex and \ref CostScaling are the fastest
    51   /// implementations available in LEMON for this problem.
     51  /// implementations available in LEMON for solving this problem.
     52  /// (For more information, see \ref min_cost_flow_algs "the module page".)
    5253  /// Furthermore, this class supports both directions of the supply/demand
    5354  /// inequality constraints. For more information, see \ref SupplyType.
     
    10071008    }
    10081009
    1009     /// \brief Return the flow map (the primal solution).
     1010    /// \brief Copy the flow values (the primal solution) into the
     1011    /// given map.
    10101012    ///
    10111013    /// This function copies the flow value on each arc into the given
     
    10311033    }
    10321034
    1033     /// \brief Return the potential map (the dual solution).
     1035    /// \brief Copy the potential values (the dual solution) into the
     1036    /// given map.
    10341037    ///
    10351038    /// This function copies the potential (dual value) of each node
Note: See TracChangeset for help on using the changeset viewer.