31 /// \addtogroup min_cost_flow |
31 /// \addtogroup min_cost_flow |
32 /// @{ |
32 /// @{ |
33 |
33 |
34 /// \brief An efficient algorithm for finding a minimum cost flow. |
34 /// \brief An efficient algorithm for finding a minimum cost flow. |
35 /// |
35 /// |
36 /// \ref lemon::MinCostFlow "MinCostFlow" implements an efficient |
36 /// \ref MinCostFlow provides an efficient algorithm for finding |
37 /// algorithm for finding a minimum cost flow. |
37 /// a minimum cost flow. |
38 /// |
38 /// |
39 /// \note \ref lemon::MinCostFlow "MinCostFlow" is just an alias for |
39 /// \note \ref MinCostFlow is just an alias for \ref NetworkSimplex, |
40 /// \ref lemon::NetworkSimplex "NetworkSimplex", wich is the most |
40 /// which is the most efficient implementation for the minimum cost |
41 /// efficient implementation for the minimum cost flow problem in the |
41 /// flow problem in the LEMON library according to our benchmark |
42 /// LEMON library according to our benchmark tests. |
42 /// tests. |
43 /// |
43 /// |
44 /// \note There are three implementations for the minimum cost flow |
44 /// \note There are three implementations for the minimum cost flow |
45 /// problem, that can be used in the same way. |
45 /// problem, that can be used exactly the same way. |
46 /// - \ref lemon::CapacityScaling "CapacityScaling" |
46 /// - \ref CapacityScaling |
47 /// - \ref lemon::CycleCanceling "CycleCanceling" |
47 /// - \ref CycleCanceling |
48 /// - \ref lemon::NetworkSimplex "NetworkSimplex" |
48 /// - \ref NetworkSimplex |
|
49 /// |
|
50 /// \note For the detailed documentation of this class see |
|
51 /// \ref NetworkSimplex. |
49 /// |
52 /// |
50 /// \param Graph The directed graph type the algorithm runs on. |
53 /// \param Graph The directed graph type the algorithm runs on. |
51 /// \param LowerMap The type of the lower bound map. |
54 /// \param LowerMap The type of the lower bound map. |
52 /// \param CapacityMap The type of the capacity (upper bound) map. |
55 /// \param CapacityMap The type of the capacity (upper bound) map. |
53 /// \param CostMap The type of the cost (length) map. |
56 /// \param CostMap The type of the cost (length) map. |
54 /// \param SupplyMap The type of the supply map. |
57 /// \param SupplyMap The type of the supply map. |
55 /// |
58 /// |
56 /// \warning |
59 /// \warning |
57 /// - Edge capacities and costs should be nonnegative integers. |
60 /// - Edge capacities and costs should be non-negative integers. |
58 /// However \c CostMap::Value should be signed type. |
61 /// However \c CostMap::Value should be signed type. |
59 /// - Supply values should be signed integers. |
62 /// - Supply values should be signed integers. |
60 /// - \c LowerMap::Value must be convertible to |
63 /// - \c LowerMap::Value must be convertible to |
61 /// \c CapacityMap::Value and \c CapacityMap::Value must be |
64 /// \c CapacityMap::Value and \c CapacityMap::Value must be |
62 /// convertible to \c SupplyMap::Value. |
65 /// convertible to \c SupplyMap::Value. |
63 /// |
66 /// |
64 /// \author Peter Kovacs |
67 /// \author Peter Kovacs |
65 |
68 |
66 template < typename Graph, |
69 template < typename Graph, |
67 typename LowerMap = typename Graph::template EdgeMap<int>, |
70 typename LowerMap = typename Graph::template EdgeMap<int>, |
68 typename CapacityMap = LowerMap, |
71 typename CapacityMap = LowerMap, |
69 typename CostMap = typename Graph::template EdgeMap<int>, |
72 typename CostMap = typename Graph::template EdgeMap<int>, |
70 typename SupplyMap = typename Graph::template NodeMap |
73 typename SupplyMap = typename Graph::template NodeMap |
71 <typename CapacityMap::Value> > |
74 <typename CapacityMap::Value> > |
72 class MinCostFlow : |
75 class MinCostFlow : |
73 public NetworkSimplex< Graph, |
76 public NetworkSimplex< Graph, LowerMap, CapacityMap, |
74 LowerMap, |
77 CostMap, SupplyMap > |
75 CapacityMap, |
|
76 CostMap, |
|
77 SupplyMap > |
|
78 { |
78 { |
79 typedef NetworkSimplex< Graph, LowerMap, CapacityMap, |
79 typedef NetworkSimplex< Graph, LowerMap, CapacityMap, |
80 CostMap, SupplyMap > |
80 CostMap, SupplyMap > MinCostFlowImpl; |
81 MinCostFlowImpl; |
|
82 typedef typename Graph::Node Node; |
81 typedef typename Graph::Node Node; |
83 typedef typename SupplyMap::Value Supply; |
82 typedef typename SupplyMap::Value Supply; |
84 |
83 |
85 public: |
84 public: |
86 |
85 |
87 /// \brief General constructor of the class (with lower bounds). |
86 /// General constructor of the class (with lower bounds). |
88 MinCostFlow( const Graph &_graph, |
87 MinCostFlow( const Graph &graph, |
89 const LowerMap &_lower, |
88 const LowerMap &lower, |
90 const CapacityMap &_capacity, |
89 const CapacityMap &capacity, |
91 const CostMap &_cost, |
90 const CostMap &cost, |
92 const SupplyMap &_supply ) : |
91 const SupplyMap &supply ) : |
93 MinCostFlowImpl(_graph, _lower, _capacity, _cost, _supply) {} |
92 MinCostFlowImpl(graph, lower, capacity, cost, supply) {} |
94 |
93 |
95 /// \brief General constructor of the class (without lower bounds). |
94 /// General constructor of the class (without lower bounds). |
96 MinCostFlow( const Graph &_graph, |
95 MinCostFlow( const Graph &graph, |
97 const CapacityMap &_capacity, |
96 const CapacityMap &capacity, |
98 const CostMap &_cost, |
97 const CostMap &_ost, |
99 const SupplyMap &_supply ) : |
98 const SupplyMap &supply ) : |
100 MinCostFlowImpl(_graph, _capacity, _cost, _supply) {} |
99 MinCostFlowImpl(graph, capacity, cost, supply) {} |
101 |
100 |
102 /// \brief Simple constructor of the class (with lower bounds). |
101 /// Simple constructor of the class (with lower bounds). |
103 MinCostFlow( const Graph &_graph, |
102 MinCostFlow( const Graph &graph, |
104 const LowerMap &_lower, |
103 const LowerMap &lower, |
105 const CapacityMap &_capacity, |
104 const CapacityMap &capacity, |
106 const CostMap &_cost, |
105 const CostMap &_ost, |
107 Node _s, Node _t, |
106 Node s, Node t, |
108 Supply _flow_value ) : |
107 Supply flow_value ) : |
109 MinCostFlowImpl( _graph, _lower, _capacity, _cost, |
108 MinCostFlowImpl( graph, lower, capacity, cost, |
110 _s, _t, _flow_value ) {} |
109 s, t, flow_value ) {} |
111 |
110 |
112 /// \brief Simple constructor of the class (without lower bounds). |
111 /// Simple constructor of the class (without lower bounds). |
113 MinCostFlow( const Graph &_graph, |
112 MinCostFlow( const Graph &graph, |
114 const CapacityMap &_capacity, |
113 const CapacityMap &capacity, |
115 const CostMap &_cost, |
114 const CostMap &cost, |
116 Node _s, Node _t, |
115 Node s, Node t, |
117 Supply _flow_value ) : |
116 Supply flow_value ) : |
118 MinCostFlowImpl( _graph, _capacity, _cost, |
117 MinCostFlowImpl( graph, capacity, cost, |
119 _s, _t, _flow_value ) {} |
118 s, t, flow_value ) {} |
120 |
119 |
121 }; //class MinCostFlow |
120 }; //class MinCostFlow |
122 |
121 |
123 ///@} |
122 ///@} |
124 |
123 |