thoneyvazul@1056
|
1 |
/* -*- mode: C++; indent-tabs-mode: nil; -*-
|
thoneyvazul@1056
|
2 |
*
|
thoneyvazul@1056
|
3 |
* This file is a part of LEMON, a generic C++ optimization library.
|
thoneyvazul@1056
|
4 |
*
|
thoneyvazul@1056
|
5 |
* Copyright (C) 2003-2010
|
thoneyvazul@1056
|
6 |
* Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
|
thoneyvazul@1056
|
7 |
* (Egervary Research Group on Combinatorial Optimization, EGRES).
|
thoneyvazul@1056
|
8 |
*
|
thoneyvazul@1056
|
9 |
* Permission to use, modify and distribute this software is granted
|
thoneyvazul@1056
|
10 |
* provided that this copyright notice appears in all copies. For
|
thoneyvazul@1056
|
11 |
* precise terms see the accompanying LICENSE file.
|
thoneyvazul@1056
|
12 |
*
|
thoneyvazul@1056
|
13 |
* This software is provided "AS IS" with no warranty of any kind,
|
thoneyvazul@1056
|
14 |
* express or implied, and with no claim as to its suitability for any
|
thoneyvazul@1056
|
15 |
* purpose.
|
thoneyvazul@1056
|
16 |
*
|
thoneyvazul@1056
|
17 |
*/
|
thoneyvazul@1056
|
18 |
|
thoneyvazul@1056
|
19 |
#ifndef LEMON_EDMONDS_KARP_H
|
thoneyvazul@1056
|
20 |
#define LEMON_EDMONDS_KARP_H
|
thoneyvazul@1056
|
21 |
|
thoneyvazul@1056
|
22 |
/// \file
|
thoneyvazul@1056
|
23 |
/// \ingroup max_flow
|
thoneyvazul@1056
|
24 |
/// \brief Implementation of the Edmonds-Karp algorithm.
|
thoneyvazul@1056
|
25 |
|
thoneyvazul@1056
|
26 |
#include <lemon/tolerance.h>
|
thoneyvazul@1056
|
27 |
#include <vector>
|
thoneyvazul@1056
|
28 |
|
thoneyvazul@1056
|
29 |
namespace lemon {
|
thoneyvazul@1056
|
30 |
|
thoneyvazul@1056
|
31 |
/// \brief Default traits class of EdmondsKarp class.
|
thoneyvazul@1056
|
32 |
///
|
thoneyvazul@1056
|
33 |
/// Default traits class of EdmondsKarp class.
|
thoneyvazul@1056
|
34 |
/// \param GR Digraph type.
|
thoneyvazul@1056
|
35 |
/// \param CAP Type of capacity map.
|
thoneyvazul@1056
|
36 |
template <typename GR, typename CAP>
|
thoneyvazul@1056
|
37 |
struct EdmondsKarpDefaultTraits {
|
thoneyvazul@1056
|
38 |
|
thoneyvazul@1056
|
39 |
/// \brief The digraph type the algorithm runs on.
|
thoneyvazul@1056
|
40 |
typedef GR Digraph;
|
thoneyvazul@1056
|
41 |
|
thoneyvazul@1056
|
42 |
/// \brief The type of the map that stores the arc capacities.
|
thoneyvazul@1056
|
43 |
///
|
thoneyvazul@1056
|
44 |
/// The type of the map that stores the arc capacities.
|
thoneyvazul@1056
|
45 |
/// It must meet the \ref concepts::ReadMap "ReadMap" concept.
|
thoneyvazul@1056
|
46 |
typedef CAP CapacityMap;
|
thoneyvazul@1056
|
47 |
|
thoneyvazul@1056
|
48 |
/// \brief The type of the length of the arcs.
|
thoneyvazul@1056
|
49 |
typedef typename CapacityMap::Value Value;
|
thoneyvazul@1056
|
50 |
|
thoneyvazul@1056
|
51 |
/// \brief The map type that stores the flow values.
|
thoneyvazul@1056
|
52 |
///
|
thoneyvazul@1056
|
53 |
/// The map type that stores the flow values.
|
thoneyvazul@1056
|
54 |
/// It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
|
thoneyvazul@1056
|
55 |
typedef typename Digraph::template ArcMap<Value> FlowMap;
|
thoneyvazul@1056
|
56 |
|
thoneyvazul@1056
|
57 |
/// \brief Instantiates a FlowMap.
|
thoneyvazul@1056
|
58 |
///
|
thoneyvazul@1056
|
59 |
/// This function instantiates a \ref FlowMap.
|
thoneyvazul@1056
|
60 |
/// \param digraph The digraph, to which we would like to define the flow map.
|
thoneyvazul@1056
|
61 |
static FlowMap* createFlowMap(const Digraph& digraph) {
|
thoneyvazul@1056
|
62 |
return new FlowMap(digraph);
|
thoneyvazul@1056
|
63 |
}
|
thoneyvazul@1056
|
64 |
|
thoneyvazul@1056
|
65 |
/// \brief The tolerance used by the algorithm
|
thoneyvazul@1056
|
66 |
///
|
thoneyvazul@1056
|
67 |
/// The tolerance used by the algorithm to handle inexact computation.
|
thoneyvazul@1056
|
68 |
typedef lemon::Tolerance<Value> Tolerance;
|
thoneyvazul@1056
|
69 |
|
thoneyvazul@1056
|
70 |
};
|
thoneyvazul@1056
|
71 |
|
thoneyvazul@1056
|
72 |
/// \ingroup max_flow
|
thoneyvazul@1056
|
73 |
///
|
thoneyvazul@1056
|
74 |
/// \brief Edmonds-Karp algorithms class.
|
thoneyvazul@1056
|
75 |
///
|
thoneyvazul@1056
|
76 |
/// This class provides an implementation of the \e Edmonds-Karp \e
|
thoneyvazul@1056
|
77 |
/// algorithm producing a flow of maximum value in directed
|
thoneyvazul@1056
|
78 |
/// digraphs. The Edmonds-Karp algorithm is slower than the Preflow
|
thoneyvazul@1056
|
79 |
/// algorithm but it has an advantage of the step-by-step execution
|
thoneyvazul@1056
|
80 |
/// control with feasible flow solutions. The \e source node, the \e
|
thoneyvazul@1056
|
81 |
/// target node, the \e capacity of the arcs and the \e starting \e
|
thoneyvazul@1056
|
82 |
/// flow value of the arcs should be passed to the algorithm
|
thoneyvazul@1056
|
83 |
/// through the constructor.
|
thoneyvazul@1056
|
84 |
///
|
thoneyvazul@1056
|
85 |
/// The time complexity of the algorithm is \f$ O(nm^2) \f$ in
|
thoneyvazul@1056
|
86 |
/// worst case. Always try the preflow algorithm instead of this if
|
thoneyvazul@1056
|
87 |
/// you just want to compute the optimal flow.
|
thoneyvazul@1056
|
88 |
///
|
thoneyvazul@1056
|
89 |
/// \param GR The digraph type the algorithm runs on.
|
thoneyvazul@1056
|
90 |
/// \param CAP The capacity map type.
|
thoneyvazul@1056
|
91 |
/// \param TR Traits class to set various data types used by
|
thoneyvazul@1056
|
92 |
/// the algorithm. The default traits class is \ref
|
thoneyvazul@1056
|
93 |
/// EdmondsKarpDefaultTraits. See \ref EdmondsKarpDefaultTraits for the
|
thoneyvazul@1056
|
94 |
/// documentation of a Edmonds-Karp traits class.
|
thoneyvazul@1056
|
95 |
|
thoneyvazul@1056
|
96 |
#ifdef DOXYGEN
|
thoneyvazul@1056
|
97 |
template <typename GR, typename CAP, typename TR>
|
thoneyvazul@1056
|
98 |
#else
|
thoneyvazul@1056
|
99 |
template <typename GR,
|
thoneyvazul@1056
|
100 |
typename CAP = typename GR::template ArcMap<int>,
|
thoneyvazul@1056
|
101 |
typename TR = EdmondsKarpDefaultTraits<GR, CAP> >
|
thoneyvazul@1056
|
102 |
#endif
|
thoneyvazul@1056
|
103 |
class EdmondsKarp {
|
thoneyvazul@1056
|
104 |
public:
|
thoneyvazul@1056
|
105 |
|
thoneyvazul@1056
|
106 |
typedef TR Traits;
|
thoneyvazul@1056
|
107 |
typedef typename Traits::Digraph Digraph;
|
thoneyvazul@1056
|
108 |
typedef typename Traits::CapacityMap CapacityMap;
|
thoneyvazul@1056
|
109 |
typedef typename Traits::Value Value;
|
thoneyvazul@1056
|
110 |
|
thoneyvazul@1056
|
111 |
typedef typename Traits::FlowMap FlowMap;
|
thoneyvazul@1056
|
112 |
typedef typename Traits::Tolerance Tolerance;
|
thoneyvazul@1056
|
113 |
|
thoneyvazul@1056
|
114 |
private:
|
thoneyvazul@1056
|
115 |
|
thoneyvazul@1056
|
116 |
TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);
|
thoneyvazul@1056
|
117 |
typedef typename Digraph::template NodeMap<Arc> PredMap;
|
thoneyvazul@1056
|
118 |
|
thoneyvazul@1056
|
119 |
const Digraph& _graph;
|
thoneyvazul@1056
|
120 |
const CapacityMap* _capacity;
|
thoneyvazul@1056
|
121 |
|
thoneyvazul@1056
|
122 |
Node _source, _target;
|
thoneyvazul@1056
|
123 |
|
thoneyvazul@1056
|
124 |
FlowMap* _flow;
|
thoneyvazul@1056
|
125 |
bool _local_flow;
|
thoneyvazul@1056
|
126 |
|
thoneyvazul@1056
|
127 |
PredMap* _pred;
|
thoneyvazul@1056
|
128 |
std::vector<Node> _queue;
|
thoneyvazul@1056
|
129 |
|
thoneyvazul@1056
|
130 |
Tolerance _tolerance;
|
thoneyvazul@1056
|
131 |
Value _flow_value;
|
thoneyvazul@1056
|
132 |
|
thoneyvazul@1056
|
133 |
void createStructures() {
|
thoneyvazul@1056
|
134 |
if (!_flow) {
|
thoneyvazul@1056
|
135 |
_flow = Traits::createFlowMap(_graph);
|
thoneyvazul@1056
|
136 |
_local_flow = true;
|
thoneyvazul@1056
|
137 |
}
|
thoneyvazul@1056
|
138 |
if (!_pred) {
|
thoneyvazul@1056
|
139 |
_pred = new PredMap(_graph);
|
thoneyvazul@1056
|
140 |
}
|
thoneyvazul@1056
|
141 |
_queue.resize(countNodes(_graph));
|
thoneyvazul@1056
|
142 |
}
|
thoneyvazul@1056
|
143 |
|
thoneyvazul@1056
|
144 |
void destroyStructures() {
|
thoneyvazul@1056
|
145 |
if (_local_flow) {
|
thoneyvazul@1056
|
146 |
delete _flow;
|
thoneyvazul@1056
|
147 |
}
|
thoneyvazul@1056
|
148 |
if (_pred) {
|
thoneyvazul@1056
|
149 |
delete _pred;
|
thoneyvazul@1056
|
150 |
}
|
thoneyvazul@1056
|
151 |
}
|
thoneyvazul@1056
|
152 |
|
thoneyvazul@1056
|
153 |
public:
|
thoneyvazul@1056
|
154 |
|
thoneyvazul@1056
|
155 |
///\name Named template parameters
|
thoneyvazul@1056
|
156 |
|
thoneyvazul@1056
|
157 |
///@{
|
thoneyvazul@1056
|
158 |
|
thoneyvazul@1056
|
159 |
template <typename T>
|
thoneyvazul@1056
|
160 |
struct DefFlowMapTraits : public Traits {
|
thoneyvazul@1056
|
161 |
typedef T FlowMap;
|
thoneyvazul@1056
|
162 |
static FlowMap *createFlowMap(const Digraph&) {
|
thoneyvazul@1056
|
163 |
LEMON_ASSERT(false,"Uninitialized parameter.");
|
thoneyvazul@1056
|
164 |
return 0;
|
thoneyvazul@1056
|
165 |
}
|
thoneyvazul@1056
|
166 |
};
|
thoneyvazul@1056
|
167 |
|
thoneyvazul@1056
|
168 |
/// \brief \ref named-templ-param "Named parameter" for setting
|
thoneyvazul@1056
|
169 |
/// FlowMap type
|
thoneyvazul@1056
|
170 |
///
|
thoneyvazul@1056
|
171 |
/// \ref named-templ-param "Named parameter" for setting FlowMap
|
thoneyvazul@1056
|
172 |
/// type
|
thoneyvazul@1056
|
173 |
template <typename T>
|
thoneyvazul@1056
|
174 |
struct DefFlowMap
|
thoneyvazul@1056
|
175 |
: public EdmondsKarp<Digraph, CapacityMap, DefFlowMapTraits<T> > {
|
thoneyvazul@1056
|
176 |
typedef EdmondsKarp<Digraph, CapacityMap, DefFlowMapTraits<T> >
|
thoneyvazul@1056
|
177 |
Create;
|
thoneyvazul@1056
|
178 |
};
|
thoneyvazul@1056
|
179 |
|
thoneyvazul@1056
|
180 |
|
thoneyvazul@1056
|
181 |
/// @}
|
thoneyvazul@1056
|
182 |
|
thoneyvazul@1056
|
183 |
protected:
|
thoneyvazul@1056
|
184 |
|
thoneyvazul@1056
|
185 |
EdmondsKarp() {}
|
thoneyvazul@1056
|
186 |
|
thoneyvazul@1056
|
187 |
public:
|
thoneyvazul@1056
|
188 |
|
thoneyvazul@1056
|
189 |
/// \brief The constructor of the class.
|
thoneyvazul@1056
|
190 |
///
|
thoneyvazul@1056
|
191 |
/// The constructor of the class.
|
thoneyvazul@1056
|
192 |
/// \param digraph The digraph the algorithm runs on.
|
thoneyvazul@1056
|
193 |
/// \param capacity The capacity of the arcs.
|
thoneyvazul@1056
|
194 |
/// \param source The source node.
|
thoneyvazul@1056
|
195 |
/// \param target The target node.
|
thoneyvazul@1056
|
196 |
EdmondsKarp(const Digraph& digraph, const CapacityMap& capacity,
|
thoneyvazul@1056
|
197 |
Node source, Node target)
|
thoneyvazul@1056
|
198 |
: _graph(digraph), _capacity(&capacity), _source(source), _target(target),
|
thoneyvazul@1056
|
199 |
_flow(0), _local_flow(false), _pred(0), _tolerance(), _flow_value()
|
thoneyvazul@1056
|
200 |
{
|
thoneyvazul@1056
|
201 |
LEMON_ASSERT(_source != _target,"Flow source and target are the same nodes.");
|
thoneyvazul@1056
|
202 |
}
|
thoneyvazul@1056
|
203 |
|
thoneyvazul@1056
|
204 |
/// \brief Destructor.
|
thoneyvazul@1056
|
205 |
///
|
thoneyvazul@1056
|
206 |
/// Destructor.
|
thoneyvazul@1056
|
207 |
~EdmondsKarp() {
|
thoneyvazul@1056
|
208 |
destroyStructures();
|
thoneyvazul@1056
|
209 |
}
|
thoneyvazul@1056
|
210 |
|
thoneyvazul@1056
|
211 |
/// \brief Sets the capacity map.
|
thoneyvazul@1056
|
212 |
///
|
thoneyvazul@1056
|
213 |
/// Sets the capacity map.
|
thoneyvazul@1056
|
214 |
/// \return \c (*this)
|
thoneyvazul@1056
|
215 |
EdmondsKarp& capacityMap(const CapacityMap& map) {
|
thoneyvazul@1056
|
216 |
_capacity = ↦
|
thoneyvazul@1056
|
217 |
return *this;
|
thoneyvazul@1056
|
218 |
}
|
thoneyvazul@1056
|
219 |
|
thoneyvazul@1056
|
220 |
/// \brief Sets the flow map.
|
thoneyvazul@1056
|
221 |
///
|
thoneyvazul@1056
|
222 |
/// Sets the flow map.
|
thoneyvazul@1056
|
223 |
/// \return \c (*this)
|
thoneyvazul@1056
|
224 |
EdmondsKarp& flowMap(FlowMap& map) {
|
thoneyvazul@1056
|
225 |
if (_local_flow) {
|
thoneyvazul@1056
|
226 |
delete _flow;
|
thoneyvazul@1056
|
227 |
_local_flow = false;
|
thoneyvazul@1056
|
228 |
}
|
thoneyvazul@1056
|
229 |
_flow = ↦
|
thoneyvazul@1056
|
230 |
return *this;
|
thoneyvazul@1056
|
231 |
}
|
thoneyvazul@1056
|
232 |
|
thoneyvazul@1056
|
233 |
/// \brief Returns the flow map.
|
thoneyvazul@1056
|
234 |
///
|
thoneyvazul@1056
|
235 |
/// \return The flow map.
|
thoneyvazul@1056
|
236 |
const FlowMap& flowMap() const {
|
thoneyvazul@1056
|
237 |
return *_flow;
|
thoneyvazul@1056
|
238 |
}
|
thoneyvazul@1056
|
239 |
|
thoneyvazul@1056
|
240 |
/// \brief Sets the source node.
|
thoneyvazul@1056
|
241 |
///
|
thoneyvazul@1056
|
242 |
/// Sets the source node.
|
thoneyvazul@1056
|
243 |
/// \return \c (*this)
|
thoneyvazul@1056
|
244 |
EdmondsKarp& source(const Node& node) {
|
thoneyvazul@1056
|
245 |
_source = node;
|
thoneyvazul@1056
|
246 |
return *this;
|
thoneyvazul@1056
|
247 |
}
|
thoneyvazul@1056
|
248 |
|
thoneyvazul@1056
|
249 |
/// \brief Sets the target node.
|
thoneyvazul@1056
|
250 |
///
|
thoneyvazul@1056
|
251 |
/// Sets the target node.
|
thoneyvazul@1056
|
252 |
/// \return \c (*this)
|
thoneyvazul@1056
|
253 |
EdmondsKarp& target(const Node& node) {
|
thoneyvazul@1056
|
254 |
_target = node;
|
thoneyvazul@1056
|
255 |
return *this;
|
thoneyvazul@1056
|
256 |
}
|
thoneyvazul@1056
|
257 |
|
thoneyvazul@1056
|
258 |
/// \brief Sets the tolerance used by algorithm.
|
thoneyvazul@1056
|
259 |
///
|
thoneyvazul@1056
|
260 |
/// Sets the tolerance used by algorithm.
|
thoneyvazul@1056
|
261 |
EdmondsKarp& tolerance(const Tolerance& tolerance) {
|
thoneyvazul@1056
|
262 |
_tolerance = tolerance;
|
thoneyvazul@1056
|
263 |
return *this;
|
thoneyvazul@1056
|
264 |
}
|
thoneyvazul@1056
|
265 |
|
thoneyvazul@1056
|
266 |
/// \brief Returns the tolerance used by algorithm.
|
thoneyvazul@1056
|
267 |
///
|
thoneyvazul@1056
|
268 |
/// Returns the tolerance used by algorithm.
|
thoneyvazul@1056
|
269 |
const Tolerance& tolerance() const {
|
thoneyvazul@1056
|
270 |
return _tolerance;
|
thoneyvazul@1056
|
271 |
}
|
thoneyvazul@1056
|
272 |
|
thoneyvazul@1056
|
273 |
/// \name Execution control
|
thoneyvazul@1056
|
274 |
/// The simplest way to execute the
|
thoneyvazul@1056
|
275 |
/// algorithm is to use the \c run() member functions.
|
thoneyvazul@1056
|
276 |
/// \n
|
thoneyvazul@1056
|
277 |
/// If you need more control on initial solution or
|
thoneyvazul@1056
|
278 |
/// execution then you have to call one \ref init() function and then
|
thoneyvazul@1056
|
279 |
/// the start() or multiple times the \c augment() member function.
|
thoneyvazul@1056
|
280 |
|
thoneyvazul@1056
|
281 |
///@{
|
thoneyvazul@1056
|
282 |
|
thoneyvazul@1056
|
283 |
/// \brief Initializes the algorithm
|
thoneyvazul@1056
|
284 |
///
|
thoneyvazul@1056
|
285 |
/// Sets the flow to empty flow.
|
thoneyvazul@1056
|
286 |
void init() {
|
thoneyvazul@1056
|
287 |
createStructures();
|
thoneyvazul@1056
|
288 |
for (ArcIt it(_graph); it != INVALID; ++it) {
|
thoneyvazul@1056
|
289 |
_flow->set(it, 0);
|
thoneyvazul@1056
|
290 |
}
|
thoneyvazul@1056
|
291 |
_flow_value = 0;
|
thoneyvazul@1056
|
292 |
}
|
thoneyvazul@1056
|
293 |
|
thoneyvazul@1056
|
294 |
/// \brief Initializes the algorithm
|
thoneyvazul@1056
|
295 |
///
|
thoneyvazul@1056
|
296 |
/// Initializes the flow to the \c flowMap. The \c flowMap should
|
thoneyvazul@1056
|
297 |
/// contain a feasible flow, ie. in each node excluding the source
|
thoneyvazul@1056
|
298 |
/// and the target the incoming flow should be equal to the
|
thoneyvazul@1056
|
299 |
/// outgoing flow.
|
thoneyvazul@1056
|
300 |
template <typename FlowMap>
|
thoneyvazul@1056
|
301 |
void flowInit(const FlowMap& flowMap) {
|
thoneyvazul@1056
|
302 |
createStructures();
|
thoneyvazul@1056
|
303 |
for (ArcIt e(_graph); e != INVALID; ++e) {
|
thoneyvazul@1056
|
304 |
_flow->set(e, flowMap[e]);
|
thoneyvazul@1056
|
305 |
}
|
thoneyvazul@1056
|
306 |
_flow_value = 0;
|
thoneyvazul@1056
|
307 |
for (OutArcIt jt(_graph, _source); jt != INVALID; ++jt) {
|
thoneyvazul@1056
|
308 |
_flow_value += (*_flow)[jt];
|
thoneyvazul@1056
|
309 |
}
|
thoneyvazul@1056
|
310 |
for (InArcIt jt(_graph, _source); jt != INVALID; ++jt) {
|
thoneyvazul@1056
|
311 |
_flow_value -= (*_flow)[jt];
|
thoneyvazul@1056
|
312 |
}
|
thoneyvazul@1056
|
313 |
}
|
thoneyvazul@1056
|
314 |
|
thoneyvazul@1056
|
315 |
/// \brief Initializes the algorithm
|
thoneyvazul@1056
|
316 |
///
|
thoneyvazul@1056
|
317 |
/// Initializes the flow to the \c flowMap. The \c flowMap should
|
thoneyvazul@1056
|
318 |
/// contain a feasible flow, ie. in each node excluding the source
|
thoneyvazul@1056
|
319 |
/// and the target the incoming flow should be equal to the
|
thoneyvazul@1056
|
320 |
/// outgoing flow.
|
thoneyvazul@1056
|
321 |
/// \return %False when the given flowMap does not contain
|
thoneyvazul@1056
|
322 |
/// feasible flow.
|
thoneyvazul@1056
|
323 |
template <typename FlowMap>
|
thoneyvazul@1056
|
324 |
bool checkedFlowInit(const FlowMap& flowMap) {
|
thoneyvazul@1056
|
325 |
createStructures();
|
thoneyvazul@1056
|
326 |
for (ArcIt e(_graph); e != INVALID; ++e) {
|
thoneyvazul@1056
|
327 |
_flow->set(e, flowMap[e]);
|
thoneyvazul@1056
|
328 |
}
|
thoneyvazul@1056
|
329 |
for (NodeIt it(_graph); it != INVALID; ++it) {
|
thoneyvazul@1056
|
330 |
if (it == _source || it == _target) continue;
|
thoneyvazul@1056
|
331 |
Value outFlow = 0;
|
thoneyvazul@1056
|
332 |
for (OutArcIt jt(_graph, it); jt != INVALID; ++jt) {
|
thoneyvazul@1056
|
333 |
outFlow += (*_flow)[jt];
|
thoneyvazul@1056
|
334 |
}
|
thoneyvazul@1056
|
335 |
Value inFlow = 0;
|
thoneyvazul@1056
|
336 |
for (InArcIt jt(_graph, it); jt != INVALID; ++jt) {
|
thoneyvazul@1056
|
337 |
inFlow += (*_flow)[jt];
|
thoneyvazul@1056
|
338 |
}
|
thoneyvazul@1056
|
339 |
if (_tolerance.different(outFlow, inFlow)) {
|
thoneyvazul@1056
|
340 |
return false;
|
thoneyvazul@1056
|
341 |
}
|
thoneyvazul@1056
|
342 |
}
|
thoneyvazul@1056
|
343 |
for (ArcIt it(_graph); it != INVALID; ++it) {
|
thoneyvazul@1056
|
344 |
if (_tolerance.less((*_flow)[it], 0)) return false;
|
thoneyvazul@1056
|
345 |
if (_tolerance.less((*_capacity)[it], (*_flow)[it])) return false;
|
thoneyvazul@1056
|
346 |
}
|
thoneyvazul@1056
|
347 |
_flow_value = 0;
|
thoneyvazul@1056
|
348 |
for (OutArcIt jt(_graph, _source); jt != INVALID; ++jt) {
|
thoneyvazul@1056
|
349 |
_flow_value += (*_flow)[jt];
|
thoneyvazul@1056
|
350 |
}
|
thoneyvazul@1056
|
351 |
for (InArcIt jt(_graph, _source); jt != INVALID; ++jt) {
|
thoneyvazul@1056
|
352 |
_flow_value -= (*_flow)[jt];
|
thoneyvazul@1056
|
353 |
}
|
thoneyvazul@1056
|
354 |
return true;
|
thoneyvazul@1056
|
355 |
}
|
thoneyvazul@1056
|
356 |
|
thoneyvazul@1056
|
357 |
/// \brief Augment the solution on an arc shortest path.
|
thoneyvazul@1056
|
358 |
///
|
thoneyvazul@1056
|
359 |
/// Augment the solution on an arc shortest path. It searches an
|
thoneyvazul@1056
|
360 |
/// arc shortest path between the source and the target
|
thoneyvazul@1056
|
361 |
/// in the residual digraph by the bfs algoritm.
|
thoneyvazul@1056
|
362 |
/// Then it increases the flow on this path with the minimal residual
|
thoneyvazul@1056
|
363 |
/// capacity on the path. If there is no such path it gives back
|
thoneyvazul@1056
|
364 |
/// false.
|
thoneyvazul@1056
|
365 |
/// \return %False when the augmenting didn't success so the
|
thoneyvazul@1056
|
366 |
/// current flow is a feasible and optimal solution.
|
thoneyvazul@1056
|
367 |
bool augment() {
|
thoneyvazul@1056
|
368 |
for (NodeIt n(_graph); n != INVALID; ++n) {
|
thoneyvazul@1056
|
369 |
_pred->set(n, INVALID);
|
thoneyvazul@1056
|
370 |
}
|
thoneyvazul@1056
|
371 |
|
thoneyvazul@1056
|
372 |
int first = 0, last = 1;
|
thoneyvazul@1056
|
373 |
|
thoneyvazul@1056
|
374 |
_queue[0] = _source;
|
thoneyvazul@1056
|
375 |
_pred->set(_source, OutArcIt(_graph, _source));
|
thoneyvazul@1056
|
376 |
|
thoneyvazul@1056
|
377 |
while (first != last && (*_pred)[_target] == INVALID) {
|
thoneyvazul@1056
|
378 |
Node n = _queue[first++];
|
thoneyvazul@1056
|
379 |
|
thoneyvazul@1056
|
380 |
for (OutArcIt e(_graph, n); e != INVALID; ++e) {
|
thoneyvazul@1056
|
381 |
Value rem = (*_capacity)[e] - (*_flow)[e];
|
thoneyvazul@1056
|
382 |
Node t = _graph.target(e);
|
thoneyvazul@1056
|
383 |
if (_tolerance.positive(rem) && (*_pred)[t] == INVALID) {
|
thoneyvazul@1056
|
384 |
_pred->set(t, e);
|
thoneyvazul@1056
|
385 |
_queue[last++] = t;
|
thoneyvazul@1056
|
386 |
}
|
thoneyvazul@1056
|
387 |
}
|
thoneyvazul@1056
|
388 |
for (InArcIt e(_graph, n); e != INVALID; ++e) {
|
thoneyvazul@1056
|
389 |
Value rem = (*_flow)[e];
|
thoneyvazul@1056
|
390 |
Node t = _graph.source(e);
|
thoneyvazul@1056
|
391 |
if (_tolerance.positive(rem) && (*_pred)[t] == INVALID) {
|
thoneyvazul@1056
|
392 |
_pred->set(t, e);
|
thoneyvazul@1056
|
393 |
_queue[last++] = t;
|
thoneyvazul@1056
|
394 |
}
|
thoneyvazul@1056
|
395 |
}
|
thoneyvazul@1056
|
396 |
}
|
thoneyvazul@1056
|
397 |
|
thoneyvazul@1056
|
398 |
if ((*_pred)[_target] != INVALID) {
|
thoneyvazul@1056
|
399 |
Node n = _target;
|
thoneyvazul@1056
|
400 |
Arc e = (*_pred)[n];
|
thoneyvazul@1056
|
401 |
|
thoneyvazul@1056
|
402 |
Value prem = (*_capacity)[e] - (*_flow)[e];
|
thoneyvazul@1056
|
403 |
n = _graph.source(e);
|
thoneyvazul@1056
|
404 |
while (n != _source) {
|
thoneyvazul@1056
|
405 |
e = (*_pred)[n];
|
thoneyvazul@1056
|
406 |
if (_graph.target(e) == n) {
|
thoneyvazul@1056
|
407 |
Value rem = (*_capacity)[e] - (*_flow)[e];
|
thoneyvazul@1056
|
408 |
if (rem < prem) prem = rem;
|
thoneyvazul@1056
|
409 |
n = _graph.source(e);
|
thoneyvazul@1056
|
410 |
} else {
|
thoneyvazul@1056
|
411 |
Value rem = (*_flow)[e];
|
thoneyvazul@1056
|
412 |
if (rem < prem) prem = rem;
|
thoneyvazul@1056
|
413 |
n = _graph.target(e);
|
thoneyvazul@1056
|
414 |
}
|
thoneyvazul@1056
|
415 |
}
|
thoneyvazul@1056
|
416 |
|
thoneyvazul@1056
|
417 |
n = _target;
|
thoneyvazul@1056
|
418 |
e = (*_pred)[n];
|
thoneyvazul@1056
|
419 |
|
thoneyvazul@1056
|
420 |
_flow->set(e, (*_flow)[e] + prem);
|
thoneyvazul@1056
|
421 |
n = _graph.source(e);
|
thoneyvazul@1056
|
422 |
while (n != _source) {
|
thoneyvazul@1056
|
423 |
e = (*_pred)[n];
|
thoneyvazul@1056
|
424 |
if (_graph.target(e) == n) {
|
thoneyvazul@1056
|
425 |
_flow->set(e, (*_flow)[e] + prem);
|
thoneyvazul@1056
|
426 |
n = _graph.source(e);
|
thoneyvazul@1056
|
427 |
} else {
|
thoneyvazul@1056
|
428 |
_flow->set(e, (*_flow)[e] - prem);
|
thoneyvazul@1056
|
429 |
n = _graph.target(e);
|
thoneyvazul@1056
|
430 |
}
|
thoneyvazul@1056
|
431 |
}
|
thoneyvazul@1056
|
432 |
|
thoneyvazul@1056
|
433 |
_flow_value += prem;
|
thoneyvazul@1056
|
434 |
return true;
|
thoneyvazul@1056
|
435 |
} else {
|
thoneyvazul@1056
|
436 |
return false;
|
thoneyvazul@1056
|
437 |
}
|
thoneyvazul@1056
|
438 |
}
|
thoneyvazul@1056
|
439 |
|
thoneyvazul@1056
|
440 |
/// \brief Executes the algorithm
|
thoneyvazul@1056
|
441 |
///
|
thoneyvazul@1056
|
442 |
/// It runs augmenting phases until the optimal solution is reached.
|
thoneyvazul@1056
|
443 |
void start() {
|
thoneyvazul@1056
|
444 |
while (augment()) {}
|
thoneyvazul@1056
|
445 |
}
|
thoneyvazul@1056
|
446 |
|
thoneyvazul@1056
|
447 |
/// \brief Runs the algorithm.
|
thoneyvazul@1056
|
448 |
///
|
thoneyvazul@1056
|
449 |
/// It is just a shorthand for:
|
thoneyvazul@1056
|
450 |
///
|
thoneyvazul@1056
|
451 |
///\code
|
thoneyvazul@1056
|
452 |
/// ek.init();
|
thoneyvazul@1056
|
453 |
/// ek.start();
|
thoneyvazul@1056
|
454 |
///\endcode
|
thoneyvazul@1056
|
455 |
void run() {
|
thoneyvazul@1056
|
456 |
init();
|
thoneyvazul@1056
|
457 |
start();
|
thoneyvazul@1056
|
458 |
}
|
thoneyvazul@1056
|
459 |
|
thoneyvazul@1056
|
460 |
/// @}
|
thoneyvazul@1056
|
461 |
|
thoneyvazul@1056
|
462 |
/// \name Query Functions
|
thoneyvazul@1056
|
463 |
/// The result of the Edmonds-Karp algorithm can be obtained using these
|
thoneyvazul@1056
|
464 |
/// functions.\n
|
thoneyvazul@1056
|
465 |
/// Before the use of these functions,
|
thoneyvazul@1056
|
466 |
/// either run() or start() must be called.
|
thoneyvazul@1056
|
467 |
|
thoneyvazul@1056
|
468 |
///@{
|
thoneyvazul@1056
|
469 |
|
thoneyvazul@1056
|
470 |
/// \brief Returns the value of the maximum flow.
|
thoneyvazul@1056
|
471 |
///
|
thoneyvazul@1056
|
472 |
/// Returns the value of the maximum flow by returning the excess
|
thoneyvazul@1056
|
473 |
/// of the target node \c t.
|
thoneyvazul@1056
|
474 |
|
thoneyvazul@1056
|
475 |
Value flowValue() const {
|
thoneyvazul@1056
|
476 |
return _flow_value;
|
thoneyvazul@1056
|
477 |
}
|
thoneyvazul@1056
|
478 |
|
thoneyvazul@1056
|
479 |
|
thoneyvazul@1056
|
480 |
/// \brief Returns the flow on the arc.
|
thoneyvazul@1056
|
481 |
///
|
thoneyvazul@1056
|
482 |
/// Sets the \c flowMap to the flow on the arcs.
|
thoneyvazul@1056
|
483 |
Value flow(const Arc& arc) const {
|
thoneyvazul@1056
|
484 |
return (*_flow)[arc];
|
thoneyvazul@1056
|
485 |
}
|
thoneyvazul@1056
|
486 |
|
thoneyvazul@1056
|
487 |
/// \brief Returns true when the node is on the source side of minimum cut.
|
thoneyvazul@1056
|
488 |
///
|
thoneyvazul@1056
|
489 |
|
thoneyvazul@1056
|
490 |
/// Returns true when the node is on the source side of minimum
|
thoneyvazul@1056
|
491 |
/// cut.
|
thoneyvazul@1056
|
492 |
|
thoneyvazul@1056
|
493 |
bool minCut(const Node& node) const {
|
thoneyvazul@1056
|
494 |
return ((*_pred)[node] != INVALID) or node == _source;
|
thoneyvazul@1056
|
495 |
}
|
thoneyvazul@1056
|
496 |
|
thoneyvazul@1056
|
497 |
/// \brief Returns a minimum value cut.
|
thoneyvazul@1056
|
498 |
///
|
thoneyvazul@1056
|
499 |
/// Sets \c cutMap to the characteristic vector of a minimum value cut.
|
thoneyvazul@1056
|
500 |
|
thoneyvazul@1056
|
501 |
template <typename CutMap>
|
thoneyvazul@1056
|
502 |
void minCutMap(CutMap& cutMap) const {
|
thoneyvazul@1056
|
503 |
for (NodeIt n(_graph); n != INVALID; ++n) {
|
thoneyvazul@1056
|
504 |
cutMap.set(n, (*_pred)[n] != INVALID);
|
thoneyvazul@1056
|
505 |
}
|
thoneyvazul@1056
|
506 |
cutMap.set(_source, true);
|
thoneyvazul@1056
|
507 |
}
|
thoneyvazul@1056
|
508 |
|
thoneyvazul@1056
|
509 |
/// @}
|
thoneyvazul@1056
|
510 |
|
thoneyvazul@1056
|
511 |
};
|
thoneyvazul@1056
|
512 |
|
thoneyvazul@1056
|
513 |
}
|
thoneyvazul@1056
|
514 |
|
thoneyvazul@1056
|
515 |
#endif
|