84 |
83 |
85 private: |
84 private: |
86 |
85 |
87 // The directed graph the algorithm runs on |
86 // The directed graph the algorithm runs on |
88 const Graph &_graph; |
87 const Graph &_graph; |
89 // The modified capacity map |
88 // The capacity map |
90 const CapacityMap &_capacity; |
89 const CapacityMap &_capacity; |
91 // The cost map |
90 // The cost map |
92 const CostMap &_cost; |
91 const CostMap &_cost; |
93 |
92 |
94 // Edge map of the found flow |
93 // Edge map of the found flow |
95 FlowMap _flow; |
94 FlowMap *_flow; |
96 // Node map of the found potentials |
95 bool _local_flow; |
97 PotentialMap _potential; |
96 // Node map of the current potentials |
|
97 PotentialMap *_potential; |
|
98 bool _local_potential; |
98 |
99 |
99 // The source node |
100 // The source node |
100 Node _source; |
101 Node _source; |
101 // The target node |
102 // The target node |
102 Node _target; |
103 Node _target; |
103 |
104 |
104 public: |
105 public: |
105 |
106 |
106 /// \brief The constructor of the class. |
107 /// \brief Constructor. |
107 /// |
108 /// |
108 /// The constructor of the class. |
109 /// Constructor. |
109 /// |
110 /// |
110 /// \param _graph The directed graph the algorithm runs on. |
111 /// \param graph The directed graph the algorithm runs on. |
111 /// \param _capacity The capacities (upper bounds) of the edges. |
112 /// \param capacity The capacities (upper bounds) of the edges. |
112 /// \param _cost The cost (length) values of the edges. |
113 /// \param cost The cost (length) values of the edges. |
113 /// \param _s The source node. |
114 /// \param s The source node. |
114 /// \param _t The target node. |
115 /// \param t The target node. |
115 MinCostMaxFlow( const Graph &graph, |
116 MinCostMaxFlow( const Graph &graph, |
116 const CapacityMap &capacity, |
117 const CapacityMap &capacity, |
117 const CostMap &cost, |
118 const CostMap &cost, |
118 Node s, Node t ) : |
119 Node s, Node t ) : |
119 _graph(graph), _capacity(capacity), _cost(cost), _flow(graph), |
120 _graph(graph), _capacity(capacity), _cost(cost), _flow(0), |
120 _potential(graph), _source(s), _target(t) |
121 _local_flow(false), _potential(0), _local_potential(false), |
121 {} |
122 _source(s), _target(t) {} |
|
123 |
|
124 /// Destructor. |
|
125 ~MinCostMaxFlow() { |
|
126 if (_local_flow) delete _flow; |
|
127 if (_local_potential) delete _potential; |
|
128 } |
|
129 |
|
130 /// \brief Sets the flow map. |
|
131 /// |
|
132 /// Sets the flow map. |
|
133 /// |
|
134 /// \return \c (*this) |
|
135 MinCostMaxFlow& flowMap(FlowMap &map) { |
|
136 if (_local_flow) { |
|
137 delete _flow; |
|
138 _local_flow = false; |
|
139 } |
|
140 _flow = ↦ |
|
141 return *this; |
|
142 } |
|
143 |
|
144 /// \brief Sets the potential map. |
|
145 /// |
|
146 /// Sets the potential map. |
|
147 /// |
|
148 /// \return \c (*this) |
|
149 MinCostMaxFlow& potentialMap(PotentialMap &map) { |
|
150 if (_local_potential) { |
|
151 delete _potential; |
|
152 _local_potential = false; |
|
153 } |
|
154 _potential = ↦ |
|
155 return *this; |
|
156 } |
|
157 |
|
158 /// \name Execution control |
|
159 /// The only way to execute the algorithm is to call the run() |
|
160 /// function. |
|
161 |
|
162 /// @{ |
122 |
163 |
123 /// \brief Runs the algorithm. |
164 /// \brief Runs the algorithm. |
124 /// |
165 /// |
125 /// Runs the algorithm. |
166 /// Runs the algorithm. |
126 void run() { |
167 void run() { |
|
168 // Initializing maps |
|
169 if (!_flow) { |
|
170 _flow = new FlowMap(_graph); |
|
171 _local_flow = true; |
|
172 } |
|
173 if (!_potential) { |
|
174 _potential = new PotentialMap(_graph); |
|
175 _local_potential = true; |
|
176 } |
|
177 // Running Preflow |
127 MaxFlowImpl preflow(_graph, _capacity, _source, _target); |
178 MaxFlowImpl preflow(_graph, _capacity, _source, _target); |
128 preflow.flowMap(_flow).runMinCut(); |
179 preflow.flowMap(*_flow).runMinCut(); |
|
180 // Running NetworkSimplex |
129 MinCostFlowImpl mcf( _graph, _capacity, _cost, |
181 MinCostFlowImpl mcf( _graph, _capacity, _cost, |
130 _source, _target, preflow.flowValue() ); |
182 _source, _target, preflow.flowValue() ); |
131 mcf.flowMap(_flow).potentialMap(_potential).run(); |
183 mcf.flowMap(*_flow).potentialMap(*_potential).run(); |
132 } |
184 } |
|
185 |
|
186 /// @} |
|
187 |
|
188 /// \name Query Functions |
|
189 /// The result of the algorithm can be obtained using these |
|
190 /// functions. |
|
191 /// \n run() must be called before using them. |
|
192 |
|
193 /// @{ |
133 |
194 |
134 /// \brief Returns a const reference to the edge map storing the |
195 /// \brief Returns a const reference to the edge map storing the |
135 /// found flow. |
196 /// found flow. |
136 /// |
197 /// |
137 /// Returns a const reference to the edge map storing the found flow. |
198 /// Returns a const reference to the edge map storing the found flow. |
138 /// |
199 /// |
139 /// \pre \ref run() must be called before using this function. |
200 /// \pre \ref run() must be called before using this function. |
140 const FlowMap& flowMap() const { |
201 const FlowMap& flowMap() const { |
141 return _flow; |
202 return *_flow; |
142 } |
203 } |
143 |
204 |
144 /// \brief Returns a const reference to the node map storing the |
205 /// \brief Returns a const reference to the node map storing the |
145 /// found potentials (the dual solution). |
206 /// found potentials (the dual solution). |
146 /// |
207 /// |
147 /// Returns a const reference to the node map storing the found |
208 /// Returns a const reference to the node map storing the found |
148 /// potentials (the dual solution). |
209 /// potentials (the dual solution). |
149 /// |
210 /// |
150 /// \pre \ref run() must be called before using this function. |
211 /// \pre \ref run() must be called before using this function. |
151 const PotentialMap& potentialMap() const { |
212 const PotentialMap& potentialMap() const { |
152 return _potential; |
213 return *_potential; |
|
214 } |
|
215 |
|
216 /// \brief Returns the flow on the given edge. |
|
217 /// |
|
218 /// Returns the flow on the given edge. |
|
219 /// |
|
220 /// \pre \ref run() must be called before using this function. |
|
221 Capacity flow(const Edge& edge) const { |
|
222 return (*_flow)[edge]; |
|
223 } |
|
224 |
|
225 /// \brief Returns the potential of the given node. |
|
226 /// |
|
227 /// Returns the potential of the given node. |
|
228 /// |
|
229 /// \pre \ref run() must be called before using this function. |
|
230 Cost potential(const Node& node) const { |
|
231 return (*_potential)[node]; |
153 } |
232 } |
154 |
233 |
155 /// \brief Returns the total cost of the found flow. |
234 /// \brief Returns the total cost of the found flow. |
156 /// |
235 /// |
157 /// Returns the total cost of the found flow. The complexity of the |
236 /// Returns the total cost of the found flow. The complexity of the |
158 /// function is \f$ O(e) \f$. |
237 /// function is \f$ O(e) \f$. |
159 /// |
238 /// |
160 /// \pre \ref run() must be called before using this function. |
239 /// \pre \ref run() must be called before using this function. |
161 Cost totalCost() const { |
240 Cost totalCost() const { |
162 Cost c = 0; |
241 Cost c = 0; |
163 for (typename Graph::EdgeIt e(_graph); e != INVALID; ++e) |
242 for (EdgeIt e(_graph); e != INVALID; ++e) |
164 c += _flow[e] * _cost[e]; |
243 c += (*_flow)[e] * _cost[e]; |
165 return c; |
244 return c; |
166 } |
245 } |
167 |
246 |
|
247 /// @} |
|
248 |
168 }; //class MinCostMaxFlow |
249 }; //class MinCostMaxFlow |
169 |
250 |
170 ///@} |
251 ///@} |
171 |
252 |
172 } //namespace lemon |
253 } //namespace lemon |