41 /// |
41 /// |
42 /// \ref NetworkSimplex implements the primal Network Simplex algorithm |
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, |
44 /// \ref amo93networkflows, \ref dantzig63linearprog, |
45 /// \ref kellyoneill91netsimplex. |
45 /// \ref kellyoneill91netsimplex. |
46 /// This algorithm is a specialized version of the linear programming |
46 /// This algorithm is a highly efficient specialized version of the |
47 /// simplex method directly for the minimum cost flow problem. |
47 /// linear programming simplex method directly for the minimum cost |
48 /// It is one of the most efficient solution methods. |
48 /// flow problem. |
49 /// |
49 /// |
50 /// In general this class is the fastest implementation available |
50 /// In general, %NetworkSimplex is the fastest implementation available |
51 /// in LEMON for the minimum cost flow problem. |
51 /// in LEMON for this problem. |
52 /// Moreover it supports both directions of the supply/demand inequality |
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 /// Most of the parameters of the problem (except for the digraph) |
55 /// Most of the parameters of the problem (except for the digraph) |
56 /// can be given using separate functions, and the algorithm can be |
56 /// can be given using separate functions, and the algorithm can be |
57 /// executed using the \ref run() function. If some parameters are not |
57 /// executed using the \ref run() function. If some parameters are not |
58 /// specified, then default values will be used. |
58 /// specified, then default values will be used. |
59 /// |
59 /// |
60 /// \tparam GR The digraph type the algorithm runs on. |
60 /// \tparam GR The digraph type the algorithm runs on. |
61 /// \tparam V The value type used for flow amounts, capacity bounds |
61 /// \tparam V The number 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 /// \tparam C The value type used for costs and potentials in the |
63 /// \tparam C The number 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 /// \warning Both value types must be signed and all input data must |
66 /// \warning Both number types must be signed and all input data must |
67 /// be integer. |
67 /// be integer. |
68 /// |
68 /// |
69 /// \note %NetworkSimplex provides five different pivot rule |
69 /// \note %NetworkSimplex provides five different pivot rule |
70 /// implementations, from which the most efficient one is used |
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. |
124 /// \ref NetworkSimplex provides five different pivot rule |
124 /// \ref NetworkSimplex provides five different pivot rule |
125 /// implementations that significantly affect the running time |
125 /// implementations that significantly affect the running time |
126 /// of the algorithm. |
126 /// of the algorithm. |
127 /// By default, \ref BLOCK_SEARCH "Block Search" is used, which |
127 /// By default, \ref BLOCK_SEARCH "Block Search" is used, which |
128 /// proved to be the most efficient and the most robust on various |
128 /// proved to be the most efficient and the most robust on various |
129 /// test inputs according to our benchmark tests. |
129 /// test inputs. |
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 /// function with the proper parameter. |
131 /// function with the proper parameter. |
132 enum PivotRule { |
132 enum PivotRule { |
133 |
133 |
134 /// The \e First \e Eligible pivot rule. |
134 /// The \e First \e Eligible pivot rule. |
635 _graph(graph), _node_id(graph), _arc_id(graph), |
635 _graph(graph), _node_id(graph), _arc_id(graph), |
636 MAX(std::numeric_limits<Value>::max()), |
636 MAX(std::numeric_limits<Value>::max()), |
637 INF(std::numeric_limits<Value>::has_infinity ? |
637 INF(std::numeric_limits<Value>::has_infinity ? |
638 std::numeric_limits<Value>::infinity() : MAX) |
638 std::numeric_limits<Value>::infinity() : MAX) |
639 { |
639 { |
640 // Check the value types |
640 // Check the number types |
641 LEMON_ASSERT(std::numeric_limits<Value>::is_signed, |
641 LEMON_ASSERT(std::numeric_limits<Value>::is_signed, |
642 "The flow type of NetworkSimplex must be signed"); |
642 "The flow type of NetworkSimplex must be signed"); |
643 LEMON_ASSERT(std::numeric_limits<Cost>::is_signed, |
643 LEMON_ASSERT(std::numeric_limits<Cost>::is_signed, |
644 "The cost type of NetworkSimplex must be signed"); |
644 "The cost type of NetworkSimplex must be signed"); |
645 |
645 |
727 /// \brief Set the upper bounds (capacities) on the arcs. |
727 /// \brief Set the upper bounds (capacities) on the arcs. |
728 /// |
728 /// |
729 /// This function sets the upper bounds (capacities) on the arcs. |
729 /// This function sets the upper bounds (capacities) on the arcs. |
730 /// If it is not used before calling \ref run(), the upper bounds |
730 /// If it is not used before calling \ref run(), the upper bounds |
731 /// will be set to \ref INF on all arcs (i.e. the flow value will be |
731 /// will be set to \ref INF on all arcs (i.e. the flow value will be |
732 /// unbounded from above on each arc). |
732 /// unbounded from above). |
733 /// |
733 /// |
734 /// \param map An arc map storing the upper bounds. |
734 /// \param map An arc map storing the upper bounds. |
735 /// Its \c Value type must be convertible to the \c Value type |
735 /// Its \c Value type must be convertible to the \c Value type |
736 /// of the algorithm. |
736 /// of the algorithm. |
737 /// |
737 /// |