gravatar
kpeter (Peter Kovacs)
kpeter@inf.elte.hu
Many doc improvements for Preflow (#176) - More precise doc for members. - Add doc for public types. - Hide the doc of the traits class parameter. - Removing \author comments. - Use \tparam for template parameters.
0 1 0
default
1 file changed with 156 insertions and 109 deletions:
↑ Collapse diff ↑
Ignore white space 48 line context
... ...
@@ -10,146 +10,148 @@
10 10
 * provided that this copyright notice appears in all copies. For
11 11
 * precise terms see the accompanying LICENSE file.
12 12
 *
13 13
 * This software is provided "AS IS" with no warranty of any kind,
14 14
 * express or implied, and with no claim as to its suitability for any
15 15
 * purpose.
16 16
 *
17 17
 */
18 18

	
19 19
#ifndef LEMON_PREFLOW_H
20 20
#define LEMON_PREFLOW_H
21 21

	
22 22
#include <lemon/tolerance.h>
23 23
#include <lemon/elevator.h>
24 24

	
25 25
/// \file
26 26
/// \ingroup max_flow
27 27
/// \brief Implementation of the preflow algorithm.
28 28

	
29 29
namespace lemon {
30 30

	
31 31
  /// \brief Default traits class of Preflow class.
32 32
  ///
33 33
  /// Default traits class of Preflow class.
34
  /// \param _Graph Digraph type.
35
  /// \param _CapacityMap Type of capacity map.
36
  template <typename _Graph, typename _CapacityMap>
34
  /// \tparam _Digraph Digraph type.
35
  /// \tparam _CapacityMap Capacity map type.
36
  template <typename _Digraph, typename _CapacityMap>
37 37
  struct PreflowDefaultTraits {
38 38

	
39
    /// \brief The digraph type the algorithm runs on.
40
    typedef _Graph Digraph;
39
    /// \brief The type of the digraph the algorithm runs on.
40
    typedef _Digraph Digraph;
41 41

	
42 42
    /// \brief The type of the map that stores the arc capacities.
43 43
    ///
44 44
    /// The type of the map that stores the arc capacities.
45 45
    /// It must meet the \ref concepts::ReadMap "ReadMap" concept.
46 46
    typedef _CapacityMap CapacityMap;
47 47

	
48
    /// \brief The type of the length of the arcs.
48
    /// \brief The type of the flow values.
49 49
    typedef typename CapacityMap::Value Value;
50 50

	
51
    /// \brief The map type that stores the flow values.
51
    /// \brief The type of the map that stores the flow values.
52 52
    ///
53
    /// The map type that stores the flow values.
53
    /// The type of the map that stores the flow values.
54 54
    /// It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
55 55
    typedef typename Digraph::template ArcMap<Value> FlowMap;
56 56

	
57 57
    /// \brief Instantiates a FlowMap.
58 58
    ///
59 59
    /// This function instantiates a \ref FlowMap.
60 60
    /// \param digraph The digraph, to which we would like to define
61 61
    /// the flow map.
62 62
    static FlowMap* createFlowMap(const Digraph& digraph) {
63 63
      return new FlowMap(digraph);
64 64
    }
65 65

	
66
    /// \brief The eleavator type used by Preflow algorithm.
66
    /// \brief The elevator type used by Preflow algorithm.
67 67
    ///
68 68
    /// The elevator type used by Preflow algorithm.
69 69
    ///
70 70
    /// \sa Elevator
71 71
    /// \sa LinkedElevator
72 72
    typedef LinkedElevator<Digraph, typename Digraph::Node> Elevator;
73 73

	
74 74
    /// \brief Instantiates an Elevator.
75 75
    ///
76
    /// This function instantiates a \ref Elevator.
76
    /// This function instantiates an \ref Elevator.
77 77
    /// \param digraph The digraph, to which we would like to define
78 78
    /// the elevator.
79 79
    /// \param max_level The maximum level of the elevator.
80 80
    static Elevator* createElevator(const Digraph& digraph, int max_level) {
81 81
      return new Elevator(digraph, max_level);
82 82
    }
83 83

	
84 84
    /// \brief The tolerance used by the algorithm
85 85
    ///
86 86
    /// The tolerance used by the algorithm to handle inexact computation.
87 87
    typedef lemon::Tolerance<Value> Tolerance;
88 88

	
89 89
  };
90 90

	
91 91

	
92 92
  /// \ingroup max_flow
93 93
  ///
94
  /// \brief %Preflow algorithms class.
94
  /// \brief %Preflow algorithm class.
95 95
  ///
96
  /// This class provides an implementation of the Goldberg's \e
97
  /// preflow \e algorithm producing a flow of maximum value in a
98
  /// digraph. The preflow algorithms are the fastest known max
96
  /// This class provides an implementation of Goldberg-Tarjan's \e preflow
97
  /// \e push-relabel algorithm producing a flow of maximum value in a
98
  /// digraph. The preflow algorithms are the fastest known maximum
99 99
  /// flow algorithms. The current implementation use a mixture of the
100 100
  /// \e "highest label" and the \e "bound decrease" heuristics.
101 101
  /// The worst case time complexity of the algorithm is \f$O(n^2\sqrt{e})\f$.
102 102
  ///
103
  /// The algorithm consists from two phases. After the first phase
104
  /// the maximal flow value and the minimum cut can be obtained. The
105
  /// second phase constructs the feasible maximum flow on each arc.
103
  /// The algorithm consists of two phases. After the first phase
104
  /// the maximum flow value and the minimum cut is obtained. The
105
  /// second phase constructs a feasible maximum flow on each arc.
106 106
  ///
107
  /// \param _Graph The digraph type the algorithm runs on.
108
  /// \param _CapacityMap The flow map type.
109
  /// \param _Traits Traits class to set various data types used by
110
  /// the algorithm.  The default traits class is \ref
111
  /// PreflowDefaultTraits.  See \ref PreflowDefaultTraits for the
112
  /// documentation of a %Preflow traits class.
113
  ///
114
  ///\author Jacint Szabo and Balazs Dezso
107
  /// \tparam _Digraph The type of the digraph the algorithm runs on.
108
  /// \tparam _CapacityMap The type of the capacity map. The default map
109
  /// type is \ref concepts::Digraph::ArcMap "_Digraph::ArcMap<int>".
115 110
#ifdef DOXYGEN
116
  template <typename _Graph, typename _CapacityMap, typename _Traits>
111
  template <typename _Digraph, typename _CapacityMap, typename _Traits>
117 112
#else
118
  template <typename _Graph,
119
            typename _CapacityMap = typename _Graph::template ArcMap<int>,
120
            typename _Traits = PreflowDefaultTraits<_Graph, _CapacityMap> >
113
  template <typename _Digraph,
114
            typename _CapacityMap = typename _Digraph::template ArcMap<int>,
115
            typename _Traits = PreflowDefaultTraits<_Digraph, _CapacityMap> >
121 116
#endif
122 117
  class Preflow {
123 118
  public:
124 119

	
120
    ///The \ref PreflowDefaultTraits "traits class" of the algorithm.
125 121
    typedef _Traits Traits;
122
    ///The type of the digraph the algorithm runs on.
126 123
    typedef typename Traits::Digraph Digraph;
124
    ///The type of the capacity map.
127 125
    typedef typename Traits::CapacityMap CapacityMap;
126
    ///The type of the flow values.
128 127
    typedef typename Traits::Value Value;
129 128

	
129
    ///The type of the flow map.
130 130
    typedef typename Traits::FlowMap FlowMap;
131
    ///The type of the elevator.
131 132
    typedef typename Traits::Elevator Elevator;
133
    ///The type of the tolerance.
132 134
    typedef typename Traits::Tolerance Tolerance;
133 135

	
134 136
  private:
135 137

	
136 138
    TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);
137 139

	
138 140
    const Digraph& _graph;
139 141
    const CapacityMap* _capacity;
140 142

	
141 143
    int _node_num;
142 144

	
143 145
    Node _source, _target;
144 146

	
145 147
    FlowMap* _flow;
146 148
    bool _local_flow;
147 149

	
148 150
    Elevator* _level;
149 151
    bool _local_level;
150 152

	
151 153
    typedef typename Digraph::template NodeMap<Value> ExcessMap;
152 154
    ExcessMap* _excess;
153 155

	
154 156
    Tolerance _tolerance;
155 157

	
... ...
@@ -167,243 +169,256 @@
167 169
        _level = Traits::createElevator(_graph, _node_num);
168 170
        _local_level = true;
169 171
      }
170 172
      if (!_excess) {
171 173
        _excess = new ExcessMap(_graph);
172 174
      }
173 175
    }
174 176

	
175 177
    void destroyStructures() {
176 178
      if (_local_flow) {
177 179
        delete _flow;
178 180
      }
179 181
      if (_local_level) {
180 182
        delete _level;
181 183
      }
182 184
      if (_excess) {
183 185
        delete _excess;
184 186
      }
185 187
    }
186 188

	
187 189
  public:
188 190

	
189 191
    typedef Preflow Create;
190 192

	
191
    ///\name Named template parameters
193
    ///\name Named Template Parameters
192 194

	
193 195
    ///@{
194 196

	
195 197
    template <typename _FlowMap>
196 198
    struct SetFlowMapTraits : public Traits {
197 199
      typedef _FlowMap FlowMap;
198 200
      static FlowMap *createFlowMap(const Digraph&) {
199 201
        LEMON_ASSERT(false, "FlowMap is not initialized");
200 202
        return 0; // ignore warnings
201 203
      }
202 204
    };
203 205

	
204 206
    /// \brief \ref named-templ-param "Named parameter" for setting
205 207
    /// FlowMap type
206 208
    ///
207 209
    /// \ref named-templ-param "Named parameter" for setting FlowMap
208
    /// type
210
    /// type.
209 211
    template <typename _FlowMap>
210 212
    struct SetFlowMap
211 213
      : public Preflow<Digraph, CapacityMap, SetFlowMapTraits<_FlowMap> > {
212 214
      typedef Preflow<Digraph, CapacityMap,
213 215
                      SetFlowMapTraits<_FlowMap> > Create;
214 216
    };
215 217

	
216 218
    template <typename _Elevator>
217 219
    struct SetElevatorTraits : public Traits {
218 220
      typedef _Elevator Elevator;
219 221
      static Elevator *createElevator(const Digraph&, int) {
220 222
        LEMON_ASSERT(false, "Elevator is not initialized");
221 223
        return 0; // ignore warnings
222 224
      }
223 225
    };
224 226

	
225 227
    /// \brief \ref named-templ-param "Named parameter" for setting
226 228
    /// Elevator type
227 229
    ///
228 230
    /// \ref named-templ-param "Named parameter" for setting Elevator
229
    /// type
231
    /// type. If this named parameter is used, then an external
232
    /// elevator object must be passed to the algorithm using the
233
    /// \ref elevator(Elevator&) "elevator()" function before calling
234
    /// \ref run() or \ref init().
235
    /// \sa SetStandardElevator
230 236
    template <typename _Elevator>
231 237
    struct SetElevator
232 238
      : public Preflow<Digraph, CapacityMap, SetElevatorTraits<_Elevator> > {
233 239
      typedef Preflow<Digraph, CapacityMap,
234 240
                      SetElevatorTraits<_Elevator> > Create;
235 241
    };
236 242

	
237 243
    template <typename _Elevator>
238 244
    struct SetStandardElevatorTraits : public Traits {
239 245
      typedef _Elevator Elevator;
240 246
      static Elevator *createElevator(const Digraph& digraph, int max_level) {
241 247
        return new Elevator(digraph, max_level);
242 248
      }
243 249
    };
244 250

	
245 251
    /// \brief \ref named-templ-param "Named parameter" for setting
246
    /// Elevator type
252
    /// Elevator type with automatic allocation
247 253
    ///
248 254
    /// \ref named-templ-param "Named parameter" for setting Elevator
249
    /// type. The Elevator should be standard constructor interface, ie.
250
    /// the digraph and the maximum level should be passed to it.
255
    /// type with automatic allocation.
256
    /// The Elevator should have standard constructor interface to be
257
    /// able to automatically created by the algorithm (i.e. the
258
    /// digraph and the maximum level should be passed to it).
259
    /// However an external elevator object could also be passed to the
260
    /// algorithm with the \ref elevator(Elevator&) "elevator()" function
261
    /// before calling \ref run() or \ref init().
262
    /// \sa SetElevator
251 263
    template <typename _Elevator>
252 264
    struct SetStandardElevator
253 265
      : public Preflow<Digraph, CapacityMap,
254 266
                       SetStandardElevatorTraits<_Elevator> > {
255 267
      typedef Preflow<Digraph, CapacityMap,
256 268
                      SetStandardElevatorTraits<_Elevator> > Create;
257 269
    };
258 270

	
259 271
    /// @}
260 272

	
261 273
  protected:
262 274

	
263 275
    Preflow() {}
264 276

	
265 277
  public:
266 278

	
267 279

	
268 280
    /// \brief The constructor of the class.
269 281
    ///
270 282
    /// The constructor of the class.
271 283
    /// \param digraph The digraph the algorithm runs on.
272 284
    /// \param capacity The capacity of the arcs.
273 285
    /// \param source The source node.
274 286
    /// \param target The target node.
275 287
    Preflow(const Digraph& digraph, const CapacityMap& capacity,
276
               Node source, Node target)
288
            Node source, Node target)
277 289
      : _graph(digraph), _capacity(&capacity),
278 290
        _node_num(0), _source(source), _target(target),
279 291
        _flow(0), _local_flow(false),
280 292
        _level(0), _local_level(false),
281 293
        _excess(0), _tolerance(), _phase() {}
282 294

	
283
    /// \brief Destrcutor.
295
    /// \brief Destructor.
284 296
    ///
285 297
    /// Destructor.
286 298
    ~Preflow() {
287 299
      destroyStructures();
288 300
    }
289 301

	
290 302
    /// \brief Sets the capacity map.
291 303
    ///
292 304
    /// Sets the capacity map.
293
    /// \return \c (*this)
305
    /// \return <tt>(*this)</tt>
294 306
    Preflow& capacityMap(const CapacityMap& map) {
295 307
      _capacity = &map;
296 308
      return *this;
297 309
    }
298 310

	
299 311
    /// \brief Sets the flow map.
300 312
    ///
301 313
    /// Sets the flow map.
302
    /// \return \c (*this)
314
    /// If you don't use this function before calling \ref run() or
315
    /// \ref init(), an instance will be allocated automatically.
316
    /// The destructor deallocates this automatically allocated map,
317
    /// of course.
318
    /// \return <tt>(*this)</tt>
303 319
    Preflow& flowMap(FlowMap& map) {
304 320
      if (_local_flow) {
305 321
        delete _flow;
306 322
        _local_flow = false;
307 323
      }
308 324
      _flow = &map;
309 325
      return *this;
310 326
    }
311 327

	
312
    /// \brief Returns the flow map.
328
    /// \brief Sets the source node.
313 329
    ///
314
    /// \return The flow map.
315
    const FlowMap& flowMap() {
316
      return *_flow;
330
    /// Sets the source node.
331
    /// \return <tt>(*this)</tt>
332
    Preflow& source(const Node& node) {
333
      _source = node;
334
      return *this;
317 335
    }
318 336

	
319
    /// \brief Sets the elevator.
337
    /// \brief Sets the target node.
320 338
    ///
321
    /// Sets the elevator.
322
    /// \return \c (*this)
339
    /// Sets the target node.
340
    /// \return <tt>(*this)</tt>
341
    Preflow& target(const Node& node) {
342
      _target = node;
343
      return *this;
344
    }
345

	
346
    /// \brief Sets the elevator used by algorithm.
347
    ///
348
    /// Sets the elevator used by algorithm.
349
    /// If you don't use this function before calling \ref run() or
350
    /// \ref init(), an instance will be allocated automatically.
351
    /// The destructor deallocates this automatically allocated elevator,
352
    /// of course.
353
    /// \return <tt>(*this)</tt>
323 354
    Preflow& elevator(Elevator& elevator) {
324 355
      if (_local_level) {
325 356
        delete _level;
326 357
        _local_level = false;
327 358
      }
328 359
      _level = &elevator;
329 360
      return *this;
330 361
    }
331 362

	
332
    /// \brief Returns the elevator.
363
    /// \brief Returns a const reference to the elevator.
333 364
    ///
334
    /// \return The elevator.
365
    /// Returns a const reference to the elevator.
366
    ///
367
    /// \pre Either \ref run() or \ref init() must be called before
368
    /// using this function.
335 369
    const Elevator& elevator() {
336 370
      return *_level;
337 371
    }
338 372

	
339
    /// \brief Sets the source node.
340
    ///
341
    /// Sets the source node.
342
    /// \return \c (*this)
343
    Preflow& source(const Node& node) {
344
      _source = node;
345
      return *this;
346
    }
347

	
348
    /// \brief Sets the target node.
349
    ///
350
    /// Sets the target node.
351
    /// \return \c (*this)
352
    Preflow& target(const Node& node) {
353
      _target = node;
354
      return *this;
355
    }
356

	
357 373
    /// \brief Sets the tolerance used by algorithm.
358 374
    ///
359 375
    /// Sets the tolerance used by algorithm.
360 376
    Preflow& tolerance(const Tolerance& tolerance) const {
361 377
      _tolerance = tolerance;
362 378
      return *this;
363 379
    }
364 380

	
365
    /// \brief Returns the tolerance used by algorithm.
381
    /// \brief Returns a const reference to the tolerance.
366 382
    ///
367
    /// Returns the tolerance used by algorithm.
383
    /// Returns a const reference to the tolerance.
368 384
    const Tolerance& tolerance() const {
369 385
      return tolerance;
370 386
    }
371 387

	
372
    /// \name Execution control The simplest way to execute the
373
    /// algorithm is to use one of the member functions called \c
374
    /// run().
375
    /// \n
376
    /// If you need more control on initial solution or
377
    /// execution then you have to call one \ref init() function and then
378
    /// the startFirstPhase() and if you need the startSecondPhase().
388
    /// \name Execution Control
389
    /// The simplest way to execute the preflow algorithm is to use
390
    /// \ref run() or \ref runMinCut().\n
391
    /// If you need more control on the initial solution or the execution,
392
    /// first you have to call one of the \ref init() functions, then
393
    /// \ref startFirstPhase() and if you need it \ref startSecondPhase().
379 394

	
380 395
    ///@{
381 396

	
382 397
    /// \brief Initializes the internal data structures.
383 398
    ///
384
    /// Initializes the internal data structures.
385
    ///
399
    /// Initializes the internal data structures and sets the initial
400
    /// flow to zero on each arc.
386 401
    void init() {
387 402
      createStructures();
388 403

	
389 404
      _phase = true;
390 405
      for (NodeIt n(_graph); n != INVALID; ++n) {
391 406
        _excess->set(n, 0);
392 407
      }
393 408

	
394 409
      for (ArcIt e(_graph); e != INVALID; ++e) {
395 410
        _flow->set(e, 0);
396 411
      }
397 412

	
398 413
      typename Digraph::template NodeMap<bool> reached(_graph, false);
399 414

	
400 415
      _level->initStart();
401 416
      _level->initAddItem(_target);
402 417

	
403 418
      std::vector<Node> queue;
404 419
      reached.set(_source, true);
405 420

	
406 421
      queue.push_back(_target);
407 422
      reached.set(_target, true);
408 423
      while (!queue.empty()) {
409 424
        _level->initNewLevel();
... ...
@@ -415,56 +430,57 @@
415 430
            if (!reached[u] && _tolerance.positive((*_capacity)[e])) {
416 431
              reached.set(u, true);
417 432
              _level->initAddItem(u);
418 433
              nqueue.push_back(u);
419 434
            }
420 435
          }
421 436
        }
422 437
        queue.swap(nqueue);
423 438
      }
424 439
      _level->initFinish();
425 440

	
426 441
      for (OutArcIt e(_graph, _source); e != INVALID; ++e) {
427 442
        if (_tolerance.positive((*_capacity)[e])) {
428 443
          Node u = _graph.target(e);
429 444
          if ((*_level)[u] == _level->maxLevel()) continue;
430 445
          _flow->set(e, (*_capacity)[e]);
431 446
          _excess->set(u, (*_excess)[u] + (*_capacity)[e]);
432 447
          if (u != _target && !_level->active(u)) {
433 448
            _level->activate(u);
434 449
          }
435 450
        }
436 451
      }
437 452
    }
438 453

	
439
    /// \brief Initializes the internal data structures.
454
    /// \brief Initializes the internal data structures using the
455
    /// given flow map.
440 456
    ///
441 457
    /// Initializes the internal data structures and sets the initial
442 458
    /// flow to the given \c flowMap. The \c flowMap should contain a
443
    /// flow or at least a preflow, ie. in each node excluding the
444
    /// target the incoming flow should greater or equal to the
459
    /// flow or at least a preflow, i.e. at each node excluding the
460
    /// source node the incoming flow should greater or equal to the
445 461
    /// outgoing flow.
446
    /// \return %False when the given \c flowMap is not a preflow.
462
    /// \return \c false if the given \c flowMap is not a preflow.
447 463
    template <typename FlowMap>
448 464
    bool init(const FlowMap& flowMap) {
449 465
      createStructures();
450 466

	
451 467
      for (ArcIt e(_graph); e != INVALID; ++e) {
452 468
        _flow->set(e, flowMap[e]);
453 469
      }
454 470

	
455 471
      for (NodeIt n(_graph); n != INVALID; ++n) {
456 472
        Value excess = 0;
457 473
        for (InArcIt e(_graph, n); e != INVALID; ++e) {
458 474
          excess += (*_flow)[e];
459 475
        }
460 476
        for (OutArcIt e(_graph, n); e != INVALID; ++e) {
461 477
          excess -= (*_flow)[e];
462 478
        }
463 479
        if (excess < 0 && n != _source) return false;
464 480
        _excess->set(n, excess);
465 481
      }
466 482

	
467 483
      typename Digraph::template NodeMap<bool> reached(_graph, false);
468 484

	
469 485
      _level->initStart();
470 486
      _level->initAddItem(_target);
... ...
@@ -515,49 +531,50 @@
515 531
      }
516 532
      for (InArcIt e(_graph, _source); e != INVALID; ++e) {
517 533
        Value rem = (*_flow)[e];
518 534
        if (_tolerance.positive(rem)) {
519 535
          Node v = _graph.source(e);
520 536
          if ((*_level)[v] == _level->maxLevel()) continue;
521 537
          _flow->set(e, 0);
522 538
          _excess->set(v, (*_excess)[v] + rem);
523 539
          if (v != _target && !_level->active(v)) {
524 540
            _level->activate(v);
525 541
          }
526 542
        }
527 543
      }
528 544
      return true;
529 545
    }
530 546

	
531 547
    /// \brief Starts the first phase of the preflow algorithm.
532 548
    ///
533 549
    /// The preflow algorithm consists of two phases, this method runs
534 550
    /// the first phase. After the first phase the maximum flow value
535 551
    /// and a minimum value cut can already be computed, although a
536 552
    /// maximum flow is not yet obtained. So after calling this method
537 553
    /// \ref flowValue() returns the value of a maximum flow and \ref
538 554
    /// minCut() returns a minimum cut.
539
    /// \pre One of the \ref init() functions should be called.
555
    /// \pre One of the \ref init() functions must be called before
556
    /// using this function.
540 557
    void startFirstPhase() {
541 558
      _phase = true;
542 559

	
543 560
      Node n = _level->highestActive();
544 561
      int level = _level->highestActiveLevel();
545 562
      while (n != INVALID) {
546 563
        int num = _node_num;
547 564

	
548 565
        while (num > 0 && n != INVALID) {
549 566
          Value excess = (*_excess)[n];
550 567
          int new_level = _level->maxLevel();
551 568

	
552 569
          for (OutArcIt e(_graph, n); e != INVALID; ++e) {
553 570
            Value rem = (*_capacity)[e] - (*_flow)[e];
554 571
            if (!_tolerance.positive(rem)) continue;
555 572
            Node v = _graph.target(e);
556 573
            if ((*_level)[v] < level) {
557 574
              if (!_level->active(v) && v != _target) {
558 575
                _level->activate(v);
559 576
              }
560 577
              if (!_tolerance.less(rem, excess)) {
561 578
                _flow->set(e, (*_flow)[e] + excess);
562 579
                _excess->set(v, (*_excess)[v] + excess);
563 580
                excess = 0;
... ...
@@ -681,54 +698,54 @@
681 698
            if (_level->emptyLevel(level)) {
682 699
              _level->liftToTop(level);
683 700
            }
684 701
          } else {
685 702
            _level->deactivate(n);
686 703
          }
687 704

	
688 705
          while (level >= 0 && _level->activeFree(level)) {
689 706
            --level;
690 707
          }
691 708
          if (level == -1) {
692 709
            n = _level->highestActive();
693 710
            level = _level->highestActiveLevel();
694 711
          } else {
695 712
            n = _level->activeOn(level);
696 713
          }
697 714
          --num;
698 715
        }
699 716
      }
700 717
    }
701 718

	
702 719
    /// \brief Starts the second phase of the preflow algorithm.
703 720
    ///
704 721
    /// The preflow algorithm consists of two phases, this method runs
705
    /// the second phase. After calling \ref init() and \ref
706
    /// startFirstPhase() and then \ref startSecondPhase(), \ref
707
    /// flowMap() return a maximum flow, \ref flowValue() returns the
722
    /// the second phase. After calling one of the \ref init() functions
723
    /// and \ref startFirstPhase() and then \ref startSecondPhase(),
724
    /// \ref flowMap() returns a maximum flow, \ref flowValue() returns the
708 725
    /// value of a maximum flow, \ref minCut() returns a minimum cut
709
    /// \pre The \ref init() and startFirstPhase() functions should be
710
    /// called before.
726
    /// \pre One of the \ref init() functions and \ref startFirstPhase()
727
    /// must be called before using this function.
711 728
    void startSecondPhase() {
712 729
      _phase = false;
713 730

	
714 731
      typename Digraph::template NodeMap<bool> reached(_graph);
715 732
      for (NodeIt n(_graph); n != INVALID; ++n) {
716 733
        reached.set(n, (*_level)[n] < _level->maxLevel());
717 734
      }
718 735

	
719 736
      _level->initStart();
720 737
      _level->initAddItem(_source);
721 738

	
722 739
      std::vector<Node> queue;
723 740
      queue.push_back(_source);
724 741
      reached.set(_source, true);
725 742

	
726 743
      while (!queue.empty()) {
727 744
        _level->initNewLevel();
728 745
        std::vector<Node> nqueue;
729 746
        for (int i = 0; i < int(queue.size()); ++i) {
730 747
          Node n = queue[i];
731 748
          for (OutArcIt e(_graph, n); e != INVALID; ++e) {
732 749
            Node v = _graph.target(e);
733 750
            if (!reached[v] && _tolerance.positive((*_flow)[e])) {
734 751
              reached.set(v, true);
... ...
@@ -842,76 +859,106 @@
842 859
    ///   pf.startSecondPhase();
843 860
    /// \endcode
844 861
    void run() {
845 862
      init();
846 863
      startFirstPhase();
847 864
      startSecondPhase();
848 865
    }
849 866

	
850 867
    /// \brief Runs the preflow algorithm to compute the minimum cut.
851 868
    ///
852 869
    /// Runs the preflow algorithm to compute the minimum cut.
853 870
    /// \note pf.runMinCut() is just a shortcut of the following code.
854 871
    /// \code
855 872
    ///   pf.init();
856 873
    ///   pf.startFirstPhase();
857 874
    /// \endcode
858 875
    void runMinCut() {
859 876
      init();
860 877
      startFirstPhase();
861 878
    }
862 879

	
863 880
    /// @}
864 881

	
865 882
    /// \name Query Functions
866
    /// The result of the %Preflow algorithm can be obtained using these
883
    /// The results of the preflow algorithm can be obtained using these
867 884
    /// functions.\n
868
    /// Before the use of these functions,
869
    /// either run() or start() must be called.
885
    /// Either one of the \ref run() "run*()" functions or one of the
886
    /// \ref startFirstPhase() "start*()" functions should be called
887
    /// before using them.
870 888

	
871 889
    ///@{
872 890

	
873 891
    /// \brief Returns the value of the maximum flow.
874 892
    ///
875 893
    /// Returns the value of the maximum flow by returning the excess
876
    /// of the target node \c t. This value equals to the value of
877
    /// the maximum flow already after the first phase.
894
    /// of the target node. This value equals to the value of
895
    /// the maximum flow already after the first phase of the algorithm.
896
    ///
897
    /// \pre Either \ref run() or \ref init() must be called before
898
    /// using this function.
878 899
    Value flowValue() const {
879 900
      return (*_excess)[_target];
880 901
    }
881 902

	
882
    /// \brief Returns true when the node is on the source side of minimum cut.
903
    /// \brief Returns the flow on the given arc.
883 904
    ///
884
    /// Returns true when the node is on the source side of minimum
885
    /// cut. This method can be called both after running \ref
905
    /// Returns the flow on the given arc. This method can
906
    /// be called after the second phase of the algorithm.
907
    ///
908
    /// \pre Either \ref run() or \ref init() must be called before
909
    /// using this function.
910
    Value flow(const Arc& arc) const {
911
      return (*_flow)[arc];
912
    }
913

	
914
    /// \brief Returns a const reference to the flow map.
915
    ///
916
    /// Returns a const reference to the arc map storing the found flow.
917
    /// This method can be called after the second phase of the algorithm.
918
    ///
919
    /// \pre Either \ref run() or \ref init() must be called before
920
    /// using this function.
921
    const FlowMap& flowMap() {
922
      return *_flow;
923
    }
924

	
925
    /// \brief Returns \c true when the node is on the source side of the
926
    /// minimum cut.
927
    ///
928
    /// Returns true when the node is on the source side of the found
929
    /// minimum cut. This method can be called both after running \ref
886 930
    /// startFirstPhase() and \ref startSecondPhase().
931
    ///
932
    /// \pre Either \ref run() or \ref init() must be called before
933
    /// using this function.
887 934
    bool minCut(const Node& node) const {
888 935
      return ((*_level)[node] == _level->maxLevel()) == _phase;
889 936
    }
890 937

	
891
    /// \brief Returns a minimum value cut.
938
    /// \brief Gives back a minimum value cut.
892 939
    ///
893
    /// Sets the \c cutMap to the characteristic vector of a minimum value
894
    /// cut. This method can be called both after running \ref
895
    /// startFirstPhase() and \ref startSecondPhase(). The result after second
896
    /// phase could be changed slightly if inexact computation is used.
897
    /// \pre The \c cutMap should be a bool-valued node-map.
940
    /// Sets \c cutMap to the characteristic vector of a minimum value
941
    /// cut. \c cutMap should be a \ref concepts::WriteMap "writable"
942
    /// node map with \c bool (or convertible) value type.
943
    ///
944
    /// This method can be called both after running \ref startFirstPhase()
945
    /// and \ref startSecondPhase(). The result after the second phase
946
    /// could be slightly different if inexact computation is used.
947
    ///
948
    /// \note This function calls \ref minCut() for each node, so it runs in
949
    /// \f$O(n)\f$ time.
950
    ///
951
    /// \pre Either \ref run() or \ref init() must be called before
952
    /// using this function.
898 953
    template <typename CutMap>
899 954
    void minCutMap(CutMap& cutMap) const {
900 955
      for (NodeIt n(_graph); n != INVALID; ++n) {
901 956
        cutMap.set(n, minCut(n));
902 957
      }
903 958
    }
904 959

	
905
    /// \brief Returns the flow on the arc.
906
    ///
907
    /// Sets the \c flowMap to the flow on the arcs. This method can
908
    /// be called after the second phase of algorithm.
909
    Value flow(const Arc& arc) const {
910
      return (*_flow)[arc];
911
    }
912

	
913 960
    /// @}
914 961
  };
915 962
}
916 963

	
917 964
#endif
0 comments (0 inline)