Changeset 835:c92296660262 in lemon for lemon/network_simplex.h
- Timestamp:
- 11/18/09 14:38:02 (14 years ago)
- Branch:
- default
- Parents:
- 834:c2230649a493 (diff), 833:e20173729589 (diff)
Note: this is a merge changeset, the changes displayed below correspond to the merge itself.
Use the (diff) links above to see all the changes relative to each parent. - Phase:
- public
- Files:
-
- 2 edited
Legend:
- Unmodified
- Added
- Removed
-
lemon/network_simplex.h
r833 r835 41 41 /// 42 42 /// \ref NetworkSimplex implements the primal Network Simplex algorithm 43 /// for finding a \ref min_cost_flow "minimum cost flow". 43 /// for finding a \ref min_cost_flow "minimum cost flow" 44 /// \ref amo93networkflows, \ref dantzig63linearprog, 45 /// \ref kellyoneill91netsimplex. 44 46 /// This algorithm is a specialized version of the linear programming 45 47 /// simplex method directly for the minimum cost flow problem. -
lemon/network_simplex.h
r802 r835 51 51 /// in LEMON for the minimum cost flow problem. 52 52 /// Moreover it supports both directions of the supply/demand inequality 53 /// constraints. For more information see \ref SupplyType.53 /// constraints. For more information, see \ref SupplyType. 54 54 /// 55 55 /// Most of the parameters of the problem (except for the digraph) … … 60 60 /// \tparam GR The digraph type the algorithm runs on. 61 61 /// \tparam V The value type used for flow amounts, capacity bounds 62 /// and supply values in the algorithm. By default it is \c int.62 /// and supply values in the algorithm. By default, it is \c int. 63 63 /// \tparam C The value type used for costs and potentials in the 64 /// algorithm. By default it is the same as \c V.64 /// algorithm. By default, it is the same as \c V. 65 65 /// 66 66 /// \warning Both value types must be signed and all input data must … … 69 69 /// \note %NetworkSimplex provides five different pivot rule 70 70 /// implementations, from which the most efficient one is used 71 /// by default. For more information see \ref PivotRule.71 /// by default. For more information, see \ref PivotRule. 72 72 template <typename GR, typename V = int, typename C = V> 73 73 class NetworkSimplex … … 125 125 /// implementations that significantly affect the running time 126 126 /// of the algorithm. 127 /// By default \ref BLOCK_SEARCH "Block Search" is used, which127 /// By default, \ref BLOCK_SEARCH "Block Search" is used, which 128 128 /// proved to be the most efficient and the most robust on various 129 129 /// test inputs according to our benchmark tests. 130 /// However another pivot rule can be selected using the \ref run()130 /// However, another pivot rule can be selected using the \ref run() 131 131 /// function with the proper parameter. 132 132 enum PivotRule { 133 133 134 /// The FirstEligible pivot rule.134 /// The \e First \e Eligible pivot rule. 135 135 /// The next eligible arc is selected in a wraparound fashion 136 136 /// in every iteration. 137 137 FIRST_ELIGIBLE, 138 138 139 /// The BestEligible pivot rule.139 /// The \e Best \e Eligible pivot rule. 140 140 /// The best eligible arc is selected in every iteration. 141 141 BEST_ELIGIBLE, 142 142 143 /// The BlockSearch pivot rule.143 /// The \e Block \e Search pivot rule. 144 144 /// A specified number of arcs are examined in every iteration 145 145 /// in a wraparound fashion and the best eligible arc is selected … … 147 147 BLOCK_SEARCH, 148 148 149 /// The Candidate List pivot rule.149 /// The \e Candidate \e List pivot rule. 150 150 /// In a major iteration a candidate list is built from eligible arcs 151 151 /// in a wraparound fashion and in the following minor iterations … … 153 153 CANDIDATE_LIST, 154 154 155 /// The Altering Candidate List pivot rule.155 /// The \e Altering \e Candidate \e List pivot rule. 156 156 /// It is a modified version of the Candidate List method. 157 157 /// It keeps only the several best eligible arcs from the former … … 813 813 /// type will be used. 814 814 /// 815 /// For more information see \ref SupplyType.815 /// For more information, see \ref SupplyType. 816 816 /// 817 817 /// \return <tt>(*this)</tt> … … 845 845 /// \ref reset() is called, thus only the modified parameters 846 846 /// have to be set again. See \ref reset() for examples. 847 /// However the underlying digraph must not be modified after this847 /// However, the underlying digraph must not be modified after this 848 848 /// class have been constructed, since it copies and extends the graph. 849 849 /// 850 850 /// \param pivot_rule The pivot rule that will be used during the 851 /// algorithm. For more information see \ref PivotRule.851 /// algorithm. For more information, see \ref PivotRule. 852 852 /// 853 853 /// \return \c INFEASIBLE if no feasible flow exists, … … 874 874 /// used, all the parameters given before are kept for the next 875 875 /// \ref run() call. 876 /// However the underlying digraph must not be modified after this876 /// However, the underlying digraph must not be modified after this 877 877 /// class have been constructed, since it copies and extends the graph. 878 878 ///
Note: See TracChangeset
for help on using the changeset viewer.