41 |
41 |
42 /// \addtogroup min_cost_flow |
42 /// \addtogroup min_cost_flow |
43 /// @{ |
43 /// @{ |
44 |
44 |
45 /// \brief Implementation of the capacity scaling version of the |
45 /// \brief Implementation of the capacity scaling version of the |
46 /// successive shortest path algorithm for finding a minimum cost flow. |
46 /// successive shortest path algorithm for finding a minimum cost |
|
47 /// flow. |
47 /// |
48 /// |
48 /// \ref lemon::CapacityScaling "CapacityScaling" implements a |
49 /// \ref lemon::CapacityScaling "CapacityScaling" implements the |
49 /// capacity scaling algorithm for finding a minimum cost flow. |
50 /// capacity scaling version of the successive shortest path |
|
51 /// algorithm for finding a minimum cost flow. |
50 /// |
52 /// |
51 /// \param Graph The directed graph type the algorithm runs on. |
53 /// \param Graph The directed graph type the algorithm runs on. |
52 /// \param LowerMap The type of the lower bound map. |
54 /// \param LowerMap The type of the lower bound map. |
53 /// \param CapacityMap The type of the capacity (upper bound) map. |
55 /// \param CapacityMap The type of the capacity (upper bound) map. |
54 /// \param CostMap The type of the cost (length) map. |
56 /// \param CostMap The type of the cost (length) map. |
55 /// \param SupplyMap The type of the supply map. |
57 /// \param SupplyMap The type of the supply map. |
56 /// |
58 /// |
57 /// \warning |
59 /// \warning |
58 /// - Edge capacities and costs should be nonnegative integers. |
60 /// - Edge capacities and costs should be nonnegative integers. |
59 /// However \c CostMap::Value should be signed type. |
61 /// However \c CostMap::Value should be signed type. |
60 /// - Supply values should be integers. |
62 /// - Supply values should be signed integers. |
61 /// - \c LowerMap::Value must be convertible to |
63 /// - \c LowerMap::Value must be convertible to |
62 /// \c CapacityMap::Value and \c CapacityMap::Value must be |
64 /// \c CapacityMap::Value and \c CapacityMap::Value must be |
63 /// convertible to \c SupplyMap::Value. |
65 /// convertible to \c SupplyMap::Value. |
64 /// |
66 /// |
65 /// \author Peter Kovacs |
67 /// \author Peter Kovacs |
111 const CostMap &cost_map; |
113 const CostMap &cost_map; |
112 const PotentialMap &pot_map; |
114 const PotentialMap &pot_map; |
113 |
115 |
114 public: |
116 public: |
115 |
117 |
116 typedef typename MapBase<ResEdge, Cost>::Value Value; |
|
117 typedef typename MapBase<ResEdge, Cost>::Key Key; |
|
118 |
|
119 ReducedCostMap( const ResGraph &_gr, |
118 ReducedCostMap( const ResGraph &_gr, |
120 const CostMap &_cost, |
119 const CostMap &_cost, |
121 const PotentialMap &_pot ) : |
120 const PotentialMap &_pot ) : |
122 gr(_gr), cost_map(_cost), pot_map(_pot) {} |
121 gr(_gr), cost_map(_cost), pot_map(_pot) {} |
123 |
122 |
124 Value operator[](const Key &e) const { |
123 Cost operator[](const ResEdge &e) const { |
125 return ResGraph::forward(e) ? |
124 return ResGraph::forward(e) ? |
126 cost_map[e] - pot_map[gr.source(e)] + pot_map[gr.target(e)] : |
125 cost_map[e] - pot_map[gr.source(e)] + pot_map[gr.target(e)] : |
127 -cost_map[e] - pot_map[gr.source(e)] + pot_map[gr.target(e)]; |
126 -cost_map[e] - pot_map[gr.source(e)] + pot_map[gr.target(e)]; |
128 } |
127 } |
129 |
128 |
130 }; //class ReducedCostMap |
129 }; //class ReducedCostMap |
131 |
130 |
132 /// \brief Map adaptor for \ref lemon::Dijkstra "Dijkstra" class to |
131 /// \brief Map class for the \ref lemon::Dijkstra "Dijkstra" |
133 /// update node potentials. |
132 /// algorithm to update node potentials. |
134 class PotentialUpdateMap : public MapBase<ResNode, Cost> |
133 class PotentialUpdateMap : public MapBase<ResNode, Cost> |
135 { |
134 { |
136 private: |
135 private: |
137 |
136 |
138 PotentialMap *pot; |
137 PotentialMap *pot; |
139 typedef std::pair<ResNode, Cost> Pair; |
138 typedef std::pair<ResNode, Cost> Pair; |
140 std::vector<Pair> data; |
139 std::vector<Pair> data; |
141 |
140 |
142 public: |
141 public: |
143 |
142 |
144 typedef typename MapBase<ResNode, Cost>::Value Value; |
|
145 typedef typename MapBase<ResNode, Cost>::Key Key; |
|
146 |
|
147 void potentialMap(PotentialMap &_pot) { |
143 void potentialMap(PotentialMap &_pot) { |
148 pot = &_pot; |
144 pot = &_pot; |
149 } |
145 } |
150 |
146 |
151 void init() { |
147 void init() { |
152 data.clear(); |
148 data.clear(); |
153 } |
149 } |
154 |
150 |
155 void set(const Key &n, const Value &v) { |
151 void set(const ResNode &n, const Cost &v) { |
156 data.push_back(Pair(n, v)); |
152 data.push_back(Pair(n, v)); |
157 } |
153 } |
158 |
154 |
159 void update() { |
155 void update() { |
160 Cost val = data[data.size()-1].second; |
156 Cost val = data[data.size()-1].second; |
183 } |
179 } |
184 |
180 |
185 }; //class DeficitBoolMap |
181 }; //class DeficitBoolMap |
186 |
182 |
187 /// \brief Map adaptor class for filtering edges with at least |
183 /// \brief Map adaptor class for filtering edges with at least |
188 /// \c delta residual capacity |
184 /// \c delta residual capacity. |
189 class DeltaFilterMap : public MapBase<ResEdge, bool> |
185 class DeltaFilterMap : public MapBase<ResEdge, bool> |
190 { |
186 { |
191 private: |
187 private: |
192 |
188 |
193 const ResGraph &gr; |
189 const ResGraph &gr; |
194 const Capacity δ |
190 const Capacity δ |
195 |
191 |
196 public: |
192 public: |
197 |
193 |
198 typedef typename MapBase<ResEdge, Cost>::Value Value; |
|
199 typedef typename MapBase<ResEdge, Cost>::Key Key; |
|
200 |
|
201 DeltaFilterMap(const ResGraph &_gr, const Capacity &_delta) : |
194 DeltaFilterMap(const ResGraph &_gr, const Capacity &_delta) : |
202 gr(_gr), delta(_delta) {} |
195 gr(_gr), delta(_delta) {} |
203 |
196 |
204 Value operator[](const Key &e) const { |
197 bool operator[](const ResEdge &e) const { |
205 return gr.rescap(e) >= delta; |
198 return gr.rescap(e) >= delta; |
206 } |
199 } |
207 |
200 |
208 }; //class DeltaFilterMap |
201 }; //class DeltaFilterMap |
209 |
202 |
296 /// reduced edge costs. |
289 /// reduced edge costs. |
297 ResDijkstra dijkstra; |
290 ResDijkstra dijkstra; |
298 |
291 |
299 /// \brief The delta parameter used for capacity scaling. |
292 /// \brief The delta parameter used for capacity scaling. |
300 Capacity delta; |
293 Capacity delta; |
301 /// \brief Edge filter map. |
294 /// \brief Edge filter map for filtering edges with at least |
|
295 /// \c delta residual capacity. |
302 DeltaFilterMap delta_filter; |
296 DeltaFilterMap delta_filter; |
303 /// \brief The delta residual graph. |
297 /// \brief The delta residual graph (i.e. the subgraph of the |
|
298 /// residual graph consisting of edges with at least \c delta |
|
299 /// residual capacity). |
304 DeltaResGraph dres_graph; |
300 DeltaResGraph dres_graph; |
305 /// \brief Map for identifing deficit nodes. |
301 /// \brief Map for identifing deficit nodes. |
306 DeficitBoolMap delta_deficit; |
302 DeficitBoolMap delta_deficit; |
307 |
303 |
308 /// \brief The deficit nodes. |
304 /// \brief The deficit nodes. |
571 // Saturating edges not satisfying the optimality condition |
567 // Saturating edges not satisfying the optimality condition |
572 Capacity r; |
568 Capacity r; |
573 for (DeltaResEdgeIt e(dres_graph); e != INVALID; ++e) { |
569 for (DeltaResEdgeIt e(dres_graph); e != INVALID; ++e) { |
574 if (red_cost[e] < 0) { |
570 if (red_cost[e] < 0) { |
575 res_graph.augment(e, r = res_graph.rescap(e)); |
571 res_graph.augment(e, r = res_graph.rescap(e)); |
|
572 imbalance[dres_graph.source(e)] -= r; |
576 imbalance[dres_graph.target(e)] += r; |
573 imbalance[dres_graph.target(e)] += r; |
577 imbalance[dres_graph.source(e)] -= r; |
|
578 } |
574 } |
579 } |
575 } |
580 |
576 |
581 // Finding excess nodes |
577 // Finding excess nodes |
582 excess_nodes.clear(); |
578 excess_nodes.clear(); |