COIN-OR::LEMON - Graph Library

Changeset 1165:16f55008c863 in 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)

Files:
5 edited

Legend:

Unmodified
Added
Removed
  • doc/groups.dox

    r1164 r1165  
    408408
    409409In general, \ref NetworkSimplex and \ref CostScaling are the most efficient
    410 implementations, but the other algorithms could be faster in special cases.
     410implementations.
     411\ref NetworkSimplex is usually the fastest on relatively small graphs (up to
     412several thousands of nodes) and on dense graphs, while \ref CostScaling is
     413typically more efficient on large graphs (e.g. hundreds of thousands of
     414nodes or above), especially if they are sparse.
     415However, other algorithms could be faster in special cases.
    411416For example, if the total supply and/or capacities are rather small,
    412417\ref CapacityScaling is usually the fastest algorithm (without effective scaling).
  • 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.