Changeset 1270:dceba191c00d in lemon for lemon/edmonds_karp.h

Timestamp:

08/09/13 11:28:17 (11 years ago)

Author:

Alpar Juttner <alpar@…>

Branch:

default

Children:

1271:fb1c7da561ce, 1381:e0ccc1f0268f

Phase:

public

Message:

Apply unify-sources.sh to the source tree

File:

• lemon/edmonds_karp.h (modified) (28 diffs)

lemon/edmonds_karp.h

@@ -3 +3 @@
  * This file is a part of LEMON, a generic C++ optimization library.
  *
- * Copyright (C) 2003-2010
+ * Copyright (C) 2003-2013
  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
  * (Egervary Research Group on Combinatorial Optimization, EGRES).
@@ -37 +37 @@
   struct EdmondsKarpDefaultTraits {
 
-    /// \brief The digraph type the algorithm runs on. 
+    /// \brief The digraph type the algorithm runs on.
     typedef GR Digraph;
 
@@ -61 +61 @@
     /// \brief Instantiates a FlowMap.
     ///
-    /// This function instantiates a \ref FlowMap. 
+    /// This function instantiates a \ref FlowMap.
     /// \param digraph The digraph for which we would like to define
     /// the flow map.
@@ -96 +96 @@
   /// \tparam GR The type of the digraph the algorithm runs on.
   /// \tparam CAP The type of the capacity map. The default map
-  /// type is \ref concepts::Digraph::ArcMap "GR::ArcMap<int>". 
+  /// type is \ref concepts::Digraph::ArcMap "GR::ArcMap<int>".
   /// \tparam TR The traits class that defines various types used by the
   /// algorithm. By default, it is \ref EdmondsKarpDefaultTraits
@@ -105 +105 @@
 #ifdef DOXYGEN
   template <typename GR, typename CAP, typename TR>
-#else 
+#else
   template <typename GR,
-            typename CAP = typename GR::template ArcMap<int>,
+            typename CAP = typename GR::template ArcMap<int>,
             typename TR = EdmondsKarpDefaultTraits<GR, CAP> >
 #endif
@@ -121 +121 @@
     typedef typename Traits::CapacityMap CapacityMap;
     /// The type of the flow values.
-    typedef typename Traits::Value Value; 
+    typedef typename Traits::Value Value;
 
     /// The type of the flow map.
@@ -132 +132 @@
     TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);
     typedef typename Digraph::template NodeMap<Arc> PredMap;
-    
+
     const Digraph& _graph;
     const CapacityMap* _capacity;
@@ -143 +143 @@
     PredMap* _pred;
     std::vector<Node> _queue;
-    
+
     Tolerance _tolerance;
     Value _flow_value;
@@ -149 +149 @@
     void createStructures() {
       if (!_flow) {
-        _flow = Traits::createFlowMap(_graph);
-        _local_flow = true;
+        _flow = Traits::createFlowMap(_graph);
+        _local_flow = true;
       }
       if (!_pred) {
-        _pred = new PredMap(_graph);
+        _pred = new PredMap(_graph);
       }
       _queue.resize(countNodes(_graph));
@@ -160 +160 @@
     void destroyStructures() {
       if (_local_flow) {
-        delete _flow;
+        delete _flow;
       }
       if (_pred) {
-        delete _pred;
-      }
-    }
-    
+        delete _pred;
+      }
+    }
+
   public:
 
@@ -179 +179 @@
       typedef T FlowMap;
       static FlowMap *createFlowMap(const Digraph&) {
-        LEMON_ASSERT(false, "FlowMap is not initialized");
+        LEMON_ASSERT(false, "FlowMap is not initialized");
         return 0;
       }
@@ -190 +190 @@
     /// type
     template <typename T>
-    struct SetFlowMap 
+    struct SetFlowMap
       : public EdmondsKarp<Digraph, CapacityMap, SetFlowMapTraits<T> > {
       typedef EdmondsKarp<Digraph, CapacityMap, SetFlowMapTraits<T> > Create;
@@ -198 +198 @@
 
   protected:
-    
+
     EdmondsKarp() {}
 
@@ -205 +205 @@
     /// \brief The constructor of the class.
     ///
-    /// The constructor of the class. 
-    /// \param digraph The digraph the algorithm runs on. 
-    /// \param capacity The capacity of the arcs. 
+    /// The constructor of the class.
+    /// \param digraph The digraph the algorithm runs on.
+    /// \param capacity The capacity of the arcs.
     /// \param source The source node.
     /// \param target The target node.
     EdmondsKarp(const Digraph& digraph, const CapacityMap& capacity,
-                Node source, Node target)
+                Node source, Node target)
       : _graph(digraph), _capacity(&capacity), _source(source), _target(target),
-        _flow(0), _local_flow(false), _pred(0), _tolerance(), _flow_value()
+        _flow(0), _local_flow(false), _pred(0), _tolerance(), _flow_value()
     {
       LEMON_ASSERT(_source != _target,
@@ -245 +245 @@
     EdmondsKarp& flowMap(FlowMap& map) {
       if (_local_flow) {
-        delete _flow;
-        _local_flow = false;
+        delete _flow;
+        _local_flow = false;
       }
       _flow = &map;
@@ -277 +277 @@
       _tolerance = tolerance;
       return *this;
-    } 
+    }
 
     /// \brief Returns a const reference to the tolerance.
@@ -285 +285 @@
     const Tolerance& tolerance() const {
       return _tolerance;
-    } 
+    }
 
     /// \name Execution control
@@ -292 +292 @@
     /// you have to call one of the \ref init() functions first, then
     /// \ref start() or multiple times the \ref augment() function.
-    
+
     ///@{
 
@@ -306 +306 @@
       _flow_value = 0;
     }
-    
+
     /// \brief Initializes the algorithm using the given flow map.
     ///
@@ -318 +318 @@
       createStructures();
       for (ArcIt e(_graph); e != INVALID; ++e) {
-        _flow->set(e, flowMap[e]);
+        _flow->set(e, flowMap[e]);
       }
       _flow_value = 0;
@@ -335 +335 @@
     /// contain a feasible flow, i.e. at each node excluding the source
     /// and the target, the incoming flow should be equal to the
-    /// outgoing flow. 
+    /// outgoing flow.
     /// \return \c false when the given \c flowMap does not contain a
     /// feasible flow.
@@ -342 +342 @@
       createStructures();
       for (ArcIt e(_graph); e != INVALID; ++e) {
-        _flow->set(e, flowMap[e]);
+        _flow->set(e, flowMap[e]);
       }
       for (NodeIt it(_graph); it != INVALID; ++it) {
@@ -373 +373 @@
 
     /// \brief Augments the solution along a shortest path.
-    /// 
+    ///
     /// Augments the solution along a shortest path. This function searches a
     /// shortest path between the source and the target
@@ -384 +384 @@
     bool augment() {
       for (NodeIt n(_graph); n != INVALID; ++n) {
-        _pred->set(n, INVALID);
-      }
-      
+        _pred->set(n, INVALID);
+      }
+
       int first = 0, last = 1;
-      
+
       _queue[0] = _source;
       _pred->set(_source, OutArcIt(_graph, _source));
 
       while (first != last && (*_pred)[_target] == INVALID) {
-        Node n = _queue[first++];
-        
-        for (OutArcIt e(_graph, n); e != INVALID; ++e) {
-          Value rem = (*_capacity)[e] - (*_flow)[e];
-          Node t = _graph.target(e);
-          if (_tolerance.positive(rem) && (*_pred)[t] == INVALID) {
-            _pred->set(t, e);
-            _queue[last++] = t;
-          }
-        }
-        for (InArcIt e(_graph, n); e != INVALID; ++e) {
-          Value rem = (*_flow)[e];
-          Node t = _graph.source(e);
-          if (_tolerance.positive(rem) && (*_pred)[t] == INVALID) {
-            _pred->set(t, e);
-            _queue[last++] = t;
-          }
-        }
+        Node n = _queue[first++];
+
+        for (OutArcIt e(_graph, n); e != INVALID; ++e) {
+          Value rem = (*_capacity)[e] - (*_flow)[e];
+          Node t = _graph.target(e);
+          if (_tolerance.positive(rem) && (*_pred)[t] == INVALID) {
+            _pred->set(t, e);
+            _queue[last++] = t;
+          }
+        }
+        for (InArcIt e(_graph, n); e != INVALID; ++e) {
+          Value rem = (*_flow)[e];
+          Node t = _graph.source(e);
+          if (_tolerance.positive(rem) && (*_pred)[t] == INVALID) {
+            _pred->set(t, e);
+            _queue[last++] = t;
+          }
+        }
       }
 
       if ((*_pred)[_target] != INVALID) {
-        Node n = _target;
-        Arc e = (*_pred)[n];
-
-        Value prem = (*_capacity)[e] - (*_flow)[e];
-        n = _graph.source(e);
-        while (n != _source) {
-          e = (*_pred)[n];
-          if (_graph.target(e) == n) {
-            Value rem = (*_capacity)[e] - (*_flow)[e];
-            if (rem < prem) prem = rem;
-            n = _graph.source(e);
-          } else {
-            Value rem = (*_flow)[e];
-            if (rem < prem) prem = rem;
-            n = _graph.target(e);   
-          } 
-        }
-
-        n = _target;
-        e = (*_pred)[n];
-
-        _flow->set(e, (*_flow)[e] + prem);
-        n = _graph.source(e);
-        while (n != _source) {
-          e = (*_pred)[n];
-          if (_graph.target(e) == n) {
-            _flow->set(e, (*_flow)[e] + prem);
-            n = _graph.source(e);
-          } else {
-            _flow->set(e, (*_flow)[e] - prem);
-            n = _graph.target(e);   
-          } 
-        }
-
-        _flow_value += prem;    
-        return true;
+        Node n = _target;
+        Arc e = (*_pred)[n];
+
+        Value prem = (*_capacity)[e] - (*_flow)[e];
+        n = _graph.source(e);
+        while (n != _source) {
+          e = (*_pred)[n];
+          if (_graph.target(e) == n) {
+            Value rem = (*_capacity)[e] - (*_flow)[e];
+            if (rem < prem) prem = rem;
+            n = _graph.source(e);
+          } else {
+            Value rem = (*_flow)[e];
+            if (rem < prem) prem = rem;
+            n = _graph.target(e);
+          }
+        }
+
+        n = _target;
+        e = (*_pred)[n];
+
+        _flow->set(e, (*_flow)[e] + prem);
+        n = _graph.source(e);
+        while (n != _source) {
+          e = (*_pred)[n];
+          if (_graph.target(e) == n) {
+            _flow->set(e, (*_flow)[e] + prem);
+            n = _graph.source(e);
+          } else {
+            _flow->set(e, (*_flow)[e] - prem);
+            n = _graph.target(e);
+          }
+        }
+
+        _flow_value += prem;
+        return true;
       } else {
-        return false;
+        return false;
       }
     }
@@ -458 +458 @@
     ///
     /// Executes the algorithm by performing augmenting phases until the
-    /// optimal solution is reached. 
+    /// optimal solution is reached.
     /// \pre One of the \ref init() functions must be called before
     /// using this function.
@@ -466 +466 @@
 
     /// \brief Runs the algorithm.
-    /// 
+    ///
     /// Runs the Edmonds-Karp algorithm.
     /// \note ek.run() is just a shortcut of the following code.
-    ///\code 
+    ///\code
     /// ek.init();
     /// ek.start();
@@ -484 +484 @@
     /// functions.\n
     /// Either \ref run() or \ref start() should be called before using them.
-    
+
     ///@{
 
@@ -543 +543 @@
     void minCutMap(CutMap& cutMap) const {
       for (NodeIt n(_graph); n != INVALID; ++n) {
-        cutMap.set(n, (*_pred)[n] != INVALID);
+        cutMap.set(n, (*_pred)[n] != INVALID);
       }
       cutMap.set(_source, true);
-    }    
+    }
 
     /// @}