Changeset 658:85cb3aa71cce in lemon for lemon/preflow.h

Timestamp:

04/21/09 16:18:54 (15 years ago)

Author:

Alpar Juttner <alpar@…>

Branch:

default

Children:

659:0c8e5c688440, 660:b1811c363299, 666:ec817dfc2cb7

Parents:

647:0ba8dfce7259 (diff), 657:dacc2cee2b4c (diff)
Note: this is a merge changeset, the changes displayed below correspond to the merge itself.
Use the (diff) links above to see all the changes relative to each parent.

Phase:

public

Message:

Merge and fix

Files:

• lemon/preflow.h (modified) (17 diffs)
• lemon/preflow.h (modified) (32 diffs)

lemon/preflow.h

@@ -47 +47 @@
 
     /// \brief The type of the flow values.
-    typedef typename CapacityMap::Value Value;
+    typedef typename CapacityMap::Value Flow;
 
     /// \brief The type of the map that stores the flow values.
@@ -53 +53 @@
     /// The type of the map that stores the flow values.
     /// It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
-    typedef typename Digraph::template ArcMap<Value> FlowMap;
+    typedef typename Digraph::template ArcMap<Flow> FlowMap;
 
     /// \brief Instantiates a FlowMap.
     ///
     /// This function instantiates a \ref FlowMap.
-    /// \param digraph The digraph, to which we would like to define
+    /// \param digraph The digraph for which we would like to define
     /// the flow map.
     static FlowMap* createFlowMap(const Digraph& digraph) {
@@ -75 +75 @@
     ///
     /// This function instantiates an \ref Elevator.
-    /// \param digraph The digraph, to which we would like to define
+    /// \param digraph The digraph for which we would like to define
     /// the elevator.
     /// \param max_level The maximum level of the elevator.
@@ -85 +85 @@
     ///
     /// The tolerance used by the algorithm to handle inexact computation.
-    typedef lemon::Tolerance<Value> Tolerance;
+    typedef lemon::Tolerance<Flow> Tolerance;
 
   };
@@ -126 +126 @@
     typedef typename Traits::CapacityMap CapacityMap;
     ///The type of the flow values.
-    typedef typename Traits::Value Value;
+    typedef typename Traits::Flow Flow;
 
     ///The type of the flow map.
@@ -152 +152 @@
     bool _local_level;
 
-    typedef typename Digraph::template NodeMap<Value> ExcessMap;
+    typedef typename Digraph::template NodeMap<Flow> ExcessMap;
     ExcessMap* _excess;
 
@@ -471 +471 @@
 
       for (NodeIt n(_graph); n != INVALID; ++n) {
-        Value excess = 0;
+        Flow excess = 0;
         for (InArcIt e(_graph, n); e != INVALID; ++e) {
           excess += (*_flow)[e];
@@ -520 +520 @@
 
       for (OutArcIt e(_graph, _source); e != INVALID; ++e) {
-        Value rem = (*_capacity)[e] - (*_flow)[e];
+        Flow rem = (*_capacity)[e] - (*_flow)[e];
         if (_tolerance.positive(rem)) {
           Node u = _graph.target(e);
@@ -532 +532 @@
       }
       for (InArcIt e(_graph, _source); e != INVALID; ++e) {
-        Value rem = (*_flow)[e];
+        Flow rem = (*_flow)[e];
         if (_tolerance.positive(rem)) {
           Node v = _graph.source(e);
@@ -565 +565 @@
 
         while (num > 0 && n != INVALID) {
-          Value excess = (*_excess)[n];
+          Flow excess = (*_excess)[n];
           int new_level = _level->maxLevel();
 
           for (OutArcIt e(_graph, n); e != INVALID; ++e) {
-            Value rem = (*_capacity)[e] - (*_flow)[e];
+            Flow rem = (*_capacity)[e] - (*_flow)[e];
             if (!_tolerance.positive(rem)) continue;
             Node v = _graph.target(e);
@@ -592 +592 @@
 
           for (InArcIt e(_graph, n); e != INVALID; ++e) {
-            Value rem = (*_flow)[e];
+            Flow rem = (*_flow)[e];
             if (!_tolerance.positive(rem)) continue;
             Node v = _graph.source(e);
@@ -638 +638 @@
         num = _node_num * 20;
         while (num > 0 && n != INVALID) {
-          Value excess = (*_excess)[n];
+          Flow excess = (*_excess)[n];
           int new_level = _level->maxLevel();
 
           for (OutArcIt e(_graph, n); e != INVALID; ++e) {
-            Value rem = (*_capacity)[e] - (*_flow)[e];
+            Flow rem = (*_capacity)[e] - (*_flow)[e];
             if (!_tolerance.positive(rem)) continue;
             Node v = _graph.target(e);
@@ -665 +665 @@
 
           for (InArcIt e(_graph, n); e != INVALID; ++e) {
-            Value rem = (*_flow)[e];
+            Flow rem = (*_flow)[e];
             if (!_tolerance.positive(rem)) continue;
             Node v = _graph.source(e);
@@ -779 +779 @@
       Node n;
       while ((n = _level->highestActive()) != INVALID) {
-        Value excess = (*_excess)[n];
+        Flow excess = (*_excess)[n];
         int level = _level->highestActiveLevel();
         int new_level = _level->maxLevel();
 
         for (OutArcIt e(_graph, n); e != INVALID; ++e) {
-          Value rem = (*_capacity)[e] - (*_flow)[e];
+          Flow rem = (*_capacity)[e] - (*_flow)[e];
           if (!_tolerance.positive(rem)) continue;
           Node v = _graph.target(e);
@@ -807 +807 @@
 
         for (InArcIt e(_graph, n); e != INVALID; ++e) {
-          Value rem = (*_flow)[e];
+          Flow rem = (*_flow)[e];
           if (!_tolerance.positive(rem)) continue;
           Node v = _graph.source(e);
@@ -898 +898 @@
     /// \pre Either \ref run() or \ref init() must be called before
     /// using this function.
-    Value flowValue() const {
+    Flow flowValue() const {
       return (*_excess)[_target];
     }
@@ -909 +909 @@
     /// \pre Either \ref run() or \ref init() must be called before
     /// using this function.
-    Value flow(const Arc& arc) const {
+    Flow flow(const Arc& arc) const {
       return (*_flow)[arc];
     }

lemon/preflow.h

@@ -33 +33 @@
   /// Default traits class of Preflow class.
   /// \tparam GR Digraph type.
-  /// \tparam CM Capacity map type.
-  template <typename GR, typename CM>
+  /// \tparam CAP Capacity map type.
+  template <typename GR, typename CAP>
   struct PreflowDefaultTraits {
 
@@ -44 +44 @@
     /// The type of the map that stores the arc capacities.
     /// It must meet the \ref concepts::ReadMap "ReadMap" concept.
-    typedef CM CapacityMap;
+    typedef CAP CapacityMap;
 
     /// \brief The type of the flow values.
@@ -95 +95 @@
   ///
   /// This class provides an implementation of Goldberg-Tarjan's \e preflow
-  /// \e push-relabel algorithm producing a flow of maximum value in a
-  /// digraph. The preflow algorithms are the fastest known maximum
+  /// \e push-relabel algorithm producing a \ref max_flow
+  /// "flow of maximum value" in a digraph.
+  /// The preflow algorithms are the fastest known maximum
   /// flow algorithms. The current implementation use a mixture of the
   /// \e "highest label" and the \e "bound decrease" heuristics.
@@ -106 +107 @@
   ///
   /// \tparam GR The type of the digraph the algorithm runs on.
-  /// \tparam CM The type of the capacity map. The default map
+  /// \tparam CAP The type of the capacity map. The default map
   /// type is \ref concepts::Digraph::ArcMap "GR::ArcMap<int>".
 #ifdef DOXYGEN
-  template <typename GR, typename CM, typename TR>
+  template <typename GR, typename CAP, typename TR>
 #else
   template <typename GR,
-            typename CM = typename GR::template ArcMap<int>,
-            typename TR = PreflowDefaultTraits<GR, CM> >
+            typename CAP = typename GR::template ArcMap<int>,
+            typename TR = PreflowDefaultTraits<GR, CAP> >
 #endif
   class Preflow {
@@ -195 +196 @@
     ///@{
 
-    template <typename _FlowMap>
+    template <typename T>
     struct SetFlowMapTraits : public Traits {
-      typedef _FlowMap FlowMap;
+      typedef T FlowMap;
       static FlowMap *createFlowMap(const Digraph&) {
         LEMON_ASSERT(false, "FlowMap is not initialized");
@@ -209 +210 @@
     /// \ref named-templ-param "Named parameter" for setting FlowMap
     /// type.
-    template <typename _FlowMap>
+    template <typename T>
     struct SetFlowMap
-      : public Preflow<Digraph, CapacityMap, SetFlowMapTraits<_FlowMap> > {
+      : public Preflow<Digraph, CapacityMap, SetFlowMapTraits<T> > {
       typedef Preflow<Digraph, CapacityMap,
-                      SetFlowMapTraits<_FlowMap> > Create;
+                      SetFlowMapTraits<T> > Create;
     };
 
-    template <typename _Elevator>
+    template <typename T>
     struct SetElevatorTraits : public Traits {
-      typedef _Elevator Elevator;
+      typedef T Elevator;
       static Elevator *createElevator(const Digraph&, int) {
         LEMON_ASSERT(false, "Elevator is not initialized");
@@ -234 +235 @@
     /// \ref run() or \ref init().
     /// \sa SetStandardElevator
-    template <typename _Elevator>
+    template <typename T>
     struct SetElevator
-      : public Preflow<Digraph, CapacityMap, SetElevatorTraits<_Elevator> > {
+      : public Preflow<Digraph, CapacityMap, SetElevatorTraits<T> > {
       typedef Preflow<Digraph, CapacityMap,
-                      SetElevatorTraits<_Elevator> > Create;
+                      SetElevatorTraits<T> > Create;
     };
 
-    template <typename _Elevator>
+    template <typename T>
     struct SetStandardElevatorTraits : public Traits {
-      typedef _Elevator Elevator;
+      typedef T Elevator;
       static Elevator *createElevator(const Digraph& digraph, int max_level) {
         return new Elevator(digraph, max_level);
@@ -261 +262 @@
     /// before calling \ref run() or \ref init().
     /// \sa SetElevator
-    template <typename _Elevator>
+    template <typename T>
     struct SetStandardElevator
       : public Preflow<Digraph, CapacityMap,
-                       SetStandardElevatorTraits<_Elevator> > {
+                       SetStandardElevatorTraits<T> > {
       typedef Preflow<Digraph, CapacityMap,
-                      SetStandardElevatorTraits<_Elevator> > Create;
+                      SetStandardElevatorTraits<T> > Create;
     };
 
@@ -404 +405 @@
       _phase = true;
       for (NodeIt n(_graph); n != INVALID; ++n) {
-        _excess->set(n, 0);
+        (*_excess)[n] = 0;
       }
 
@@ -417 +418 @@
 
       std::vector<Node> queue;
-      reached.set(_source, true);
+      reached[_source] = true;
 
       queue.push_back(_target);
-      reached.set(_target, true);
+      reached[_target] = true;
       while (!queue.empty()) {
         _level->initNewLevel();
@@ -429 +430 @@
             Node u = _graph.source(e);
             if (!reached[u] && _tolerance.positive((*_capacity)[e])) {
-              reached.set(u, true);
+              reached[u] = true;
               _level->initAddItem(u);
               nqueue.push_back(u);
@@ -444 +445 @@
           if ((*_level)[u] == _level->maxLevel()) continue;
           _flow->set(e, (*_capacity)[e]);
-          _excess->set(u, (*_excess)[u] + (*_capacity)[e]);
+          (*_excess)[u] += (*_capacity)[e];
           if (u != _target && !_level->active(u)) {
             _level->activate(u);
@@ -478 +479 @@
         }
         if (excess < 0 && n != _source) return false;
-        _excess->set(n, excess);
+        (*_excess)[n] = excess;
       }
 
@@ -487 +488 @@
 
       std::vector<Node> queue;
-      reached.set(_source, true);
+      reached[_source] = true;
 
       queue.push_back(_target);
-      reached.set(_target, true);
+      reached[_target] = true;
       while (!queue.empty()) {
         _level->initNewLevel();
@@ -500 +501 @@
             if (!reached[u] &&
                 _tolerance.positive((*_capacity)[e] - (*_flow)[e])) {
-              reached.set(u, true);
+              reached[u] = true;
               _level->initAddItem(u);
               nqueue.push_back(u);
@@ -508 +509 @@
             Node v = _graph.target(e);
             if (!reached[v] && _tolerance.positive((*_flow)[e])) {
-              reached.set(v, true);
+              reached[v] = true;
               _level->initAddItem(v);
               nqueue.push_back(v);
@@ -524 +525 @@
           if ((*_level)[u] == _level->maxLevel()) continue;
           _flow->set(e, (*_capacity)[e]);
-          _excess->set(u, (*_excess)[u] + rem);
+          (*_excess)[u] += rem;
           if (u != _target && !_level->active(u)) {
             _level->activate(u);
@@ -536 +537 @@
           if ((*_level)[v] == _level->maxLevel()) continue;
           _flow->set(e, 0);
-          _excess->set(v, (*_excess)[v] + rem);
+          (*_excess)[v] += rem;
           if (v != _target && !_level->active(v)) {
             _level->activate(v);
@@ -577 +578 @@
               if (!_tolerance.less(rem, excess)) {
                 _flow->set(e, (*_flow)[e] + excess);
-                _excess->set(v, (*_excess)[v] + excess);
+                (*_excess)[v] += excess;
                 excess = 0;
                 goto no_more_push_1;
               } else {
                 excess -= rem;
-                _excess->set(v, (*_excess)[v] + rem);
+                (*_excess)[v] += rem;
                 _flow->set(e, (*_capacity)[e]);
               }
@@ -600 +601 @@
               if (!_tolerance.less(rem, excess)) {
                 _flow->set(e, (*_flow)[e] - excess);
-                _excess->set(v, (*_excess)[v] + excess);
+                (*_excess)[v] += excess;
                 excess = 0;
                 goto no_more_push_1;
               } else {
                 excess -= rem;
-                _excess->set(v, (*_excess)[v] + rem);
+                (*_excess)[v] += rem;
                 _flow->set(e, 0);
               }
@@ -615 +616 @@
         no_more_push_1:
 
-          _excess->set(n, excess);
+          (*_excess)[n] = excess;
 
           if (excess != 0) {
@@ -650 +651 @@
               if (!_tolerance.less(rem, excess)) {
                 _flow->set(e, (*_flow)[e] + excess);
-                _excess->set(v, (*_excess)[v] + excess);
+                (*_excess)[v] += excess;
                 excess = 0;
                 goto no_more_push_2;
               } else {
                 excess -= rem;
-                _excess->set(v, (*_excess)[v] + rem);
+                (*_excess)[v] += rem;
                 _flow->set(e, (*_capacity)[e]);
               }
@@ -673 +674 @@
               if (!_tolerance.less(rem, excess)) {
                 _flow->set(e, (*_flow)[e] - excess);
-                _excess->set(v, (*_excess)[v] + excess);
+                (*_excess)[v] += excess;
                 excess = 0;
                 goto no_more_push_2;
               } else {
                 excess -= rem;
-                _excess->set(v, (*_excess)[v] + rem);
+                (*_excess)[v] += rem;
                 _flow->set(e, 0);
               }
@@ -688 +689 @@
         no_more_push_2:
 
-          _excess->set(n, excess);
+          (*_excess)[n] = excess;
 
           if (excess != 0) {
@@ -731 +732 @@
       typename Digraph::template NodeMap<bool> reached(_graph);
       for (NodeIt n(_graph); n != INVALID; ++n) {
-        reached.set(n, (*_level)[n] < _level->maxLevel());
+        reached[n] = (*_level)[n] < _level->maxLevel();
       }
 
@@ -739 +740 @@
       std::vector<Node> queue;
       queue.push_back(_source);
-      reached.set(_source, true);
+      reached[_source] = true;
 
       while (!queue.empty()) {
@@ -749 +750 @@
             Node v = _graph.target(e);
             if (!reached[v] && _tolerance.positive((*_flow)[e])) {
-              reached.set(v, true);
+              reached[v] = true;
               _level->initAddItem(v);
               nqueue.push_back(v);
@@ -758 +759 @@
             if (!reached[u] &&
                 _tolerance.positive((*_capacity)[e] - (*_flow)[e])) {
-              reached.set(u, true);
+              reached[u] = true;
               _level->initAddItem(u);
               nqueue.push_back(u);
@@ -792 +793 @@
             if (!_tolerance.less(rem, excess)) {
               _flow->set(e, (*_flow)[e] + excess);
-              _excess->set(v, (*_excess)[v] + excess);
+              (*_excess)[v] += excess;
               excess = 0;
               goto no_more_push;
             } else {
               excess -= rem;
-              _excess->set(v, (*_excess)[v] + rem);
+              (*_excess)[v] += rem;
               _flow->set(e, (*_capacity)[e]);
             }
@@ -815 +816 @@
             if (!_tolerance.less(rem, excess)) {
               _flow->set(e, (*_flow)[e] - excess);
-              _excess->set(v, (*_excess)[v] + excess);
+              (*_excess)[v] += excess;
               excess = 0;
               goto no_more_push;
             } else {
               excess -= rem;
-              _excess->set(v, (*_excess)[v] + rem);
+              (*_excess)[v] += rem;
               _flow->set(e, 0);
             }
@@ -830 +831 @@
       no_more_push:
 
-        _excess->set(n, excess);
+        (*_excess)[n] = excess;
 
         if (excess != 0) {
@@ -947 +948 @@
     ///
     /// \note This function calls \ref minCut() for each node, so it runs in
-    /// \f$O(n)\f$ time.
+    /// O(n) time.
     ///
     /// \pre Either \ref run() or \ref init() must be called before