21 |
21 |
22 /// \file |
22 /// \file |
23 /// \ingroup max_flow |
23 /// \ingroup max_flow |
24 /// \brief Implementation of the Edmonds-Karp algorithm. |
24 /// \brief Implementation of the Edmonds-Karp algorithm. |
25 |
25 |
26 #include <lemon/graph_adaptor.h> |
|
27 #include <lemon/tolerance.h> |
26 #include <lemon/tolerance.h> |
28 #include <lemon/bfs.h> |
27 #include <vector> |
29 |
28 |
30 namespace lemon { |
29 namespace lemon { |
31 |
30 |
|
31 /// \brief Default traits class of EdmondsKarp class. |
|
32 /// |
|
33 /// Default traits class of EdmondsKarp class. |
|
34 /// \param _Graph Graph type. |
|
35 /// \param _CapacityMap Type of capacity map. |
|
36 template <typename _Graph, typename _CapacityMap> |
|
37 struct EdmondsKarpDefaultTraits { |
|
38 |
|
39 /// \brief The graph type the algorithm runs on. |
|
40 typedef _Graph Graph; |
|
41 |
|
42 /// \brief The type of the map that stores the edge capacities. |
|
43 /// |
|
44 /// The type of the map that stores the edge capacities. |
|
45 /// It must meet the \ref concepts::ReadMap "ReadMap" concept. |
|
46 typedef _CapacityMap CapacityMap; |
|
47 |
|
48 /// \brief The type of the length of the edges. |
|
49 typedef typename CapacityMap::Value Value; |
|
50 |
|
51 /// \brief The map type that stores the flow values. |
|
52 /// |
|
53 /// The map type that stores the flow values. |
|
54 /// It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept. |
|
55 typedef typename Graph::template EdgeMap<Value> FlowMap; |
|
56 |
|
57 /// \brief Instantiates a FlowMap. |
|
58 /// |
|
59 /// This function instantiates a \ref FlowMap. |
|
60 /// \param graph The graph, to which we would like to define the flow map. |
|
61 static FlowMap* createFlowMap(const Graph& graph) { |
|
62 return new FlowMap(graph); |
|
63 } |
|
64 |
|
65 /// \brief The tolerance used by the algorithm |
|
66 /// |
|
67 /// The tolerance used by the algorithm to handle inexact computation. |
|
68 typedef Tolerance<Value> Tolerance; |
|
69 |
|
70 }; |
|
71 |
32 /// \ingroup max_flow |
72 /// \ingroup max_flow |
|
73 /// |
33 /// \brief Edmonds-Karp algorithms class. |
74 /// \brief Edmonds-Karp algorithms class. |
34 /// |
75 /// |
35 /// This class provides an implementation of the \e Edmonds-Karp \e |
76 /// This class provides an implementation of the \e Edmonds-Karp \e |
36 /// algorithm producing a flow of maximum value in a directed |
77 /// algorithm producing a flow of maximum value in a directed |
37 /// graph. The Edmonds-Karp algorithm is slower than the Preflow algorithm |
78 /// graphs. The Edmonds-Karp algorithm is slower than the Preflow |
38 /// but it has an advantage of the step-by-step execution control with |
79 /// algorithm but it has an advantage of the step-by-step execution |
39 /// feasible flow solutions. The \e source node, the \e target node, the \e |
80 /// control with feasible flow solutions. The \e source node, the \e |
40 /// capacity of the edges and the \e starting \e flow value of the |
81 /// target node, the \e capacity of the edges and the \e starting \e |
41 /// edges should be passed to the algorithm through the |
82 /// flow value of the edges should be passed to the algorithm |
42 /// constructor. |
83 /// through the constructor. |
43 /// |
84 /// |
44 /// The time complexity of the algorithm is \f$ O(n * e^2) \f$ in |
85 /// The time complexity of the algorithm is \f$ O(nm^2) \f$ in |
45 /// worst case. Always try the preflow algorithm instead of this if |
86 /// worst case. Always try the preflow algorithm instead of this if |
46 /// you just want to compute the optimal flow. |
87 /// you just want to compute the optimal flow. |
47 /// |
88 /// |
48 /// \param _Graph The directed graph type the algorithm runs on. |
89 /// \param _Graph The directed graph type the algorithm runs on. |
49 /// \param _Number The number type of the capacities and the flow values. |
|
50 /// \param _CapacityMap The capacity map type. |
90 /// \param _CapacityMap The capacity map type. |
51 /// \param _FlowMap The flow map type. |
91 /// \param _Traits Traits class to set various data types used by |
52 /// \param _Tolerance The tolerance class to handle computation problems. |
92 /// the algorithm. The default traits class is \ref |
|
93 /// EdmondsKarpDefaultTraits. See \ref EdmondsKarpDefaultTraits for the |
|
94 /// documentation of a Edmonds-Karp traits class. |
53 /// |
95 /// |
54 /// \author Balazs Dezso |
96 /// \author Balazs Dezso |
55 #ifdef DOXYGEN |
97 #ifdef DOXYGEN |
56 template <typename _Graph, typename _Number, |
98 template <typename _Graph, typename _CapacityMap, typename _Traits> |
57 typename _CapacityMap, typename _FlowMap, typename _Tolerance> |
99 #else |
58 #else |
100 template <typename _Graph, |
59 template <typename _Graph, typename _Number, |
101 typename _CapacityMap = typename _Graph::template EdgeMap<int>, |
60 typename _CapacityMap = typename _Graph::template EdgeMap<_Number>, |
102 typename _Traits = EdmondsKarpDefaultTraits<_Graph, _CapacityMap> > |
61 typename _FlowMap = typename _Graph::template EdgeMap<_Number>, |
|
62 typename _Tolerance = Tolerance<_Number> > |
|
63 #endif |
103 #endif |
64 class EdmondsKarp { |
104 class EdmondsKarp { |
65 public: |
105 public: |
|
106 |
|
107 typedef _Traits Traits; |
|
108 typedef typename Traits::Graph Graph; |
|
109 typedef typename Traits::CapacityMap CapacityMap; |
|
110 typedef typename Traits::Value Value; |
|
111 |
|
112 typedef typename Traits::FlowMap FlowMap; |
|
113 typedef typename Traits::Tolerance Tolerance; |
66 |
114 |
67 /// \brief \ref Exception for the case when the source equals the target. |
115 /// \brief \ref Exception for the case when the source equals the target. |
68 /// |
116 /// |
69 /// \ref Exception for the case when the source equals the target. |
117 /// \ref Exception for the case when the source equals the target. |
70 /// |
118 /// |
74 return "lemon::EdmondsKarp::InvalidArgument"; |
122 return "lemon::EdmondsKarp::InvalidArgument"; |
75 } |
123 } |
76 }; |
124 }; |
77 |
125 |
78 |
126 |
79 /// \brief The graph type the algorithm runs on. |
|
80 typedef _Graph Graph; |
|
81 /// \brief The value type of the algorithms. |
|
82 typedef _Number Number; |
|
83 /// \brief The capacity map on the edges. |
|
84 typedef _CapacityMap CapacityMap; |
|
85 /// \brief The flow map on the edges. |
|
86 typedef _FlowMap FlowMap; |
|
87 /// \brief The tolerance used by the algorithm. |
|
88 typedef _Tolerance Tolerance; |
|
89 |
|
90 typedef ResGraphAdaptor<Graph, Number, CapacityMap, |
|
91 FlowMap, Tolerance> ResGraph; |
|
92 |
|
93 private: |
127 private: |
94 |
128 |
95 typedef typename Graph::Node Node; |
129 GRAPH_TYPEDEFS(typename Graph); |
96 typedef typename Graph::Edge Edge; |
130 typedef typename Graph::template NodeMap<Edge> PredMap; |
97 |
131 |
98 typedef typename Graph::NodeIt NodeIt; |
132 const Graph& _graph; |
99 typedef typename Graph::EdgeIt EdgeIt; |
133 const CapacityMap* _capacity; |
100 typedef typename Graph::InEdgeIt InEdgeIt; |
134 |
101 typedef typename Graph::OutEdgeIt OutEdgeIt; |
135 Node _source, _target; |
|
136 |
|
137 FlowMap* _flow; |
|
138 bool _local_flow; |
|
139 |
|
140 PredMap* _pred; |
|
141 std::vector<Node> _queue; |
|
142 |
|
143 Tolerance _tolerance; |
|
144 Value _flow_value; |
|
145 |
|
146 void createStructures() { |
|
147 if (!_flow) { |
|
148 _flow = Traits::createFlowMap(_graph); |
|
149 _local_flow = true; |
|
150 } |
|
151 if (!_pred) { |
|
152 _pred = new PredMap(_graph); |
|
153 } |
|
154 _queue.resize(countNodes(_graph)); |
|
155 } |
|
156 |
|
157 void destroyStructures() { |
|
158 if (_local_flow) { |
|
159 delete _flow; |
|
160 } |
|
161 if (_pred) { |
|
162 delete _pred; |
|
163 } |
|
164 } |
102 |
165 |
103 public: |
166 public: |
104 |
167 |
|
168 ///\name Named template parameters |
|
169 |
|
170 ///@{ |
|
171 |
|
172 template <typename _FlowMap> |
|
173 struct DefFlowMapTraits : public Traits { |
|
174 typedef _FlowMap FlowMap; |
|
175 static FlowMap *createFlowMap(const Graph&) { |
|
176 throw UninitializedParameter(); |
|
177 } |
|
178 }; |
|
179 |
|
180 /// \brief \ref named-templ-param "Named parameter" for setting |
|
181 /// FlowMap type |
|
182 /// |
|
183 /// \ref named-templ-param "Named parameter" for setting FlowMap |
|
184 /// type |
|
185 template <typename _FlowMap> |
|
186 struct DefFlowMap |
|
187 : public EdmondsKarp<Graph, CapacityMap, DefFlowMapTraits<_FlowMap> > { |
|
188 typedef EdmondsKarp<Graph, CapacityMap, DefFlowMapTraits<_FlowMap> > |
|
189 Create; |
|
190 }; |
|
191 |
|
192 |
|
193 /// @} |
|
194 |
105 /// \brief The constructor of the class. |
195 /// \brief The constructor of the class. |
106 /// |
196 /// |
107 /// The constructor of the class. |
197 /// The constructor of the class. |
108 /// \param graph The directed graph the algorithm runs on. |
198 /// \param graph The directed graph the algorithm runs on. |
|
199 /// \param capacity The capacity of the edges. |
109 /// \param source The source node. |
200 /// \param source The source node. |
110 /// \param target The target node. |
201 /// \param target The target node. |
111 /// \param capacity The capacity of the edges. |
202 EdmondsKarp(const Graph& graph, const CapacityMap& capacity, |
112 /// \param flow The flow of the edges. |
203 Node source, Node target) |
113 /// \param tolerance Tolerance class. |
204 : _graph(graph), _capacity(&capacity), _source(source), _target(target), |
114 EdmondsKarp(const Graph& graph, Node source, Node target, |
205 _flow(0), _local_flow(false), _pred(0), _tolerance(), _flow_value() |
115 const CapacityMap& capacity, FlowMap& flow, |
|
116 const Tolerance& tolerance = Tolerance()) |
|
117 : _graph(graph), _capacity(capacity), _flow(flow), |
|
118 _tolerance(tolerance), _resgraph(graph, capacity, flow, tolerance), |
|
119 _source(source), _target(target) |
|
120 { |
206 { |
121 if (_source == _target) { |
207 if (_source == _target) { |
122 throw InvalidArgument(); |
208 throw InvalidArgument(); |
123 } |
209 } |
124 } |
210 } |
|
211 |
|
212 /// \brief Destrcutor. |
|
213 /// |
|
214 /// Destructor. |
|
215 ~EdmondsKarp() { |
|
216 destroyStructures(); |
|
217 } |
|
218 |
|
219 /// \brief Sets the capacity map. |
|
220 /// |
|
221 /// Sets the capacity map. |
|
222 /// \return \c (*this) |
|
223 EdmondsKarp& capacityMap(const CapacityMap& map) { |
|
224 _capacity = ↦ |
|
225 return *this; |
|
226 } |
|
227 |
|
228 /// \brief Sets the flow map. |
|
229 /// |
|
230 /// Sets the flow map. |
|
231 /// \return \c (*this) |
|
232 EdmondsKarp& flowMap(FlowMap& map) { |
|
233 if (_local_flow) { |
|
234 delete _flow; |
|
235 _local_flow = false; |
|
236 } |
|
237 _flow = ↦ |
|
238 return *this; |
|
239 } |
|
240 |
|
241 /// \brief Returns the flow map. |
|
242 /// |
|
243 /// \return The flow map. |
|
244 const FlowMap& flowMap() { |
|
245 return *_flow; |
|
246 } |
|
247 |
|
248 /// \brief Sets the source node. |
|
249 /// |
|
250 /// Sets the source node. |
|
251 /// \return \c (*this) |
|
252 EdmondsKarp& source(const Node& node) { |
|
253 _source = node; |
|
254 return *this; |
|
255 } |
|
256 |
|
257 /// \brief Sets the target node. |
|
258 /// |
|
259 /// Sets the target node. |
|
260 /// \return \c (*this) |
|
261 EdmondsKarp& target(const Node& node) { |
|
262 _target = node; |
|
263 return *this; |
|
264 } |
|
265 |
|
266 /// \brief Sets the tolerance used by algorithm. |
|
267 /// |
|
268 /// Sets the tolerance used by algorithm. |
|
269 EdmondsKarp& tolerance(const Tolerance& tolerance) const { |
|
270 _tolerance = tolerance; |
|
271 return *this; |
|
272 } |
|
273 |
|
274 /// \brief Returns the tolerance used by algorithm. |
|
275 /// |
|
276 /// Returns the tolerance used by algorithm. |
|
277 const Tolerance& tolerance() const { |
|
278 return tolerance; |
|
279 } |
|
280 |
|
281 /// \name Execution control The simplest way to execute the |
|
282 /// algorithm is to use the \c run() member functions. |
|
283 /// \n |
|
284 /// If you need more control on initial solution or |
|
285 /// execution then you have to call one \ref init() function and then |
|
286 /// the start() or multiple times the \c augment() member function. |
|
287 |
|
288 ///@{ |
125 |
289 |
126 /// \brief Initializes the algorithm |
290 /// \brief Initializes the algorithm |
127 /// |
291 /// |
128 /// It sets the flow to empty flow. |
292 /// It sets the flow to empty flow. |
129 void init() { |
293 void init() { |
|
294 createStructures(); |
130 for (EdgeIt it(_graph); it != INVALID; ++it) { |
295 for (EdgeIt it(_graph); it != INVALID; ++it) { |
131 _flow.set(it, 0); |
296 _flow->set(it, 0); |
132 } |
297 } |
133 _value = 0; |
298 _flow_value = 0; |
134 } |
299 } |
135 |
300 |
136 /// \brief Initializes the algorithm |
301 /// \brief Initializes the algorithm |
137 /// |
302 /// |
138 /// If the flow map initially flow this let the flow map |
303 /// Initializes the flow to the \c flowMap. The \c flowMap should |
139 /// unchanged but the flow value will be set by the flow |
304 /// contain a feasible flow, ie. in each node excluding the source |
140 /// on the outedges from the source. |
305 /// and the target the incoming flow should be equal to the |
141 void flowInit() { |
306 /// outgoing flow. |
142 _value = 0; |
307 template <typename FlowMap> |
|
308 void flowInit(const FlowMap& flowMap) { |
|
309 createStructures(); |
|
310 for (EdgeIt e(_graph); e != INVALID; ++e) { |
|
311 _flow->set(e, flowMap[e]); |
|
312 } |
|
313 _flow_value = 0; |
143 for (OutEdgeIt jt(_graph, _source); jt != INVALID; ++jt) { |
314 for (OutEdgeIt jt(_graph, _source); jt != INVALID; ++jt) { |
144 _value += _flow[jt]; |
315 _flow_value += (*_flow)[jt]; |
145 } |
316 } |
146 for (InEdgeIt jt(_graph, _source); jt != INVALID; ++jt) { |
317 for (InEdgeIt jt(_graph, _source); jt != INVALID; ++jt) { |
147 _value -= _flow[jt]; |
318 _flow_value -= (*_flow)[jt]; |
148 } |
319 } |
149 } |
320 } |
150 |
321 |
151 /// \brief Initializes the algorithm |
322 /// \brief Initializes the algorithm |
152 /// |
323 /// |
153 /// If the flow map initially flow this let the flow map |
324 /// Initializes the flow to the \c flowMap. The \c flowMap should |
154 /// unchanged but the flow value will be set by the flow |
325 /// contain a feasible flow, ie. in each node excluding the source |
155 /// on the outedges from the source. It also checks that |
326 /// and the target the incoming flow should be equal to the |
156 /// the flow map really contains a flow. |
327 /// outgoing flow. |
157 /// \return %True when the flow map really a flow. |
328 /// \return %False when the given flowMap does not contain |
158 bool checkedFlowInit() { |
329 /// feasible flow. |
159 _value = 0; |
330 template <typename FlowMap> |
160 for (OutEdgeIt jt(_graph, _source); jt != INVALID; ++jt) { |
331 bool checkedFlowInit(const FlowMap& flowMap) { |
161 _value += _flow[jt]; |
332 createStructures(); |
162 } |
333 for (EdgeIt e(_graph); e != INVALID; ++e) { |
163 for (InEdgeIt jt(_graph, _source); jt != INVALID; ++jt) { |
334 _flow->set(e, flowMap[e]); |
164 _value -= _flow[jt]; |
|
165 } |
335 } |
166 for (NodeIt it(_graph); it != INVALID; ++it) { |
336 for (NodeIt it(_graph); it != INVALID; ++it) { |
167 if (it == _source || it == _target) continue; |
337 if (it == _source || it == _target) continue; |
168 Number outFlow = 0; |
338 Value outFlow = 0; |
169 for (OutEdgeIt jt(_graph, it); jt != INVALID; ++jt) { |
339 for (OutEdgeIt jt(_graph, it); jt != INVALID; ++jt) { |
170 outFlow += _flow[jt]; |
340 outFlow += (*_flow)[jt]; |
171 } |
341 } |
172 Number inFlow = 0; |
342 Value inFlow = 0; |
173 for (InEdgeIt jt(_graph, it); jt != INVALID; ++jt) { |
343 for (InEdgeIt jt(_graph, it); jt != INVALID; ++jt) { |
174 inFlow += _flow[jt]; |
344 inFlow += (*_flow)[jt]; |
175 } |
345 } |
176 if (_tolerance.different(outFlow, inFlow)) { |
346 if (_tolerance.different(outFlow, inFlow)) { |
177 return false; |
347 return false; |
178 } |
348 } |
179 } |
349 } |
180 for (EdgeIt it(_graph); it != INVALID; ++it) { |
350 for (EdgeIt it(_graph); it != INVALID; ++it) { |
181 if (_tolerance.less(_flow[it], 0)) return false; |
351 if (_tolerance.less((*_flow)[it], 0)) return false; |
182 if (_tolerance.less(_capacity[it], _flow[it])) return false; |
352 if (_tolerance.less((*_capacity)[it], (*_flow)[it])) return false; |
|
353 } |
|
354 _flow_value = 0; |
|
355 for (OutEdgeIt jt(_graph, _source); jt != INVALID; ++jt) { |
|
356 _flow_value += (*_flow)[jt]; |
|
357 } |
|
358 for (InEdgeIt jt(_graph, _source); jt != INVALID; ++jt) { |
|
359 _flow_value -= (*_flow)[jt]; |
183 } |
360 } |
184 return true; |
361 return true; |
185 } |
362 } |
186 |
363 |
187 /// \brief Augment the solution on an edge shortest path. |
364 /// \brief Augment the solution on an edge shortest path. |
193 /// capacity on the path. If there is not such path it gives back |
370 /// capacity on the path. If there is not such path it gives back |
194 /// false. |
371 /// false. |
195 /// \return %False when the augmenting is not success so the |
372 /// \return %False when the augmenting is not success so the |
196 /// current flow is a feasible and optimal solution. |
373 /// current flow is a feasible and optimal solution. |
197 bool augment() { |
374 bool augment() { |
198 typename Bfs<ResGraph> |
375 for (NodeIt n(_graph); n != INVALID; ++n) { |
199 ::template DefDistMap<NullMap<Node, int> > |
376 _pred->set(n, INVALID); |
200 ::Create bfs(_resgraph); |
377 } |
201 |
|
202 NullMap<Node, int> distMap; |
|
203 bfs.distMap(distMap); |
|
204 |
378 |
205 bfs.init(); |
379 int first = 0, last = 1; |
206 bfs.addSource(_source); |
380 |
207 bfs.start(_target); |
381 _queue[0] = _source; |
208 |
382 _pred->set(_source, OutEdgeIt(_graph, _source)); |
209 if (!bfs.reached(_target)) { |
383 |
210 return false; |
384 while (first != last && (*_pred)[_target] == INVALID) { |
211 } |
385 Node n = _queue[first++]; |
212 Number min = _resgraph.rescap(bfs.predEdge(_target)); |
386 |
213 for (Node it = bfs.predNode(_target); it != _source; |
387 for (OutEdgeIt e(_graph, n); e != INVALID; ++e) { |
214 it = bfs.predNode(it)) { |
388 Value rem = (*_capacity)[e] - (*_flow)[e]; |
215 if (min > _resgraph.rescap(bfs.predEdge(it))) { |
389 Node t = _graph.target(e); |
216 min = _resgraph.rescap(bfs.predEdge(it)); |
390 if (_tolerance.positive(rem) && (*_pred)[t] == INVALID) { |
217 } |
391 _pred->set(t, e); |
218 } |
392 _queue[last++] = t; |
219 for (Node it = _target; it != _source; it = bfs.predNode(it)) { |
393 } |
220 _resgraph.augment(bfs.predEdge(it), min); |
394 } |
221 } |
395 for (InEdgeIt e(_graph, n); e != INVALID; ++e) { |
222 _value += min; |
396 Value rem = (*_flow)[e]; |
223 return true; |
397 Node t = _graph.source(e); |
|
398 if (_tolerance.positive(rem) && (*_pred)[t] == INVALID) { |
|
399 _pred->set(t, e); |
|
400 _queue[last++] = t; |
|
401 } |
|
402 } |
|
403 } |
|
404 |
|
405 if ((*_pred)[_target] != INVALID) { |
|
406 Node n = _target; |
|
407 Edge e = (*_pred)[n]; |
|
408 |
|
409 Value prem = (*_capacity)[e] - (*_flow)[e]; |
|
410 n = _graph.source(e); |
|
411 while (n != _source) { |
|
412 e = (*_pred)[n]; |
|
413 if (_graph.target(e) == n) { |
|
414 Value rem = (*_capacity)[e] - (*_flow)[e]; |
|
415 if (rem < prem) prem = rem; |
|
416 n = _graph.source(e); |
|
417 } else { |
|
418 Value rem = (*_flow)[e]; |
|
419 if (rem < prem) prem = rem; |
|
420 n = _graph.target(e); |
|
421 } |
|
422 } |
|
423 |
|
424 n = _target; |
|
425 e = (*_pred)[n]; |
|
426 |
|
427 _flow->set(e, (*_flow)[e] + prem); |
|
428 n = _graph.source(e); |
|
429 while (n != _source) { |
|
430 e = (*_pred)[n]; |
|
431 if (_graph.target(e) == n) { |
|
432 _flow->set(e, (*_flow)[e] + prem); |
|
433 n = _graph.source(e); |
|
434 } else { |
|
435 _flow->set(e, (*_flow)[e] - prem); |
|
436 n = _graph.target(e); |
|
437 } |
|
438 } |
|
439 |
|
440 _flow_value += prem; |
|
441 return true; |
|
442 } else { |
|
443 return false; |
|
444 } |
224 } |
445 } |
225 |
446 |
226 /// \brief Executes the algorithm |
447 /// \brief Executes the algorithm |
227 /// |
448 /// |
228 /// It runs augmenting phases until the optimal solution is reached. |
449 /// It runs augmenting phases until the optimal solution is reached. |
229 void start() { |
450 void start() { |
230 while (augment()) {} |
451 while (augment()) {} |
231 } |
|
232 |
|
233 /// \brief Gives back the current flow value. |
|
234 /// |
|
235 /// Gives back the current flow _value. |
|
236 Number flowValue() const { |
|
237 return _value; |
|
238 } |
452 } |
239 |
453 |
240 /// \brief runs the algorithm. |
454 /// \brief runs the algorithm. |
241 /// |
455 /// |
242 /// It is just a shorthand for: |
456 /// It is just a shorthand for: |
248 void run() { |
462 void run() { |
249 init(); |
463 init(); |
250 start(); |
464 start(); |
251 } |
465 } |
252 |
466 |
|
467 /// @} |
|
468 |
|
469 /// \name Query Functions |
|
470 /// The result of the %Dijkstra algorithm can be obtained using these |
|
471 /// functions.\n |
|
472 /// Before the use of these functions, |
|
473 /// either run() or start() must be called. |
|
474 |
|
475 ///@{ |
|
476 |
|
477 /// \brief Returns the value of the maximum flow. |
|
478 /// |
|
479 /// Returns the value of the maximum flow by returning the excess |
|
480 /// of the target node \c t. This value equals to the value of |
|
481 /// the maximum flow already after the first phase. |
|
482 Value flowValue() const { |
|
483 return _flow_value; |
|
484 } |
|
485 |
|
486 |
|
487 /// \brief Returns the flow on the edge. |
|
488 /// |
|
489 /// Sets the \c flowMap to the flow on the edges. This method can |
|
490 /// be called after the second phase of algorithm. |
|
491 Value flow(const Edge& edge) const { |
|
492 return (*_flow)[edge]; |
|
493 } |
|
494 |
|
495 /// \brief Returns true when the node is on the source side of minimum cut. |
|
496 /// |
|
497 |
|
498 /// Returns true when the node is on the source side of minimum |
|
499 /// cut. This method can be called both after running \ref |
|
500 /// startFirstPhase() and \ref startSecondPhase(). |
|
501 bool minCut(const Node& node) const { |
|
502 return (*_pred)[node] != INVALID; |
|
503 } |
|
504 |
253 /// \brief Returns a minimum value cut. |
505 /// \brief Returns a minimum value cut. |
254 /// |
506 /// |
255 /// Sets \c cut to the characteristic vector of a minimum value cut |
507 /// Sets \c cut to the characteristic vector of a minimum value cut |
256 /// It simply calls the minMinCut member. |
508 /// It simply calls the minMinCut member. |
257 /// \retval cut Write node bool map. |
509 /// \retval cut Write node bool map. |
258 template <typename CutMap> |
510 template <typename CutMap> |
259 void minCut(CutMap& cut) const { |
511 void minCutMap(CutMap& cutMap) const { |
260 minMinCut(cut); |
512 for (NodeIt n(_graph); n != INVALID; ++n) { |
261 } |
513 cutMap.set(n, (*_pred)[n] != INVALID); |
262 |
514 } |
263 /// \brief Returns the inclusionwise minimum of the minimum value cuts. |
515 cutMap.set(_source, true); |
264 /// |
516 } |
265 /// Sets \c cut to the characteristic vector of the minimum value cut |
517 |
266 /// which is inclusionwise minimum. It is computed by processing a |
518 /// @} |
267 /// bfs from the source node \c source in the residual graph. |
519 |
268 /// \retval cut Write node bool map. |
|
269 template <typename CutMap> |
|
270 void minMinCut(CutMap& cut) const { |
|
271 |
|
272 typename Bfs<ResGraph> |
|
273 ::template DefDistMap<NullMap<Node, int> > |
|
274 ::template DefProcessedMap<CutMap> |
|
275 ::Create bfs(_resgraph); |
|
276 |
|
277 NullMap<Node, int> distMap; |
|
278 bfs.distMap(distMap); |
|
279 |
|
280 bfs.processedMap(cut); |
|
281 |
|
282 bfs.run(_source); |
|
283 } |
|
284 |
|
285 /// \brief Returns the inclusionwise minimum of the minimum value cuts. |
|
286 /// |
|
287 /// Sets \c cut to the characteristic vector of the minimum value cut |
|
288 /// which is inclusionwise minimum. It is computed by processing a |
|
289 /// bfs from the source node \c source in the residual graph. |
|
290 /// \retval cut Write node bool map. |
|
291 template <typename CutMap> |
|
292 void maxMinCut(CutMap& cut) const { |
|
293 |
|
294 typedef RevGraphAdaptor<const ResGraph> RevGraph; |
|
295 |
|
296 RevGraph revgraph(_resgraph); |
|
297 |
|
298 typename Bfs<RevGraph> |
|
299 ::template DefDistMap<NullMap<Node, int> > |
|
300 ::template DefPredMap<NullMap<Node, Edge> > |
|
301 ::template DefProcessedMap<NotWriteMap<CutMap> > |
|
302 ::Create bfs(revgraph); |
|
303 |
|
304 NullMap<Node, int> distMap; |
|
305 bfs.distMap(distMap); |
|
306 |
|
307 NullMap<Node, Edge> predMap; |
|
308 bfs.predMap(predMap); |
|
309 |
|
310 NotWriteMap<CutMap> notcut(cut); |
|
311 bfs.processedMap(notcut); |
|
312 |
|
313 bfs.run(_target); |
|
314 } |
|
315 |
|
316 /// \brief Returns the source node. |
|
317 /// |
|
318 /// Returns the source node. |
|
319 /// |
|
320 Node source() const { |
|
321 return _source; |
|
322 } |
|
323 |
|
324 /// \brief Returns the target node. |
|
325 /// |
|
326 /// Returns the target node. |
|
327 /// |
|
328 Node target() const { |
|
329 return _target; |
|
330 } |
|
331 |
|
332 /// \brief Returns a reference to capacity map. |
|
333 /// |
|
334 /// Returns a reference to capacity map. |
|
335 /// |
|
336 const CapacityMap &capacityMap() const { |
|
337 return *_capacity; |
|
338 } |
|
339 |
|
340 /// \brief Returns a reference to flow map. |
|
341 /// |
|
342 /// Returns a reference to flow map. |
|
343 /// |
|
344 const FlowMap &flowMap() const { |
|
345 return *_flow; |
|
346 } |
|
347 |
|
348 /// \brief Returns the tolerance used by algorithm. |
|
349 /// |
|
350 /// Returns the tolerance used by algorithm. |
|
351 const Tolerance& tolerance() const { |
|
352 return tolerance; |
|
353 } |
|
354 |
|
355 private: |
|
356 |
|
357 const Graph& _graph; |
|
358 const CapacityMap& _capacity; |
|
359 FlowMap& _flow; |
|
360 Tolerance _tolerance; |
|
361 |
|
362 ResGraph _resgraph; |
|
363 Node _source, _target; |
|
364 Number _value; |
|
365 |
|
366 }; |
520 }; |
367 |
521 |
368 } |
522 } |
369 |
523 |
370 #endif |
524 #endif |