1.1 --- a/lemon/preflow.h Mon Jul 16 16:21:40 2018 +0200
1.2 +++ b/lemon/preflow.h Wed Oct 17 19:14:07 2018 +0200
1.3 @@ -2,7 +2,7 @@
1.4 *
1.5 * This file is a part of LEMON, a generic C++ optimization library.
1.6 *
1.7 - * Copyright (C) 2003-2010
1.8 + * Copyright (C) 2003-2013
1.9 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
1.10 * (Egervary Research Group on Combinatorial Optimization, EGRES).
1.11 *
1.12 @@ -102,12 +102,12 @@
1.13 ///
1.14 /// This class provides an implementation of Goldberg-Tarjan's \e preflow
1.15 /// \e push-relabel algorithm producing a \ref max_flow
1.16 - /// "flow of maximum value" in a digraph \ref clrs01algorithms,
1.17 - /// \ref amo93networkflows, \ref goldberg88newapproach.
1.18 + /// "flow of maximum value" in a digraph \cite clrs01algorithms,
1.19 + /// \cite amo93networkflows, \cite goldberg88newapproach.
1.20 /// The preflow algorithms are the fastest known maximum
1.21 /// flow algorithms. The current implementation uses a mixture of the
1.22 /// \e "highest label" and the \e "bound decrease" heuristics.
1.23 - /// The worst case time complexity of the algorithm is \f$O(n^2\sqrt{e})\f$.
1.24 + /// The worst case time complexity of the algorithm is \f$O(n^2\sqrt{m})\f$.
1.25 ///
1.26 /// The algorithm consists of two phases. After the first phase
1.27 /// the maximum flow value and the minimum cut is obtained. The
1.28 @@ -134,7 +134,7 @@
1.29 class Preflow {
1.30 public:
1.31
1.32 - ///The \ref PreflowDefaultTraits "traits class" of the algorithm.
1.33 + ///The \ref lemon::PreflowDefaultTraits "traits class" of the algorithm.
1.34 typedef TR Traits;
1.35 ///The type of the digraph the algorithm runs on.
1.36 typedef typename Traits::Digraph Digraph;
1.37 @@ -476,7 +476,7 @@
1.38 /// Initializes the internal data structures and sets the initial
1.39 /// flow to the given \c flowMap. The \c flowMap should contain a
1.40 /// flow or at least a preflow, i.e. at each node excluding the
1.41 - /// source node the incoming flow should greater or equal to the
1.42 + /// source node the incoming flow should be greater or equal to the
1.43 /// outgoing flow.
1.44 /// \return \c false if the given \c flowMap is not a preflow.
1.45 template <typename FlowMap>
1.46 @@ -495,7 +495,7 @@
1.47 for (OutArcIt e(_graph, n); e != INVALID; ++e) {
1.48 excess -= (*_flow)[e];
1.49 }
1.50 - if (excess < 0 && n != _source) return false;
1.51 + if (_tolerance.negative(excess) && n != _source) return false;
1.52 (*_excess)[n] = excess;
1.53 }
1.54
1.55 @@ -554,10 +554,10 @@
1.56 (*_excess)[v] += rem;
1.57 }
1.58 }
1.59 - for (NodeIt n(_graph); n != INVALID; ++n)
1.60 + for (NodeIt n(_graph); n != INVALID; ++n)
1.61 if(n!=_source && n!=_target && _tolerance.positive((*_excess)[n]))
1.62 _level->activate(n);
1.63 -
1.64 +
1.65 return true;
1.66 }
1.67
1.68 @@ -585,7 +585,7 @@
1.69 if (n == INVALID) goto first_phase_done;
1.70 level = _level->highestActiveLevel();
1.71 --num;
1.72 -
1.73 +
1.74 Value excess = (*_excess)[n];
1.75 int new_level = _level->maxLevel();
1.76
1.77 @@ -639,7 +639,7 @@
1.78
1.79 (*_excess)[n] = excess;
1.80
1.81 - if (excess != 0) {
1.82 + if (_tolerance.nonZero(excess)) {
1.83 if (new_level + 1 < _level->maxLevel()) {
1.84 _level->liftHighestActive(new_level + 1);
1.85 } else {
1.86 @@ -720,7 +720,7 @@
1.87
1.88 (*_excess)[n] = excess;
1.89
1.90 - if (excess != 0) {
1.91 + if (_tolerance.nonZero(excess)) {
1.92 if (new_level + 1 < _level->maxLevel()) {
1.93 _level->liftActiveOn(level, new_level + 1);
1.94 } else {
1.95 @@ -791,7 +791,7 @@
1.96 for (NodeIt n(_graph); n != INVALID; ++n) {
1.97 if (!reached[n]) {
1.98 _level->dirtyTopButOne(n);
1.99 - } else if ((*_excess)[n] > 0 && _target != n) {
1.100 + } else if (_tolerance.positive((*_excess)[n]) && _target != n) {
1.101 _level->activate(n);
1.102 }
1.103 }
1.104 @@ -852,7 +852,7 @@
1.105
1.106 (*_excess)[n] = excess;
1.107
1.108 - if (excess != 0) {
1.109 + if (_tolerance.nonZero(excess)) {
1.110 if (new_level + 1 < _level->maxLevel()) {
1.111 _level->liftHighestActive(new_level + 1);
1.112 } else {