alpar@389
|
1 |
/* -*- mode: C++; indent-tabs-mode: nil; -*-
|
alpar@389
|
2 |
*
|
alpar@389
|
3 |
* This file is a part of LEMON, a generic C++ optimization library.
|
alpar@389
|
4 |
*
|
alpar@389
|
5 |
* Copyright (C) 2003-2008
|
alpar@389
|
6 |
* Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
|
alpar@389
|
7 |
* (Egervary Research Group on Combinatorial Optimization, EGRES).
|
alpar@389
|
8 |
*
|
alpar@389
|
9 |
* Permission to use, modify and distribute this software is granted
|
alpar@389
|
10 |
* provided that this copyright notice appears in all copies. For
|
alpar@389
|
11 |
* precise terms see the accompanying LICENSE file.
|
alpar@389
|
12 |
*
|
alpar@389
|
13 |
* This software is provided "AS IS" with no warranty of any kind,
|
alpar@389
|
14 |
* express or implied, and with no claim as to its suitability for any
|
alpar@389
|
15 |
* purpose.
|
alpar@389
|
16 |
*
|
alpar@389
|
17 |
*/
|
alpar@389
|
18 |
|
alpar@389
|
19 |
#ifndef LEMON_PREFLOW_H
|
alpar@389
|
20 |
#define LEMON_PREFLOW_H
|
alpar@389
|
21 |
|
alpar@389
|
22 |
#include <lemon/error.h>
|
alpar@389
|
23 |
#include <lemon/tolerance.h>
|
alpar@389
|
24 |
#include <lemon/elevator.h>
|
alpar@389
|
25 |
|
alpar@389
|
26 |
/// \file
|
alpar@389
|
27 |
/// \ingroup max_flow
|
alpar@389
|
28 |
/// \brief Implementation of the preflow algorithm.
|
alpar@389
|
29 |
|
alpar@389
|
30 |
namespace lemon {
|
alpar@389
|
31 |
|
alpar@389
|
32 |
/// \brief Default traits class of Preflow class.
|
alpar@389
|
33 |
///
|
alpar@389
|
34 |
/// Default traits class of Preflow class.
|
alpar@389
|
35 |
/// \param _Graph Digraph type.
|
alpar@389
|
36 |
/// \param _CapacityMap Type of capacity map.
|
alpar@389
|
37 |
template <typename _Graph, typename _CapacityMap>
|
alpar@389
|
38 |
struct PreflowDefaultTraits {
|
alpar@389
|
39 |
|
alpar@389
|
40 |
/// \brief The digraph type the algorithm runs on.
|
alpar@389
|
41 |
typedef _Graph Digraph;
|
alpar@389
|
42 |
|
alpar@389
|
43 |
/// \brief The type of the map that stores the arc capacities.
|
alpar@389
|
44 |
///
|
alpar@389
|
45 |
/// The type of the map that stores the arc capacities.
|
alpar@389
|
46 |
/// It must meet the \ref concepts::ReadMap "ReadMap" concept.
|
alpar@389
|
47 |
typedef _CapacityMap CapacityMap;
|
alpar@389
|
48 |
|
alpar@389
|
49 |
/// \brief The type of the length of the arcs.
|
alpar@389
|
50 |
typedef typename CapacityMap::Value Value;
|
alpar@389
|
51 |
|
alpar@389
|
52 |
/// \brief The map type that stores the flow values.
|
alpar@389
|
53 |
///
|
alpar@389
|
54 |
/// The map type that stores the flow values.
|
alpar@389
|
55 |
/// It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
|
alpar@389
|
56 |
typedef typename Digraph::template ArcMap<Value> FlowMap;
|
alpar@389
|
57 |
|
alpar@389
|
58 |
/// \brief Instantiates a FlowMap.
|
alpar@389
|
59 |
///
|
alpar@389
|
60 |
/// This function instantiates a \ref FlowMap.
|
alpar@389
|
61 |
/// \param digraph The digraph, to which we would like to define
|
alpar@389
|
62 |
/// the flow map.
|
alpar@389
|
63 |
static FlowMap* createFlowMap(const Digraph& digraph) {
|
alpar@389
|
64 |
return new FlowMap(digraph);
|
alpar@389
|
65 |
}
|
alpar@389
|
66 |
|
alpar@389
|
67 |
/// \brief The eleavator type used by Preflow algorithm.
|
alpar@389
|
68 |
///
|
alpar@389
|
69 |
/// The elevator type used by Preflow algorithm.
|
alpar@389
|
70 |
///
|
alpar@389
|
71 |
/// \sa Elevator
|
alpar@389
|
72 |
/// \sa LinkedElevator
|
alpar@389
|
73 |
typedef LinkedElevator<Digraph, typename Digraph::Node> Elevator;
|
alpar@389
|
74 |
|
alpar@389
|
75 |
/// \brief Instantiates an Elevator.
|
alpar@389
|
76 |
///
|
alpar@389
|
77 |
/// This function instantiates a \ref Elevator.
|
alpar@389
|
78 |
/// \param digraph The digraph, to which we would like to define
|
alpar@389
|
79 |
/// the elevator.
|
alpar@389
|
80 |
/// \param max_level The maximum level of the elevator.
|
alpar@389
|
81 |
static Elevator* createElevator(const Digraph& digraph, int max_level) {
|
alpar@389
|
82 |
return new Elevator(digraph, max_level);
|
alpar@389
|
83 |
}
|
alpar@389
|
84 |
|
alpar@389
|
85 |
/// \brief The tolerance used by the algorithm
|
alpar@389
|
86 |
///
|
alpar@389
|
87 |
/// The tolerance used by the algorithm to handle inexact computation.
|
alpar@389
|
88 |
typedef lemon::Tolerance<Value> Tolerance;
|
alpar@389
|
89 |
|
alpar@389
|
90 |
};
|
alpar@389
|
91 |
|
alpar@389
|
92 |
|
alpar@389
|
93 |
/// \ingroup max_flow
|
alpar@389
|
94 |
///
|
alpar@389
|
95 |
/// \brief %Preflow algorithms class.
|
alpar@389
|
96 |
///
|
alpar@389
|
97 |
/// This class provides an implementation of the Goldberg's \e
|
alpar@389
|
98 |
/// preflow \e algorithm producing a flow of maximum value in a
|
alpar@389
|
99 |
/// digraph. The preflow algorithms are the fastest known max
|
alpar@389
|
100 |
/// flow algorithms. The current implementation use a mixture of the
|
alpar@389
|
101 |
/// \e "highest label" and the \e "bound decrease" heuristics.
|
alpar@389
|
102 |
/// The worst case time complexity of the algorithm is \f$O(n^2\sqrt{e})\f$.
|
alpar@389
|
103 |
///
|
alpar@389
|
104 |
/// The algorithm consists from two phases. After the first phase
|
alpar@389
|
105 |
/// the maximal flow value and the minimum cut can be obtained. The
|
alpar@389
|
106 |
/// second phase constructs the feasible maximum flow on each arc.
|
alpar@389
|
107 |
///
|
alpar@389
|
108 |
/// \param _Graph The digraph type the algorithm runs on.
|
alpar@389
|
109 |
/// \param _CapacityMap The flow map type.
|
alpar@389
|
110 |
/// \param _Traits Traits class to set various data types used by
|
alpar@389
|
111 |
/// the algorithm. The default traits class is \ref
|
alpar@389
|
112 |
/// PreflowDefaultTraits. See \ref PreflowDefaultTraits for the
|
alpar@389
|
113 |
/// documentation of a %Preflow traits class.
|
alpar@389
|
114 |
///
|
alpar@389
|
115 |
///\author Jacint Szabo and Balazs Dezso
|
alpar@389
|
116 |
#ifdef DOXYGEN
|
alpar@389
|
117 |
template <typename _Graph, typename _CapacityMap, typename _Traits>
|
alpar@389
|
118 |
#else
|
alpar@389
|
119 |
template <typename _Graph,
|
alpar@389
|
120 |
typename _CapacityMap = typename _Graph::template ArcMap<int>,
|
alpar@389
|
121 |
typename _Traits = PreflowDefaultTraits<_Graph, _CapacityMap> >
|
alpar@389
|
122 |
#endif
|
alpar@389
|
123 |
class Preflow {
|
alpar@389
|
124 |
public:
|
alpar@389
|
125 |
|
alpar@389
|
126 |
typedef _Traits Traits;
|
alpar@389
|
127 |
typedef typename Traits::Digraph Digraph;
|
alpar@389
|
128 |
typedef typename Traits::CapacityMap CapacityMap;
|
alpar@389
|
129 |
typedef typename Traits::Value Value;
|
alpar@389
|
130 |
|
alpar@389
|
131 |
typedef typename Traits::FlowMap FlowMap;
|
alpar@389
|
132 |
typedef typename Traits::Elevator Elevator;
|
alpar@389
|
133 |
typedef typename Traits::Tolerance Tolerance;
|
alpar@389
|
134 |
|
alpar@389
|
135 |
/// \brief \ref Exception for uninitialized parameters.
|
alpar@389
|
136 |
///
|
alpar@389
|
137 |
/// This error represents problems in the initialization
|
alpar@389
|
138 |
/// of the parameters of the algorithms.
|
alpar@389
|
139 |
class UninitializedParameter : public lemon::Exception {
|
alpar@389
|
140 |
public:
|
alpar@389
|
141 |
virtual const char* what() const throw() {
|
alpar@389
|
142 |
return "lemon::Preflow::UninitializedParameter";
|
alpar@389
|
143 |
}
|
alpar@389
|
144 |
};
|
alpar@389
|
145 |
|
alpar@389
|
146 |
private:
|
alpar@389
|
147 |
|
alpar@389
|
148 |
TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);
|
alpar@389
|
149 |
|
alpar@389
|
150 |
const Digraph& _graph;
|
alpar@389
|
151 |
const CapacityMap* _capacity;
|
alpar@389
|
152 |
|
alpar@389
|
153 |
int _node_num;
|
alpar@389
|
154 |
|
alpar@389
|
155 |
Node _source, _target;
|
alpar@389
|
156 |
|
alpar@389
|
157 |
FlowMap* _flow;
|
alpar@389
|
158 |
bool _local_flow;
|
alpar@389
|
159 |
|
alpar@389
|
160 |
Elevator* _level;
|
alpar@389
|
161 |
bool _local_level;
|
alpar@389
|
162 |
|
alpar@389
|
163 |
typedef typename Digraph::template NodeMap<Value> ExcessMap;
|
alpar@389
|
164 |
ExcessMap* _excess;
|
alpar@389
|
165 |
|
alpar@389
|
166 |
Tolerance _tolerance;
|
alpar@389
|
167 |
|
alpar@389
|
168 |
bool _phase;
|
alpar@389
|
169 |
|
alpar@389
|
170 |
|
alpar@389
|
171 |
void createStructures() {
|
alpar@389
|
172 |
_node_num = countNodes(_graph);
|
alpar@389
|
173 |
|
alpar@389
|
174 |
if (!_flow) {
|
alpar@389
|
175 |
_flow = Traits::createFlowMap(_graph);
|
alpar@389
|
176 |
_local_flow = true;
|
alpar@389
|
177 |
}
|
alpar@389
|
178 |
if (!_level) {
|
alpar@389
|
179 |
_level = Traits::createElevator(_graph, _node_num);
|
alpar@389
|
180 |
_local_level = true;
|
alpar@389
|
181 |
}
|
alpar@389
|
182 |
if (!_excess) {
|
alpar@389
|
183 |
_excess = new ExcessMap(_graph);
|
alpar@389
|
184 |
}
|
alpar@389
|
185 |
}
|
alpar@389
|
186 |
|
alpar@389
|
187 |
void destroyStructures() {
|
alpar@389
|
188 |
if (_local_flow) {
|
alpar@389
|
189 |
delete _flow;
|
alpar@389
|
190 |
}
|
alpar@389
|
191 |
if (_local_level) {
|
alpar@389
|
192 |
delete _level;
|
alpar@389
|
193 |
}
|
alpar@389
|
194 |
if (_excess) {
|
alpar@389
|
195 |
delete _excess;
|
alpar@389
|
196 |
}
|
alpar@389
|
197 |
}
|
alpar@389
|
198 |
|
alpar@389
|
199 |
public:
|
alpar@389
|
200 |
|
alpar@389
|
201 |
typedef Preflow Create;
|
alpar@389
|
202 |
|
alpar@389
|
203 |
///\name Named template parameters
|
alpar@389
|
204 |
|
alpar@389
|
205 |
///@{
|
alpar@389
|
206 |
|
alpar@389
|
207 |
template <typename _FlowMap>
|
alpar@389
|
208 |
struct DefFlowMapTraits : public Traits {
|
alpar@389
|
209 |
typedef _FlowMap FlowMap;
|
alpar@389
|
210 |
static FlowMap *createFlowMap(const Digraph&) {
|
alpar@389
|
211 |
throw UninitializedParameter();
|
alpar@389
|
212 |
}
|
alpar@389
|
213 |
};
|
alpar@389
|
214 |
|
alpar@389
|
215 |
/// \brief \ref named-templ-param "Named parameter" for setting
|
alpar@389
|
216 |
/// FlowMap type
|
alpar@389
|
217 |
///
|
alpar@389
|
218 |
/// \ref named-templ-param "Named parameter" for setting FlowMap
|
alpar@389
|
219 |
/// type
|
alpar@389
|
220 |
template <typename _FlowMap>
|
alpar@389
|
221 |
struct DefFlowMap
|
alpar@389
|
222 |
: public Preflow<Digraph, CapacityMap, DefFlowMapTraits<_FlowMap> > {
|
alpar@389
|
223 |
typedef Preflow<Digraph, CapacityMap,
|
alpar@389
|
224 |
DefFlowMapTraits<_FlowMap> > Create;
|
alpar@389
|
225 |
};
|
alpar@389
|
226 |
|
alpar@389
|
227 |
template <typename _Elevator>
|
alpar@389
|
228 |
struct DefElevatorTraits : public Traits {
|
alpar@389
|
229 |
typedef _Elevator Elevator;
|
alpar@389
|
230 |
static Elevator *createElevator(const Digraph&, int) {
|
alpar@389
|
231 |
throw UninitializedParameter();
|
alpar@389
|
232 |
}
|
alpar@389
|
233 |
};
|
alpar@389
|
234 |
|
alpar@389
|
235 |
/// \brief \ref named-templ-param "Named parameter" for setting
|
alpar@389
|
236 |
/// Elevator type
|
alpar@389
|
237 |
///
|
alpar@389
|
238 |
/// \ref named-templ-param "Named parameter" for setting Elevator
|
alpar@389
|
239 |
/// type
|
alpar@389
|
240 |
template <typename _Elevator>
|
alpar@389
|
241 |
struct DefElevator
|
alpar@389
|
242 |
: public Preflow<Digraph, CapacityMap, DefElevatorTraits<_Elevator> > {
|
alpar@389
|
243 |
typedef Preflow<Digraph, CapacityMap,
|
alpar@389
|
244 |
DefElevatorTraits<_Elevator> > Create;
|
alpar@389
|
245 |
};
|
alpar@389
|
246 |
|
alpar@389
|
247 |
template <typename _Elevator>
|
alpar@389
|
248 |
struct DefStandardElevatorTraits : public Traits {
|
alpar@389
|
249 |
typedef _Elevator Elevator;
|
alpar@389
|
250 |
static Elevator *createElevator(const Digraph& digraph, int max_level) {
|
alpar@389
|
251 |
return new Elevator(digraph, max_level);
|
alpar@389
|
252 |
}
|
alpar@389
|
253 |
};
|
alpar@389
|
254 |
|
alpar@389
|
255 |
/// \brief \ref named-templ-param "Named parameter" for setting
|
alpar@389
|
256 |
/// Elevator type
|
alpar@389
|
257 |
///
|
alpar@389
|
258 |
/// \ref named-templ-param "Named parameter" for setting Elevator
|
alpar@389
|
259 |
/// type. The Elevator should be standard constructor interface, ie.
|
alpar@389
|
260 |
/// the digraph and the maximum level should be passed to it.
|
alpar@389
|
261 |
template <typename _Elevator>
|
alpar@389
|
262 |
struct DefStandardElevator
|
alpar@389
|
263 |
: public Preflow<Digraph, CapacityMap,
|
alpar@389
|
264 |
DefStandardElevatorTraits<_Elevator> > {
|
alpar@389
|
265 |
typedef Preflow<Digraph, CapacityMap,
|
alpar@389
|
266 |
DefStandardElevatorTraits<_Elevator> > Create;
|
alpar@389
|
267 |
};
|
alpar@389
|
268 |
|
alpar@389
|
269 |
/// @}
|
alpar@389
|
270 |
|
alpar@389
|
271 |
protected:
|
alpar@389
|
272 |
|
alpar@389
|
273 |
Preflow() {}
|
alpar@389
|
274 |
|
alpar@389
|
275 |
public:
|
alpar@389
|
276 |
|
alpar@389
|
277 |
|
alpar@389
|
278 |
/// \brief The constructor of the class.
|
alpar@389
|
279 |
///
|
alpar@389
|
280 |
/// The constructor of the class.
|
alpar@389
|
281 |
/// \param digraph The digraph the algorithm runs on.
|
alpar@389
|
282 |
/// \param capacity The capacity of the arcs.
|
alpar@389
|
283 |
/// \param source The source node.
|
alpar@389
|
284 |
/// \param target The target node.
|
alpar@389
|
285 |
Preflow(const Digraph& digraph, const CapacityMap& capacity,
|
alpar@389
|
286 |
Node source, Node target)
|
alpar@389
|
287 |
: _graph(digraph), _capacity(&capacity),
|
alpar@389
|
288 |
_node_num(0), _source(source), _target(target),
|
alpar@389
|
289 |
_flow(0), _local_flow(false),
|
alpar@389
|
290 |
_level(0), _local_level(false),
|
alpar@389
|
291 |
_excess(0), _tolerance(), _phase() {}
|
alpar@389
|
292 |
|
alpar@389
|
293 |
/// \brief Destrcutor.
|
alpar@389
|
294 |
///
|
alpar@389
|
295 |
/// Destructor.
|
alpar@389
|
296 |
~Preflow() {
|
alpar@389
|
297 |
destroyStructures();
|
alpar@389
|
298 |
}
|
alpar@389
|
299 |
|
alpar@389
|
300 |
/// \brief Sets the capacity map.
|
alpar@389
|
301 |
///
|
alpar@389
|
302 |
/// Sets the capacity map.
|
alpar@389
|
303 |
/// \return \c (*this)
|
alpar@389
|
304 |
Preflow& capacityMap(const CapacityMap& map) {
|
alpar@389
|
305 |
_capacity = ↦
|
alpar@389
|
306 |
return *this;
|
alpar@389
|
307 |
}
|
alpar@389
|
308 |
|
alpar@389
|
309 |
/// \brief Sets the flow map.
|
alpar@389
|
310 |
///
|
alpar@389
|
311 |
/// Sets the flow map.
|
alpar@389
|
312 |
/// \return \c (*this)
|
alpar@389
|
313 |
Preflow& flowMap(FlowMap& map) {
|
alpar@389
|
314 |
if (_local_flow) {
|
alpar@389
|
315 |
delete _flow;
|
alpar@389
|
316 |
_local_flow = false;
|
alpar@389
|
317 |
}
|
alpar@389
|
318 |
_flow = ↦
|
alpar@389
|
319 |
return *this;
|
alpar@389
|
320 |
}
|
alpar@389
|
321 |
|
alpar@389
|
322 |
/// \brief Returns the flow map.
|
alpar@389
|
323 |
///
|
alpar@389
|
324 |
/// \return The flow map.
|
alpar@389
|
325 |
const FlowMap& flowMap() {
|
alpar@389
|
326 |
return *_flow;
|
alpar@389
|
327 |
}
|
alpar@389
|
328 |
|
alpar@389
|
329 |
/// \brief Sets the elevator.
|
alpar@389
|
330 |
///
|
alpar@389
|
331 |
/// Sets the elevator.
|
alpar@389
|
332 |
/// \return \c (*this)
|
alpar@389
|
333 |
Preflow& elevator(Elevator& elevator) {
|
alpar@389
|
334 |
if (_local_level) {
|
alpar@389
|
335 |
delete _level;
|
alpar@389
|
336 |
_local_level = false;
|
alpar@389
|
337 |
}
|
alpar@389
|
338 |
_level = &elevator;
|
alpar@389
|
339 |
return *this;
|
alpar@389
|
340 |
}
|
alpar@389
|
341 |
|
alpar@389
|
342 |
/// \brief Returns the elevator.
|
alpar@389
|
343 |
///
|
alpar@389
|
344 |
/// \return The elevator.
|
alpar@389
|
345 |
const Elevator& elevator() {
|
alpar@389
|
346 |
return *_level;
|
alpar@389
|
347 |
}
|
alpar@389
|
348 |
|
alpar@389
|
349 |
/// \brief Sets the source node.
|
alpar@389
|
350 |
///
|
alpar@389
|
351 |
/// Sets the source node.
|
alpar@389
|
352 |
/// \return \c (*this)
|
alpar@389
|
353 |
Preflow& source(const Node& node) {
|
alpar@389
|
354 |
_source = node;
|
alpar@389
|
355 |
return *this;
|
alpar@389
|
356 |
}
|
alpar@389
|
357 |
|
alpar@389
|
358 |
/// \brief Sets the target node.
|
alpar@389
|
359 |
///
|
alpar@389
|
360 |
/// Sets the target node.
|
alpar@389
|
361 |
/// \return \c (*this)
|
alpar@389
|
362 |
Preflow& target(const Node& node) {
|
alpar@389
|
363 |
_target = node;
|
alpar@389
|
364 |
return *this;
|
alpar@389
|
365 |
}
|
alpar@389
|
366 |
|
alpar@389
|
367 |
/// \brief Sets the tolerance used by algorithm.
|
alpar@389
|
368 |
///
|
alpar@389
|
369 |
/// Sets the tolerance used by algorithm.
|
alpar@389
|
370 |
Preflow& tolerance(const Tolerance& tolerance) const {
|
alpar@389
|
371 |
_tolerance = tolerance;
|
alpar@389
|
372 |
return *this;
|
alpar@389
|
373 |
}
|
alpar@389
|
374 |
|
alpar@389
|
375 |
/// \brief Returns the tolerance used by algorithm.
|
alpar@389
|
376 |
///
|
alpar@389
|
377 |
/// Returns the tolerance used by algorithm.
|
alpar@389
|
378 |
const Tolerance& tolerance() const {
|
alpar@389
|
379 |
return tolerance;
|
alpar@389
|
380 |
}
|
alpar@389
|
381 |
|
alpar@389
|
382 |
/// \name Execution control The simplest way to execute the
|
alpar@389
|
383 |
/// algorithm is to use one of the member functions called \c
|
alpar@389
|
384 |
/// run().
|
alpar@389
|
385 |
/// \n
|
alpar@389
|
386 |
/// If you need more control on initial solution or
|
alpar@389
|
387 |
/// execution then you have to call one \ref init() function and then
|
alpar@389
|
388 |
/// the startFirstPhase() and if you need the startSecondPhase().
|
alpar@389
|
389 |
|
alpar@389
|
390 |
///@{
|
alpar@389
|
391 |
|
alpar@389
|
392 |
/// \brief Initializes the internal data structures.
|
alpar@389
|
393 |
///
|
alpar@389
|
394 |
/// Initializes the internal data structures.
|
alpar@389
|
395 |
///
|
alpar@389
|
396 |
void init() {
|
alpar@389
|
397 |
createStructures();
|
alpar@389
|
398 |
|
alpar@389
|
399 |
_phase = true;
|
alpar@389
|
400 |
for (NodeIt n(_graph); n != INVALID; ++n) {
|
alpar@389
|
401 |
_excess->set(n, 0);
|
alpar@389
|
402 |
}
|
alpar@389
|
403 |
|
alpar@389
|
404 |
for (ArcIt e(_graph); e != INVALID; ++e) {
|
alpar@389
|
405 |
_flow->set(e, 0);
|
alpar@389
|
406 |
}
|
alpar@389
|
407 |
|
alpar@389
|
408 |
typename Digraph::template NodeMap<bool> reached(_graph, false);
|
alpar@389
|
409 |
|
alpar@389
|
410 |
_level->initStart();
|
alpar@389
|
411 |
_level->initAddItem(_target);
|
alpar@389
|
412 |
|
alpar@389
|
413 |
std::vector<Node> queue;
|
alpar@389
|
414 |
reached.set(_source, true);
|
alpar@389
|
415 |
|
alpar@389
|
416 |
queue.push_back(_target);
|
alpar@389
|
417 |
reached.set(_target, true);
|
alpar@389
|
418 |
while (!queue.empty()) {
|
alpar@389
|
419 |
_level->initNewLevel();
|
alpar@389
|
420 |
std::vector<Node> nqueue;
|
alpar@389
|
421 |
for (int i = 0; i < int(queue.size()); ++i) {
|
alpar@389
|
422 |
Node n = queue[i];
|
alpar@389
|
423 |
for (InArcIt e(_graph, n); e != INVALID; ++e) {
|
alpar@389
|
424 |
Node u = _graph.source(e);
|
alpar@389
|
425 |
if (!reached[u] && _tolerance.positive((*_capacity)[e])) {
|
alpar@389
|
426 |
reached.set(u, true);
|
alpar@389
|
427 |
_level->initAddItem(u);
|
alpar@389
|
428 |
nqueue.push_back(u);
|
alpar@389
|
429 |
}
|
alpar@389
|
430 |
}
|
alpar@389
|
431 |
}
|
alpar@389
|
432 |
queue.swap(nqueue);
|
alpar@389
|
433 |
}
|
alpar@389
|
434 |
_level->initFinish();
|
alpar@389
|
435 |
|
alpar@389
|
436 |
for (OutArcIt e(_graph, _source); e != INVALID; ++e) {
|
alpar@389
|
437 |
if (_tolerance.positive((*_capacity)[e])) {
|
alpar@389
|
438 |
Node u = _graph.target(e);
|
alpar@389
|
439 |
if ((*_level)[u] == _level->maxLevel()) continue;
|
alpar@389
|
440 |
_flow->set(e, (*_capacity)[e]);
|
alpar@389
|
441 |
_excess->set(u, (*_excess)[u] + (*_capacity)[e]);
|
alpar@389
|
442 |
if (u != _target && !_level->active(u)) {
|
alpar@389
|
443 |
_level->activate(u);
|
alpar@389
|
444 |
}
|
alpar@389
|
445 |
}
|
alpar@389
|
446 |
}
|
alpar@389
|
447 |
}
|
alpar@389
|
448 |
|
alpar@389
|
449 |
/// \brief Initializes the internal data structures.
|
alpar@389
|
450 |
///
|
alpar@389
|
451 |
/// Initializes the internal data structures and sets the initial
|
alpar@389
|
452 |
/// flow to the given \c flowMap. The \c flowMap should contain a
|
alpar@389
|
453 |
/// flow or at least a preflow, ie. in each node excluding the
|
alpar@389
|
454 |
/// target the incoming flow should greater or equal to the
|
alpar@389
|
455 |
/// outgoing flow.
|
alpar@389
|
456 |
/// \return %False when the given \c flowMap is not a preflow.
|
alpar@389
|
457 |
template <typename FlowMap>
|
alpar@389
|
458 |
bool flowInit(const FlowMap& flowMap) {
|
alpar@389
|
459 |
createStructures();
|
alpar@389
|
460 |
|
alpar@389
|
461 |
for (ArcIt e(_graph); e != INVALID; ++e) {
|
alpar@389
|
462 |
_flow->set(e, flowMap[e]);
|
alpar@389
|
463 |
}
|
alpar@389
|
464 |
|
alpar@389
|
465 |
for (NodeIt n(_graph); n != INVALID; ++n) {
|
alpar@389
|
466 |
Value excess = 0;
|
alpar@389
|
467 |
for (InArcIt e(_graph, n); e != INVALID; ++e) {
|
alpar@389
|
468 |
excess += (*_flow)[e];
|
alpar@389
|
469 |
}
|
alpar@389
|
470 |
for (OutArcIt e(_graph, n); e != INVALID; ++e) {
|
alpar@389
|
471 |
excess -= (*_flow)[e];
|
alpar@389
|
472 |
}
|
alpar@389
|
473 |
if (excess < 0 && n != _source) return false;
|
alpar@389
|
474 |
_excess->set(n, excess);
|
alpar@389
|
475 |
}
|
alpar@389
|
476 |
|
alpar@389
|
477 |
typename Digraph::template NodeMap<bool> reached(_graph, false);
|
alpar@389
|
478 |
|
alpar@389
|
479 |
_level->initStart();
|
alpar@389
|
480 |
_level->initAddItem(_target);
|
alpar@389
|
481 |
|
alpar@389
|
482 |
std::vector<Node> queue;
|
alpar@389
|
483 |
reached.set(_source, true);
|
alpar@389
|
484 |
|
alpar@389
|
485 |
queue.push_back(_target);
|
alpar@389
|
486 |
reached.set(_target, true);
|
alpar@389
|
487 |
while (!queue.empty()) {
|
alpar@389
|
488 |
_level->initNewLevel();
|
alpar@389
|
489 |
std::vector<Node> nqueue;
|
alpar@389
|
490 |
for (int i = 0; i < int(queue.size()); ++i) {
|
alpar@389
|
491 |
Node n = queue[i];
|
alpar@389
|
492 |
for (InArcIt e(_graph, n); e != INVALID; ++e) {
|
alpar@389
|
493 |
Node u = _graph.source(e);
|
alpar@389
|
494 |
if (!reached[u] &&
|
alpar@389
|
495 |
_tolerance.positive((*_capacity)[e] - (*_flow)[e])) {
|
alpar@389
|
496 |
reached.set(u, true);
|
alpar@389
|
497 |
_level->initAddItem(u);
|
alpar@389
|
498 |
nqueue.push_back(u);
|
alpar@389
|
499 |
}
|
alpar@389
|
500 |
}
|
alpar@389
|
501 |
for (OutArcIt e(_graph, n); e != INVALID; ++e) {
|
alpar@389
|
502 |
Node v = _graph.target(e);
|
alpar@389
|
503 |
if (!reached[v] && _tolerance.positive((*_flow)[e])) {
|
alpar@389
|
504 |
reached.set(v, true);
|
alpar@389
|
505 |
_level->initAddItem(v);
|
alpar@389
|
506 |
nqueue.push_back(v);
|
alpar@389
|
507 |
}
|
alpar@389
|
508 |
}
|
alpar@389
|
509 |
}
|
alpar@389
|
510 |
queue.swap(nqueue);
|
alpar@389
|
511 |
}
|
alpar@389
|
512 |
_level->initFinish();
|
alpar@389
|
513 |
|
alpar@389
|
514 |
for (OutArcIt e(_graph, _source); e != INVALID; ++e) {
|
alpar@389
|
515 |
Value rem = (*_capacity)[e] - (*_flow)[e];
|
alpar@389
|
516 |
if (_tolerance.positive(rem)) {
|
alpar@389
|
517 |
Node u = _graph.target(e);
|
alpar@389
|
518 |
if ((*_level)[u] == _level->maxLevel()) continue;
|
alpar@389
|
519 |
_flow->set(e, (*_capacity)[e]);
|
alpar@389
|
520 |
_excess->set(u, (*_excess)[u] + rem);
|
alpar@389
|
521 |
if (u != _target && !_level->active(u)) {
|
alpar@389
|
522 |
_level->activate(u);
|
alpar@389
|
523 |
}
|
alpar@389
|
524 |
}
|
alpar@389
|
525 |
}
|
alpar@389
|
526 |
for (InArcIt e(_graph, _source); e != INVALID; ++e) {
|
alpar@389
|
527 |
Value rem = (*_flow)[e];
|
alpar@389
|
528 |
if (_tolerance.positive(rem)) {
|
alpar@389
|
529 |
Node v = _graph.source(e);
|
alpar@389
|
530 |
if ((*_level)[v] == _level->maxLevel()) continue;
|
alpar@389
|
531 |
_flow->set(e, 0);
|
alpar@389
|
532 |
_excess->set(v, (*_excess)[v] + rem);
|
alpar@389
|
533 |
if (v != _target && !_level->active(v)) {
|
alpar@389
|
534 |
_level->activate(v);
|
alpar@389
|
535 |
}
|
alpar@389
|
536 |
}
|
alpar@389
|
537 |
}
|
alpar@389
|
538 |
return true;
|
alpar@389
|
539 |
}
|
alpar@389
|
540 |
|
alpar@389
|
541 |
/// \brief Starts the first phase of the preflow algorithm.
|
alpar@389
|
542 |
///
|
alpar@389
|
543 |
/// The preflow algorithm consists of two phases, this method runs
|
alpar@389
|
544 |
/// the first phase. After the first phase the maximum flow value
|
alpar@389
|
545 |
/// and a minimum value cut can already be computed, although a
|
alpar@389
|
546 |
/// maximum flow is not yet obtained. So after calling this method
|
alpar@389
|
547 |
/// \ref flowValue() returns the value of a maximum flow and \ref
|
alpar@389
|
548 |
/// minCut() returns a minimum cut.
|
alpar@389
|
549 |
/// \pre One of the \ref init() functions should be called.
|
alpar@389
|
550 |
void startFirstPhase() {
|
alpar@389
|
551 |
_phase = true;
|
alpar@389
|
552 |
|
alpar@389
|
553 |
Node n = _level->highestActive();
|
alpar@389
|
554 |
int level = _level->highestActiveLevel();
|
alpar@389
|
555 |
while (n != INVALID) {
|
alpar@389
|
556 |
int num = _node_num;
|
alpar@389
|
557 |
|
alpar@389
|
558 |
while (num > 0 && n != INVALID) {
|
alpar@389
|
559 |
Value excess = (*_excess)[n];
|
alpar@389
|
560 |
int new_level = _level->maxLevel();
|
alpar@389
|
561 |
|
alpar@389
|
562 |
for (OutArcIt e(_graph, n); e != INVALID; ++e) {
|
alpar@389
|
563 |
Value rem = (*_capacity)[e] - (*_flow)[e];
|
alpar@389
|
564 |
if (!_tolerance.positive(rem)) continue;
|
alpar@389
|
565 |
Node v = _graph.target(e);
|
alpar@389
|
566 |
if ((*_level)[v] < level) {
|
alpar@389
|
567 |
if (!_level->active(v) && v != _target) {
|
alpar@389
|
568 |
_level->activate(v);
|
alpar@389
|
569 |
}
|
alpar@389
|
570 |
if (!_tolerance.less(rem, excess)) {
|
alpar@389
|
571 |
_flow->set(e, (*_flow)[e] + excess);
|
alpar@389
|
572 |
_excess->set(v, (*_excess)[v] + excess);
|
alpar@389
|
573 |
excess = 0;
|
alpar@389
|
574 |
goto no_more_push_1;
|
alpar@389
|
575 |
} else {
|
alpar@389
|
576 |
excess -= rem;
|
alpar@389
|
577 |
_excess->set(v, (*_excess)[v] + rem);
|
alpar@389
|
578 |
_flow->set(e, (*_capacity)[e]);
|
alpar@389
|
579 |
}
|
alpar@389
|
580 |
} else if (new_level > (*_level)[v]) {
|
alpar@389
|
581 |
new_level = (*_level)[v];
|
alpar@389
|
582 |
}
|
alpar@389
|
583 |
}
|
alpar@389
|
584 |
|
alpar@389
|
585 |
for (InArcIt e(_graph, n); e != INVALID; ++e) {
|
alpar@389
|
586 |
Value rem = (*_flow)[e];
|
alpar@389
|
587 |
if (!_tolerance.positive(rem)) continue;
|
alpar@389
|
588 |
Node v = _graph.source(e);
|
alpar@389
|
589 |
if ((*_level)[v] < level) {
|
alpar@389
|
590 |
if (!_level->active(v) && v != _target) {
|
alpar@389
|
591 |
_level->activate(v);
|
alpar@389
|
592 |
}
|
alpar@389
|
593 |
if (!_tolerance.less(rem, excess)) {
|
alpar@389
|
594 |
_flow->set(e, (*_flow)[e] - excess);
|
alpar@389
|
595 |
_excess->set(v, (*_excess)[v] + excess);
|
alpar@389
|
596 |
excess = 0;
|
alpar@389
|
597 |
goto no_more_push_1;
|
alpar@389
|
598 |
} else {
|
alpar@389
|
599 |
excess -= rem;
|
alpar@389
|
600 |
_excess->set(v, (*_excess)[v] + rem);
|
alpar@389
|
601 |
_flow->set(e, 0);
|
alpar@389
|
602 |
}
|
alpar@389
|
603 |
} else if (new_level > (*_level)[v]) {
|
alpar@389
|
604 |
new_level = (*_level)[v];
|
alpar@389
|
605 |
}
|
alpar@389
|
606 |
}
|
alpar@389
|
607 |
|
alpar@389
|
608 |
no_more_push_1:
|
alpar@389
|
609 |
|
alpar@389
|
610 |
_excess->set(n, excess);
|
alpar@389
|
611 |
|
alpar@389
|
612 |
if (excess != 0) {
|
alpar@389
|
613 |
if (new_level + 1 < _level->maxLevel()) {
|
alpar@389
|
614 |
_level->liftHighestActive(new_level + 1);
|
alpar@389
|
615 |
} else {
|
alpar@389
|
616 |
_level->liftHighestActiveToTop();
|
alpar@389
|
617 |
}
|
alpar@389
|
618 |
if (_level->emptyLevel(level)) {
|
alpar@389
|
619 |
_level->liftToTop(level);
|
alpar@389
|
620 |
}
|
alpar@389
|
621 |
} else {
|
alpar@389
|
622 |
_level->deactivate(n);
|
alpar@389
|
623 |
}
|
alpar@389
|
624 |
|
alpar@389
|
625 |
n = _level->highestActive();
|
alpar@389
|
626 |
level = _level->highestActiveLevel();
|
alpar@389
|
627 |
--num;
|
alpar@389
|
628 |
}
|
alpar@389
|
629 |
|
alpar@389
|
630 |
num = _node_num * 20;
|
alpar@389
|
631 |
while (num > 0 && n != INVALID) {
|
alpar@389
|
632 |
Value excess = (*_excess)[n];
|
alpar@389
|
633 |
int new_level = _level->maxLevel();
|
alpar@389
|
634 |
|
alpar@389
|
635 |
for (OutArcIt e(_graph, n); e != INVALID; ++e) {
|
alpar@389
|
636 |
Value rem = (*_capacity)[e] - (*_flow)[e];
|
alpar@389
|
637 |
if (!_tolerance.positive(rem)) continue;
|
alpar@389
|
638 |
Node v = _graph.target(e);
|
alpar@389
|
639 |
if ((*_level)[v] < level) {
|
alpar@389
|
640 |
if (!_level->active(v) && v != _target) {
|
alpar@389
|
641 |
_level->activate(v);
|
alpar@389
|
642 |
}
|
alpar@389
|
643 |
if (!_tolerance.less(rem, excess)) {
|
alpar@389
|
644 |
_flow->set(e, (*_flow)[e] + excess);
|
alpar@389
|
645 |
_excess->set(v, (*_excess)[v] + excess);
|
alpar@389
|
646 |
excess = 0;
|
alpar@389
|
647 |
goto no_more_push_2;
|
alpar@389
|
648 |
} else {
|
alpar@389
|
649 |
excess -= rem;
|
alpar@389
|
650 |
_excess->set(v, (*_excess)[v] + rem);
|
alpar@389
|
651 |
_flow->set(e, (*_capacity)[e]);
|
alpar@389
|
652 |
}
|
alpar@389
|
653 |
} else if (new_level > (*_level)[v]) {
|
alpar@389
|
654 |
new_level = (*_level)[v];
|
alpar@389
|
655 |
}
|
alpar@389
|
656 |
}
|
alpar@389
|
657 |
|
alpar@389
|
658 |
for (InArcIt e(_graph, n); e != INVALID; ++e) {
|
alpar@389
|
659 |
Value rem = (*_flow)[e];
|
alpar@389
|
660 |
if (!_tolerance.positive(rem)) continue;
|
alpar@389
|
661 |
Node v = _graph.source(e);
|
alpar@389
|
662 |
if ((*_level)[v] < level) {
|
alpar@389
|
663 |
if (!_level->active(v) && v != _target) {
|
alpar@389
|
664 |
_level->activate(v);
|
alpar@389
|
665 |
}
|
alpar@389
|
666 |
if (!_tolerance.less(rem, excess)) {
|
alpar@389
|
667 |
_flow->set(e, (*_flow)[e] - excess);
|
alpar@389
|
668 |
_excess->set(v, (*_excess)[v] + excess);
|
alpar@389
|
669 |
excess = 0;
|
alpar@389
|
670 |
goto no_more_push_2;
|
alpar@389
|
671 |
} else {
|
alpar@389
|
672 |
excess -= rem;
|
alpar@389
|
673 |
_excess->set(v, (*_excess)[v] + rem);
|
alpar@389
|
674 |
_flow->set(e, 0);
|
alpar@389
|
675 |
}
|
alpar@389
|
676 |
} else if (new_level > (*_level)[v]) {
|
alpar@389
|
677 |
new_level = (*_level)[v];
|
alpar@389
|
678 |
}
|
alpar@389
|
679 |
}
|
alpar@389
|
680 |
|
alpar@389
|
681 |
no_more_push_2:
|
alpar@389
|
682 |
|
alpar@389
|
683 |
_excess->set(n, excess);
|
alpar@389
|
684 |
|
alpar@389
|
685 |
if (excess != 0) {
|
alpar@389
|
686 |
if (new_level + 1 < _level->maxLevel()) {
|
alpar@389
|
687 |
_level->liftActiveOn(level, new_level + 1);
|
alpar@389
|
688 |
} else {
|
alpar@389
|
689 |
_level->liftActiveToTop(level);
|
alpar@389
|
690 |
}
|
alpar@389
|
691 |
if (_level->emptyLevel(level)) {
|
alpar@389
|
692 |
_level->liftToTop(level);
|
alpar@389
|
693 |
}
|
alpar@389
|
694 |
} else {
|
alpar@389
|
695 |
_level->deactivate(n);
|
alpar@389
|
696 |
}
|
alpar@389
|
697 |
|
alpar@389
|
698 |
while (level >= 0 && _level->activeFree(level)) {
|
alpar@389
|
699 |
--level;
|
alpar@389
|
700 |
}
|
alpar@389
|
701 |
if (level == -1) {
|
alpar@389
|
702 |
n = _level->highestActive();
|
alpar@389
|
703 |
level = _level->highestActiveLevel();
|
alpar@389
|
704 |
} else {
|
alpar@389
|
705 |
n = _level->activeOn(level);
|
alpar@389
|
706 |
}
|
alpar@389
|
707 |
--num;
|
alpar@389
|
708 |
}
|
alpar@389
|
709 |
}
|
alpar@389
|
710 |
}
|
alpar@389
|
711 |
|
alpar@389
|
712 |
/// \brief Starts the second phase of the preflow algorithm.
|
alpar@389
|
713 |
///
|
alpar@389
|
714 |
/// The preflow algorithm consists of two phases, this method runs
|
alpar@389
|
715 |
/// the second phase. After calling \ref init() and \ref
|
alpar@389
|
716 |
/// startFirstPhase() and then \ref startSecondPhase(), \ref
|
alpar@389
|
717 |
/// flowMap() return a maximum flow, \ref flowValue() returns the
|
alpar@389
|
718 |
/// value of a maximum flow, \ref minCut() returns a minimum cut
|
alpar@389
|
719 |
/// \pre The \ref init() and startFirstPhase() functions should be
|
alpar@389
|
720 |
/// called before.
|
alpar@389
|
721 |
void startSecondPhase() {
|
alpar@389
|
722 |
_phase = false;
|
alpar@389
|
723 |
|
alpar@389
|
724 |
typename Digraph::template NodeMap<bool> reached(_graph);
|
alpar@389
|
725 |
for (NodeIt n(_graph); n != INVALID; ++n) {
|
alpar@389
|
726 |
reached.set(n, (*_level)[n] < _level->maxLevel());
|
alpar@389
|
727 |
}
|
alpar@389
|
728 |
|
alpar@389
|
729 |
_level->initStart();
|
alpar@389
|
730 |
_level->initAddItem(_source);
|
alpar@389
|
731 |
|
alpar@389
|
732 |
std::vector<Node> queue;
|
alpar@389
|
733 |
queue.push_back(_source);
|
alpar@389
|
734 |
reached.set(_source, true);
|
alpar@389
|
735 |
|
alpar@389
|
736 |
while (!queue.empty()) {
|
alpar@389
|
737 |
_level->initNewLevel();
|
alpar@389
|
738 |
std::vector<Node> nqueue;
|
alpar@389
|
739 |
for (int i = 0; i < int(queue.size()); ++i) {
|
alpar@389
|
740 |
Node n = queue[i];
|
alpar@389
|
741 |
for (OutArcIt e(_graph, n); e != INVALID; ++e) {
|
alpar@389
|
742 |
Node v = _graph.target(e);
|
alpar@389
|
743 |
if (!reached[v] && _tolerance.positive((*_flow)[e])) {
|
alpar@389
|
744 |
reached.set(v, true);
|
alpar@389
|
745 |
_level->initAddItem(v);
|
alpar@389
|
746 |
nqueue.push_back(v);
|
alpar@389
|
747 |
}
|
alpar@389
|
748 |
}
|
alpar@389
|
749 |
for (InArcIt e(_graph, n); e != INVALID; ++e) {
|
alpar@389
|
750 |
Node u = _graph.source(e);
|
alpar@389
|
751 |
if (!reached[u] &&
|
alpar@389
|
752 |
_tolerance.positive((*_capacity)[e] - (*_flow)[e])) {
|
alpar@389
|
753 |
reached.set(u, true);
|
alpar@389
|
754 |
_level->initAddItem(u);
|
alpar@389
|
755 |
nqueue.push_back(u);
|
alpar@389
|
756 |
}
|
alpar@389
|
757 |
}
|
alpar@389
|
758 |
}
|
alpar@389
|
759 |
queue.swap(nqueue);
|
alpar@389
|
760 |
}
|
alpar@389
|
761 |
_level->initFinish();
|
alpar@389
|
762 |
|
alpar@389
|
763 |
for (NodeIt n(_graph); n != INVALID; ++n) {
|
alpar@389
|
764 |
if (!reached[n]) {
|
alpar@389
|
765 |
_level->dirtyTopButOne(n);
|
alpar@389
|
766 |
} else if ((*_excess)[n] > 0 && _target != n) {
|
alpar@389
|
767 |
_level->activate(n);
|
alpar@389
|
768 |
}
|
alpar@389
|
769 |
}
|
alpar@389
|
770 |
|
alpar@389
|
771 |
Node n;
|
alpar@389
|
772 |
while ((n = _level->highestActive()) != INVALID) {
|
alpar@389
|
773 |
Value excess = (*_excess)[n];
|
alpar@389
|
774 |
int level = _level->highestActiveLevel();
|
alpar@389
|
775 |
int new_level = _level->maxLevel();
|
alpar@389
|
776 |
|
alpar@389
|
777 |
for (OutArcIt e(_graph, n); e != INVALID; ++e) {
|
alpar@389
|
778 |
Value rem = (*_capacity)[e] - (*_flow)[e];
|
alpar@389
|
779 |
if (!_tolerance.positive(rem)) continue;
|
alpar@389
|
780 |
Node v = _graph.target(e);
|
alpar@389
|
781 |
if ((*_level)[v] < level) {
|
alpar@389
|
782 |
if (!_level->active(v) && v != _source) {
|
alpar@389
|
783 |
_level->activate(v);
|
alpar@389
|
784 |
}
|
alpar@389
|
785 |
if (!_tolerance.less(rem, excess)) {
|
alpar@389
|
786 |
_flow->set(e, (*_flow)[e] + excess);
|
alpar@389
|
787 |
_excess->set(v, (*_excess)[v] + excess);
|
alpar@389
|
788 |
excess = 0;
|
alpar@389
|
789 |
goto no_more_push;
|
alpar@389
|
790 |
} else {
|
alpar@389
|
791 |
excess -= rem;
|
alpar@389
|
792 |
_excess->set(v, (*_excess)[v] + rem);
|
alpar@389
|
793 |
_flow->set(e, (*_capacity)[e]);
|
alpar@389
|
794 |
}
|
alpar@389
|
795 |
} else if (new_level > (*_level)[v]) {
|
alpar@389
|
796 |
new_level = (*_level)[v];
|
alpar@389
|
797 |
}
|
alpar@389
|
798 |
}
|
alpar@389
|
799 |
|
alpar@389
|
800 |
for (InArcIt e(_graph, n); e != INVALID; ++e) {
|
alpar@389
|
801 |
Value rem = (*_flow)[e];
|
alpar@389
|
802 |
if (!_tolerance.positive(rem)) continue;
|
alpar@389
|
803 |
Node v = _graph.source(e);
|
alpar@389
|
804 |
if ((*_level)[v] < level) {
|
alpar@389
|
805 |
if (!_level->active(v) && v != _source) {
|
alpar@389
|
806 |
_level->activate(v);
|
alpar@389
|
807 |
}
|
alpar@389
|
808 |
if (!_tolerance.less(rem, excess)) {
|
alpar@389
|
809 |
_flow->set(e, (*_flow)[e] - excess);
|
alpar@389
|
810 |
_excess->set(v, (*_excess)[v] + excess);
|
alpar@389
|
811 |
excess = 0;
|
alpar@389
|
812 |
goto no_more_push;
|
alpar@389
|
813 |
} else {
|
alpar@389
|
814 |
excess -= rem;
|
alpar@389
|
815 |
_excess->set(v, (*_excess)[v] + rem);
|
alpar@389
|
816 |
_flow->set(e, 0);
|
alpar@389
|
817 |
}
|
alpar@389
|
818 |
} else if (new_level > (*_level)[v]) {
|
alpar@389
|
819 |
new_level = (*_level)[v];
|
alpar@389
|
820 |
}
|
alpar@389
|
821 |
}
|
alpar@389
|
822 |
|
alpar@389
|
823 |
no_more_push:
|
alpar@389
|
824 |
|
alpar@389
|
825 |
_excess->set(n, excess);
|
alpar@389
|
826 |
|
alpar@389
|
827 |
if (excess != 0) {
|
alpar@389
|
828 |
if (new_level + 1 < _level->maxLevel()) {
|
alpar@389
|
829 |
_level->liftHighestActive(new_level + 1);
|
alpar@389
|
830 |
} else {
|
alpar@389
|
831 |
// Calculation error
|
alpar@389
|
832 |
_level->liftHighestActiveToTop();
|
alpar@389
|
833 |
}
|
alpar@389
|
834 |
if (_level->emptyLevel(level)) {
|
alpar@389
|
835 |
// Calculation error
|
alpar@389
|
836 |
_level->liftToTop(level);
|
alpar@389
|
837 |
}
|
alpar@389
|
838 |
} else {
|
alpar@389
|
839 |
_level->deactivate(n);
|
alpar@389
|
840 |
}
|
alpar@389
|
841 |
|
alpar@389
|
842 |
}
|
alpar@389
|
843 |
}
|
alpar@389
|
844 |
|
alpar@389
|
845 |
/// \brief Runs the preflow algorithm.
|
alpar@389
|
846 |
///
|
alpar@389
|
847 |
/// Runs the preflow algorithm.
|
alpar@389
|
848 |
/// \note pf.run() is just a shortcut of the following code.
|
alpar@389
|
849 |
/// \code
|
alpar@389
|
850 |
/// pf.init();
|
alpar@389
|
851 |
/// pf.startFirstPhase();
|
alpar@389
|
852 |
/// pf.startSecondPhase();
|
alpar@389
|
853 |
/// \endcode
|
alpar@389
|
854 |
void run() {
|
alpar@389
|
855 |
init();
|
alpar@389
|
856 |
startFirstPhase();
|
alpar@389
|
857 |
startSecondPhase();
|
alpar@389
|
858 |
}
|
alpar@389
|
859 |
|
alpar@389
|
860 |
/// \brief Runs the preflow algorithm to compute the minimum cut.
|
alpar@389
|
861 |
///
|
alpar@389
|
862 |
/// Runs the preflow algorithm to compute the minimum cut.
|
alpar@389
|
863 |
/// \note pf.runMinCut() is just a shortcut of the following code.
|
alpar@389
|
864 |
/// \code
|
alpar@389
|
865 |
/// pf.init();
|
alpar@389
|
866 |
/// pf.startFirstPhase();
|
alpar@389
|
867 |
/// \endcode
|
alpar@389
|
868 |
void runMinCut() {
|
alpar@389
|
869 |
init();
|
alpar@389
|
870 |
startFirstPhase();
|
alpar@389
|
871 |
}
|
alpar@389
|
872 |
|
alpar@389
|
873 |
/// @}
|
alpar@389
|
874 |
|
alpar@389
|
875 |
/// \name Query Functions
|
alpar@389
|
876 |
/// The result of the %Preflow algorithm can be obtained using these
|
alpar@389
|
877 |
/// functions.\n
|
alpar@389
|
878 |
/// Before the use of these functions,
|
alpar@389
|
879 |
/// either run() or start() must be called.
|
alpar@389
|
880 |
|
alpar@389
|
881 |
///@{
|
alpar@389
|
882 |
|
alpar@389
|
883 |
/// \brief Returns the value of the maximum flow.
|
alpar@389
|
884 |
///
|
alpar@389
|
885 |
/// Returns the value of the maximum flow by returning the excess
|
alpar@389
|
886 |
/// of the target node \c t. This value equals to the value of
|
alpar@389
|
887 |
/// the maximum flow already after the first phase.
|
alpar@389
|
888 |
Value flowValue() const {
|
alpar@389
|
889 |
return (*_excess)[_target];
|
alpar@389
|
890 |
}
|
alpar@389
|
891 |
|
alpar@389
|
892 |
/// \brief Returns true when the node is on the source side of minimum cut.
|
alpar@389
|
893 |
///
|
alpar@389
|
894 |
/// Returns true when the node is on the source side of minimum
|
alpar@389
|
895 |
/// cut. This method can be called both after running \ref
|
alpar@389
|
896 |
/// startFirstPhase() and \ref startSecondPhase().
|
alpar@389
|
897 |
bool minCut(const Node& node) const {
|
alpar@389
|
898 |
return ((*_level)[node] == _level->maxLevel()) == _phase;
|
alpar@389
|
899 |
}
|
alpar@389
|
900 |
|
alpar@389
|
901 |
/// \brief Returns a minimum value cut.
|
alpar@389
|
902 |
///
|
alpar@389
|
903 |
/// Sets the \c cutMap to the characteristic vector of a minimum value
|
alpar@389
|
904 |
/// cut. This method can be called both after running \ref
|
alpar@389
|
905 |
/// startFirstPhase() and \ref startSecondPhase(). The result after second
|
alpar@389
|
906 |
/// phase could be changed slightly if inexact computation is used.
|
alpar@389
|
907 |
/// \pre The \c cutMap should be a bool-valued node-map.
|
alpar@389
|
908 |
template <typename CutMap>
|
alpar@389
|
909 |
void minCutMap(CutMap& cutMap) const {
|
alpar@389
|
910 |
for (NodeIt n(_graph); n != INVALID; ++n) {
|
alpar@389
|
911 |
cutMap.set(n, minCut(n));
|
alpar@389
|
912 |
}
|
alpar@389
|
913 |
}
|
alpar@389
|
914 |
|
alpar@389
|
915 |
/// \brief Returns the flow on the arc.
|
alpar@389
|
916 |
///
|
alpar@389
|
917 |
/// Sets the \c flowMap to the flow on the arcs. This method can
|
alpar@389
|
918 |
/// be called after the second phase of algorithm.
|
alpar@389
|
919 |
Value flow(const Arc& arc) const {
|
alpar@389
|
920 |
return (*_flow)[arc];
|
alpar@389
|
921 |
}
|
alpar@389
|
922 |
|
alpar@389
|
923 |
/// @}
|
alpar@389
|
924 |
};
|
alpar@389
|
925 |
}
|
alpar@389
|
926 |
|
alpar@389
|
927 |
#endif
|