1.1 --- a/lemon/preflow.h Mon Jan 12 23:11:39 2009 +0100
1.2 +++ b/lemon/preflow.h Thu Nov 05 15:48:01 2009 +0100
1.3 @@ -31,19 +31,19 @@
1.4 /// \brief Default traits class of Preflow class.
1.5 ///
1.6 /// Default traits class of Preflow class.
1.7 - /// \tparam _Digraph Digraph type.
1.8 - /// \tparam _CapacityMap Capacity map type.
1.9 - template <typename _Digraph, typename _CapacityMap>
1.10 + /// \tparam GR Digraph type.
1.11 + /// \tparam CAP Capacity map type.
1.12 + template <typename GR, typename CAP>
1.13 struct PreflowDefaultTraits {
1.14
1.15 /// \brief The type of the digraph the algorithm runs on.
1.16 - typedef _Digraph Digraph;
1.17 + typedef GR Digraph;
1.18
1.19 /// \brief The type of the map that stores the arc capacities.
1.20 ///
1.21 /// The type of the map that stores the arc capacities.
1.22 /// It must meet the \ref concepts::ReadMap "ReadMap" concept.
1.23 - typedef _CapacityMap CapacityMap;
1.24 + typedef CAP CapacityMap;
1.25
1.26 /// \brief The type of the flow values.
1.27 typedef typename CapacityMap::Value Value;
1.28 @@ -52,12 +52,16 @@
1.29 ///
1.30 /// The type of the map that stores the flow values.
1.31 /// It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
1.32 +#ifdef DOXYGEN
1.33 + typedef GR::ArcMap<Value> FlowMap;
1.34 +#else
1.35 typedef typename Digraph::template ArcMap<Value> FlowMap;
1.36 +#endif
1.37
1.38 /// \brief Instantiates a FlowMap.
1.39 ///
1.40 /// This function instantiates a \ref FlowMap.
1.41 - /// \param digraph The digraph, to which we would like to define
1.42 + /// \param digraph The digraph for which we would like to define
1.43 /// the flow map.
1.44 static FlowMap* createFlowMap(const Digraph& digraph) {
1.45 return new FlowMap(digraph);
1.46 @@ -67,14 +71,17 @@
1.47 ///
1.48 /// The elevator type used by Preflow algorithm.
1.49 ///
1.50 - /// \sa Elevator
1.51 - /// \sa LinkedElevator
1.52 - typedef LinkedElevator<Digraph, typename Digraph::Node> Elevator;
1.53 + /// \sa Elevator, LinkedElevator
1.54 +#ifdef DOXYGEN
1.55 + typedef lemon::Elevator<GR, GR::Node> Elevator;
1.56 +#else
1.57 + typedef lemon::Elevator<Digraph, typename Digraph::Node> Elevator;
1.58 +#endif
1.59
1.60 /// \brief Instantiates an Elevator.
1.61 ///
1.62 /// This function instantiates an \ref Elevator.
1.63 - /// \param digraph The digraph, to which we would like to define
1.64 + /// \param digraph The digraph for which we would like to define
1.65 /// the elevator.
1.66 /// \param max_level The maximum level of the elevator.
1.67 static Elevator* createElevator(const Digraph& digraph, int max_level) {
1.68 @@ -94,9 +101,11 @@
1.69 /// \brief %Preflow algorithm class.
1.70 ///
1.71 /// This class provides an implementation of Goldberg-Tarjan's \e preflow
1.72 - /// \e push-relabel algorithm producing a flow of maximum value in a
1.73 - /// digraph. The preflow algorithms are the fastest known maximum
1.74 - /// flow algorithms. The current implementation use a mixture of the
1.75 + /// \e push-relabel algorithm producing a \ref max_flow
1.76 + /// "flow of maximum value" in a digraph \ref clrs01algorithms,
1.77 + /// \ref amo93networkflows, \ref goldberg88newapproach.
1.78 + /// The preflow algorithms are the fastest known maximum
1.79 + /// flow algorithms. The current implementation uses a mixture of the
1.80 /// \e "highest label" and the \e "bound decrease" heuristics.
1.81 /// The worst case time complexity of the algorithm is \f$O(n^2\sqrt{e})\f$.
1.82 ///
1.83 @@ -104,21 +113,21 @@
1.84 /// the maximum flow value and the minimum cut is obtained. The
1.85 /// second phase constructs a feasible maximum flow on each arc.
1.86 ///
1.87 - /// \tparam _Digraph The type of the digraph the algorithm runs on.
1.88 - /// \tparam _CapacityMap The type of the capacity map. The default map
1.89 - /// type is \ref concepts::Digraph::ArcMap "_Digraph::ArcMap<int>".
1.90 + /// \tparam GR The type of the digraph the algorithm runs on.
1.91 + /// \tparam CAP The type of the capacity map. The default map
1.92 + /// type is \ref concepts::Digraph::ArcMap "GR::ArcMap<int>".
1.93 #ifdef DOXYGEN
1.94 - template <typename _Digraph, typename _CapacityMap, typename _Traits>
1.95 + template <typename GR, typename CAP, typename TR>
1.96 #else
1.97 - template <typename _Digraph,
1.98 - typename _CapacityMap = typename _Digraph::template ArcMap<int>,
1.99 - typename _Traits = PreflowDefaultTraits<_Digraph, _CapacityMap> >
1.100 + template <typename GR,
1.101 + typename CAP = typename GR::template ArcMap<int>,
1.102 + typename TR = PreflowDefaultTraits<GR, CAP> >
1.103 #endif
1.104 class Preflow {
1.105 public:
1.106
1.107 ///The \ref PreflowDefaultTraits "traits class" of the algorithm.
1.108 - typedef _Traits Traits;
1.109 + typedef TR Traits;
1.110 ///The type of the digraph the algorithm runs on.
1.111 typedef typename Traits::Digraph Digraph;
1.112 ///The type of the capacity map.
1.113 @@ -194,9 +203,9 @@
1.114
1.115 ///@{
1.116
1.117 - template <typename _FlowMap>
1.118 + template <typename T>
1.119 struct SetFlowMapTraits : public Traits {
1.120 - typedef _FlowMap FlowMap;
1.121 + typedef T FlowMap;
1.122 static FlowMap *createFlowMap(const Digraph&) {
1.123 LEMON_ASSERT(false, "FlowMap is not initialized");
1.124 return 0; // ignore warnings
1.125 @@ -208,16 +217,16 @@
1.126 ///
1.127 /// \ref named-templ-param "Named parameter" for setting FlowMap
1.128 /// type.
1.129 - template <typename _FlowMap>
1.130 + template <typename T>
1.131 struct SetFlowMap
1.132 - : public Preflow<Digraph, CapacityMap, SetFlowMapTraits<_FlowMap> > {
1.133 + : public Preflow<Digraph, CapacityMap, SetFlowMapTraits<T> > {
1.134 typedef Preflow<Digraph, CapacityMap,
1.135 - SetFlowMapTraits<_FlowMap> > Create;
1.136 + SetFlowMapTraits<T> > Create;
1.137 };
1.138
1.139 - template <typename _Elevator>
1.140 + template <typename T>
1.141 struct SetElevatorTraits : public Traits {
1.142 - typedef _Elevator Elevator;
1.143 + typedef T Elevator;
1.144 static Elevator *createElevator(const Digraph&, int) {
1.145 LEMON_ASSERT(false, "Elevator is not initialized");
1.146 return 0; // ignore warnings
1.147 @@ -233,16 +242,16 @@
1.148 /// \ref elevator(Elevator&) "elevator()" function before calling
1.149 /// \ref run() or \ref init().
1.150 /// \sa SetStandardElevator
1.151 - template <typename _Elevator>
1.152 + template <typename T>
1.153 struct SetElevator
1.154 - : public Preflow<Digraph, CapacityMap, SetElevatorTraits<_Elevator> > {
1.155 + : public Preflow<Digraph, CapacityMap, SetElevatorTraits<T> > {
1.156 typedef Preflow<Digraph, CapacityMap,
1.157 - SetElevatorTraits<_Elevator> > Create;
1.158 + SetElevatorTraits<T> > Create;
1.159 };
1.160
1.161 - template <typename _Elevator>
1.162 + template <typename T>
1.163 struct SetStandardElevatorTraits : public Traits {
1.164 - typedef _Elevator Elevator;
1.165 + typedef T Elevator;
1.166 static Elevator *createElevator(const Digraph& digraph, int max_level) {
1.167 return new Elevator(digraph, max_level);
1.168 }
1.169 @@ -260,12 +269,12 @@
1.170 /// algorithm with the \ref elevator(Elevator&) "elevator()" function
1.171 /// before calling \ref run() or \ref init().
1.172 /// \sa SetElevator
1.173 - template <typename _Elevator>
1.174 + template <typename T>
1.175 struct SetStandardElevator
1.176 : public Preflow<Digraph, CapacityMap,
1.177 - SetStandardElevatorTraits<_Elevator> > {
1.178 + SetStandardElevatorTraits<T> > {
1.179 typedef Preflow<Digraph, CapacityMap,
1.180 - SetStandardElevatorTraits<_Elevator> > Create;
1.181 + SetStandardElevatorTraits<T> > Create;
1.182 };
1.183
1.184 /// @}
1.185 @@ -370,26 +379,28 @@
1.186 return *_level;
1.187 }
1.188
1.189 - /// \brief Sets the tolerance used by algorithm.
1.190 + /// \brief Sets the tolerance used by the algorithm.
1.191 ///
1.192 - /// Sets the tolerance used by algorithm.
1.193 - Preflow& tolerance(const Tolerance& tolerance) const {
1.194 + /// Sets the tolerance object used by the algorithm.
1.195 + /// \return <tt>(*this)</tt>
1.196 + Preflow& tolerance(const Tolerance& tolerance) {
1.197 _tolerance = tolerance;
1.198 return *this;
1.199 }
1.200
1.201 /// \brief Returns a const reference to the tolerance.
1.202 ///
1.203 - /// Returns a const reference to the tolerance.
1.204 + /// Returns a const reference to the tolerance object used by
1.205 + /// the algorithm.
1.206 const Tolerance& tolerance() const {
1.207 - return tolerance;
1.208 + return _tolerance;
1.209 }
1.210
1.211 /// \name Execution Control
1.212 /// The simplest way to execute the preflow algorithm is to use
1.213 /// \ref run() or \ref runMinCut().\n
1.214 - /// If you need more control on the initial solution or the execution,
1.215 - /// first you have to call one of the \ref init() functions, then
1.216 + /// If you need better control on the initial solution or the execution,
1.217 + /// you have to call one of the \ref init() functions first, then
1.218 /// \ref startFirstPhase() and if you need it \ref startSecondPhase().
1.219
1.220 ///@{
1.221 @@ -403,7 +414,7 @@
1.222
1.223 _phase = true;
1.224 for (NodeIt n(_graph); n != INVALID; ++n) {
1.225 - _excess->set(n, 0);
1.226 + (*_excess)[n] = 0;
1.227 }
1.228
1.229 for (ArcIt e(_graph); e != INVALID; ++e) {
1.230 @@ -416,10 +427,10 @@
1.231 _level->initAddItem(_target);
1.232
1.233 std::vector<Node> queue;
1.234 - reached.set(_source, true);
1.235 + reached[_source] = true;
1.236
1.237 queue.push_back(_target);
1.238 - reached.set(_target, true);
1.239 + reached[_target] = true;
1.240 while (!queue.empty()) {
1.241 _level->initNewLevel();
1.242 std::vector<Node> nqueue;
1.243 @@ -428,7 +439,7 @@
1.244 for (InArcIt e(_graph, n); e != INVALID; ++e) {
1.245 Node u = _graph.source(e);
1.246 if (!reached[u] && _tolerance.positive((*_capacity)[e])) {
1.247 - reached.set(u, true);
1.248 + reached[u] = true;
1.249 _level->initAddItem(u);
1.250 nqueue.push_back(u);
1.251 }
1.252 @@ -443,7 +454,7 @@
1.253 Node u = _graph.target(e);
1.254 if ((*_level)[u] == _level->maxLevel()) continue;
1.255 _flow->set(e, (*_capacity)[e]);
1.256 - _excess->set(u, (*_excess)[u] + (*_capacity)[e]);
1.257 + (*_excess)[u] += (*_capacity)[e];
1.258 if (u != _target && !_level->active(u)) {
1.259 _level->activate(u);
1.260 }
1.261 @@ -477,7 +488,7 @@
1.262 excess -= (*_flow)[e];
1.263 }
1.264 if (excess < 0 && n != _source) return false;
1.265 - _excess->set(n, excess);
1.266 + (*_excess)[n] = excess;
1.267 }
1.268
1.269 typename Digraph::template NodeMap<bool> reached(_graph, false);
1.270 @@ -486,10 +497,10 @@
1.271 _level->initAddItem(_target);
1.272
1.273 std::vector<Node> queue;
1.274 - reached.set(_source, true);
1.275 + reached[_source] = true;
1.276
1.277 queue.push_back(_target);
1.278 - reached.set(_target, true);
1.279 + reached[_target] = true;
1.280 while (!queue.empty()) {
1.281 _level->initNewLevel();
1.282 std::vector<Node> nqueue;
1.283 @@ -499,7 +510,7 @@
1.284 Node u = _graph.source(e);
1.285 if (!reached[u] &&
1.286 _tolerance.positive((*_capacity)[e] - (*_flow)[e])) {
1.287 - reached.set(u, true);
1.288 + reached[u] = true;
1.289 _level->initAddItem(u);
1.290 nqueue.push_back(u);
1.291 }
1.292 @@ -507,7 +518,7 @@
1.293 for (OutArcIt e(_graph, n); e != INVALID; ++e) {
1.294 Node v = _graph.target(e);
1.295 if (!reached[v] && _tolerance.positive((*_flow)[e])) {
1.296 - reached.set(v, true);
1.297 + reached[v] = true;
1.298 _level->initAddItem(v);
1.299 nqueue.push_back(v);
1.300 }
1.301 @@ -523,7 +534,7 @@
1.302 Node u = _graph.target(e);
1.303 if ((*_level)[u] == _level->maxLevel()) continue;
1.304 _flow->set(e, (*_capacity)[e]);
1.305 - _excess->set(u, (*_excess)[u] + rem);
1.306 + (*_excess)[u] += rem;
1.307 if (u != _target && !_level->active(u)) {
1.308 _level->activate(u);
1.309 }
1.310 @@ -535,7 +546,7 @@
1.311 Node v = _graph.source(e);
1.312 if ((*_level)[v] == _level->maxLevel()) continue;
1.313 _flow->set(e, 0);
1.314 - _excess->set(v, (*_excess)[v] + rem);
1.315 + (*_excess)[v] += rem;
1.316 if (v != _target && !_level->active(v)) {
1.317 _level->activate(v);
1.318 }
1.319 @@ -576,12 +587,12 @@
1.320 }
1.321 if (!_tolerance.less(rem, excess)) {
1.322 _flow->set(e, (*_flow)[e] + excess);
1.323 - _excess->set(v, (*_excess)[v] + excess);
1.324 + (*_excess)[v] += excess;
1.325 excess = 0;
1.326 goto no_more_push_1;
1.327 } else {
1.328 excess -= rem;
1.329 - _excess->set(v, (*_excess)[v] + rem);
1.330 + (*_excess)[v] += rem;
1.331 _flow->set(e, (*_capacity)[e]);
1.332 }
1.333 } else if (new_level > (*_level)[v]) {
1.334 @@ -599,12 +610,12 @@
1.335 }
1.336 if (!_tolerance.less(rem, excess)) {
1.337 _flow->set(e, (*_flow)[e] - excess);
1.338 - _excess->set(v, (*_excess)[v] + excess);
1.339 + (*_excess)[v] += excess;
1.340 excess = 0;
1.341 goto no_more_push_1;
1.342 } else {
1.343 excess -= rem;
1.344 - _excess->set(v, (*_excess)[v] + rem);
1.345 + (*_excess)[v] += rem;
1.346 _flow->set(e, 0);
1.347 }
1.348 } else if (new_level > (*_level)[v]) {
1.349 @@ -614,7 +625,7 @@
1.350
1.351 no_more_push_1:
1.352
1.353 - _excess->set(n, excess);
1.354 + (*_excess)[n] = excess;
1.355
1.356 if (excess != 0) {
1.357 if (new_level + 1 < _level->maxLevel()) {
1.358 @@ -649,12 +660,12 @@
1.359 }
1.360 if (!_tolerance.less(rem, excess)) {
1.361 _flow->set(e, (*_flow)[e] + excess);
1.362 - _excess->set(v, (*_excess)[v] + excess);
1.363 + (*_excess)[v] += excess;
1.364 excess = 0;
1.365 goto no_more_push_2;
1.366 } else {
1.367 excess -= rem;
1.368 - _excess->set(v, (*_excess)[v] + rem);
1.369 + (*_excess)[v] += rem;
1.370 _flow->set(e, (*_capacity)[e]);
1.371 }
1.372 } else if (new_level > (*_level)[v]) {
1.373 @@ -672,12 +683,12 @@
1.374 }
1.375 if (!_tolerance.less(rem, excess)) {
1.376 _flow->set(e, (*_flow)[e] - excess);
1.377 - _excess->set(v, (*_excess)[v] + excess);
1.378 + (*_excess)[v] += excess;
1.379 excess = 0;
1.380 goto no_more_push_2;
1.381 } else {
1.382 excess -= rem;
1.383 - _excess->set(v, (*_excess)[v] + rem);
1.384 + (*_excess)[v] += rem;
1.385 _flow->set(e, 0);
1.386 }
1.387 } else if (new_level > (*_level)[v]) {
1.388 @@ -687,7 +698,7 @@
1.389
1.390 no_more_push_2:
1.391
1.392 - _excess->set(n, excess);
1.393 + (*_excess)[n] = excess;
1.394
1.395 if (excess != 0) {
1.396 if (new_level + 1 < _level->maxLevel()) {
1.397 @@ -730,7 +741,7 @@
1.398
1.399 typename Digraph::template NodeMap<bool> reached(_graph);
1.400 for (NodeIt n(_graph); n != INVALID; ++n) {
1.401 - reached.set(n, (*_level)[n] < _level->maxLevel());
1.402 + reached[n] = (*_level)[n] < _level->maxLevel();
1.403 }
1.404
1.405 _level->initStart();
1.406 @@ -738,7 +749,7 @@
1.407
1.408 std::vector<Node> queue;
1.409 queue.push_back(_source);
1.410 - reached.set(_source, true);
1.411 + reached[_source] = true;
1.412
1.413 while (!queue.empty()) {
1.414 _level->initNewLevel();
1.415 @@ -748,7 +759,7 @@
1.416 for (OutArcIt e(_graph, n); e != INVALID; ++e) {
1.417 Node v = _graph.target(e);
1.418 if (!reached[v] && _tolerance.positive((*_flow)[e])) {
1.419 - reached.set(v, true);
1.420 + reached[v] = true;
1.421 _level->initAddItem(v);
1.422 nqueue.push_back(v);
1.423 }
1.424 @@ -757,7 +768,7 @@
1.425 Node u = _graph.source(e);
1.426 if (!reached[u] &&
1.427 _tolerance.positive((*_capacity)[e] - (*_flow)[e])) {
1.428 - reached.set(u, true);
1.429 + reached[u] = true;
1.430 _level->initAddItem(u);
1.431 nqueue.push_back(u);
1.432 }
1.433 @@ -791,12 +802,12 @@
1.434 }
1.435 if (!_tolerance.less(rem, excess)) {
1.436 _flow->set(e, (*_flow)[e] + excess);
1.437 - _excess->set(v, (*_excess)[v] + excess);
1.438 + (*_excess)[v] += excess;
1.439 excess = 0;
1.440 goto no_more_push;
1.441 } else {
1.442 excess -= rem;
1.443 - _excess->set(v, (*_excess)[v] + rem);
1.444 + (*_excess)[v] += rem;
1.445 _flow->set(e, (*_capacity)[e]);
1.446 }
1.447 } else if (new_level > (*_level)[v]) {
1.448 @@ -814,12 +825,12 @@
1.449 }
1.450 if (!_tolerance.less(rem, excess)) {
1.451 _flow->set(e, (*_flow)[e] - excess);
1.452 - _excess->set(v, (*_excess)[v] + excess);
1.453 + (*_excess)[v] += excess;
1.454 excess = 0;
1.455 goto no_more_push;
1.456 } else {
1.457 excess -= rem;
1.458 - _excess->set(v, (*_excess)[v] + rem);
1.459 + (*_excess)[v] += rem;
1.460 _flow->set(e, 0);
1.461 }
1.462 } else if (new_level > (*_level)[v]) {
1.463 @@ -829,7 +840,7 @@
1.464
1.465 no_more_push:
1.466
1.467 - _excess->set(n, excess);
1.468 + (*_excess)[n] = excess;
1.469
1.470 if (excess != 0) {
1.471 if (new_level + 1 < _level->maxLevel()) {
1.472 @@ -900,9 +911,9 @@
1.473 return (*_excess)[_target];
1.474 }
1.475
1.476 - /// \brief Returns the flow on the given arc.
1.477 + /// \brief Returns the flow value on the given arc.
1.478 ///
1.479 - /// Returns the flow on the given arc. This method can
1.480 + /// Returns the flow value on the given arc. This method can
1.481 /// be called after the second phase of the algorithm.
1.482 ///
1.483 /// \pre Either \ref run() or \ref init() must be called before
1.484 @@ -946,7 +957,7 @@
1.485 /// could be slightly different if inexact computation is used.
1.486 ///
1.487 /// \note This function calls \ref minCut() for each node, so it runs in
1.488 - /// \f$O(n)\f$ time.
1.489 + /// O(n) time.
1.490 ///
1.491 /// \pre Either \ref run() or \ref init() must be called before
1.492 /// using this function.