41 /// flow problem in LEMON according to our benchmark tests. |
41 /// flow problem in LEMON according to our benchmark tests. |
42 /// For the detailed documentation of this class see |
42 /// For the detailed documentation of this class see |
43 /// \ref NetworkSimplex. |
43 /// \ref NetworkSimplex. |
44 /// |
44 /// |
45 /// There are four implementations for the minimum cost flow problem, |
45 /// There are four implementations for the minimum cost flow problem, |
46 /// which can be used exactly the same way except for the fact that |
46 /// which can be used exactly the same way. |
47 /// \ref CycleCanceling does not provide dual solution (node |
|
48 /// potentials) since it is a pure primal method. |
|
49 /// - \ref CapacityScaling The capacity scaling algorithm. |
47 /// - \ref CapacityScaling The capacity scaling algorithm. |
50 /// - \ref CostScaling The cost scaling algorithm. |
48 /// - \ref CostScaling The cost scaling algorithm. |
51 /// - \ref CycleCanceling A cycle-canceling algorithm. |
49 /// - \ref CycleCanceling A cycle-canceling algorithm. |
52 /// - \ref NetworkSimplex The network simplex algorithm. |
50 /// - \ref NetworkSimplex The network simplex algorithm. |
53 /// |
51 /// |
58 /// \tparam SupplyMap The type of the supply map. |
56 /// \tparam SupplyMap The type of the supply map. |
59 /// |
57 /// |
60 /// \warning |
58 /// \warning |
61 /// - Edge capacities and costs should be \e non-negative \e integers. |
59 /// - Edge capacities and costs should be \e non-negative \e integers. |
62 /// - Supply values should be \e signed \e integers. |
60 /// - Supply values should be \e signed \e integers. |
63 /// - \c LowerMap::Value must be convertible to \c CapacityMap::Value. |
61 /// - The value types of the maps should be convertible to each other. |
64 /// - \c CapacityMap::Value and \c SupplyMap::Value must be |
62 /// - \c CostMap::Value must be signed type. |
65 /// convertible to each other. |
|
66 /// - All value types must be convertible to \c CostMap::Value, which |
|
67 /// must be signed type. |
|
68 /// |
63 /// |
69 /// \author Peter Kovacs |
64 /// \author Peter Kovacs |
70 |
65 |
71 template < typename Graph, |
66 template < typename Graph, |
72 typename LowerMap = typename Graph::template EdgeMap<int>, |
67 typename LowerMap = typename Graph::template EdgeMap<int>, |
73 typename CapacityMap = LowerMap, |
68 typename CapacityMap = typename Graph::template EdgeMap<int>, |
74 typename CostMap = typename Graph::template EdgeMap<int>, |
69 typename CostMap = typename Graph::template EdgeMap<int>, |
75 typename SupplyMap = typename Graph::template NodeMap |
70 typename SupplyMap = typename Graph::template NodeMap<int> > |
76 <typename CapacityMap::Value> > |
|
77 class MinCostFlow : |
71 class MinCostFlow : |
78 public NetworkSimplex< Graph, LowerMap, CapacityMap, |
72 public NetworkSimplex< Graph, LowerMap, CapacityMap, |
79 CostMap, SupplyMap > |
73 CostMap, SupplyMap > |
80 { |
74 { |
81 typedef NetworkSimplex< Graph, LowerMap, CapacityMap, |
75 typedef NetworkSimplex< Graph, LowerMap, CapacityMap, |
83 typedef typename Graph::Node Node; |
77 typedef typename Graph::Node Node; |
84 typedef typename SupplyMap::Value Supply; |
78 typedef typename SupplyMap::Value Supply; |
85 |
79 |
86 public: |
80 public: |
87 |
81 |
88 /// General constructor of the class (with lower bounds). |
82 /// General constructor (with lower bounds). |
89 MinCostFlow( const Graph &graph, |
83 MinCostFlow( const Graph &graph, |
90 const LowerMap &lower, |
84 const LowerMap &lower, |
91 const CapacityMap &capacity, |
85 const CapacityMap &capacity, |
92 const CostMap &cost, |
86 const CostMap &cost, |
93 const SupplyMap &supply ) : |
87 const SupplyMap &supply ) : |
98 const CapacityMap &capacity, |
92 const CapacityMap &capacity, |
99 const CostMap &cost, |
93 const CostMap &cost, |
100 const SupplyMap &supply ) : |
94 const SupplyMap &supply ) : |
101 MinCostFlowImpl(graph, capacity, cost, supply) {} |
95 MinCostFlowImpl(graph, capacity, cost, supply) {} |
102 |
96 |
103 /// Simple constructor of the class (with lower bounds). |
97 /// Simple constructor (with lower bounds). |
104 MinCostFlow( const Graph &graph, |
98 MinCostFlow( const Graph &graph, |
105 const LowerMap &lower, |
99 const LowerMap &lower, |
106 const CapacityMap &capacity, |
100 const CapacityMap &capacity, |
107 const CostMap &cost, |
101 const CostMap &cost, |
108 Node s, Node t, |
102 Node s, Node t, |
109 Supply flow_value ) : |
103 Supply flow_value ) : |
110 MinCostFlowImpl( graph, lower, capacity, cost, |
104 MinCostFlowImpl( graph, lower, capacity, cost, |
111 s, t, flow_value ) {} |
105 s, t, flow_value ) {} |
112 |
106 |
113 /// Simple constructor of the class (without lower bounds). |
107 /// Simple constructor (without lower bounds). |
114 MinCostFlow( const Graph &graph, |
108 MinCostFlow( const Graph &graph, |
115 const CapacityMap &capacity, |
109 const CapacityMap &capacity, |
116 const CostMap &cost, |
110 const CostMap &cost, |
117 Node s, Node t, |
111 Node s, Node t, |
118 Supply flow_value ) : |
112 Supply flow_value ) : |