# HG changeset patch
# User kpeter
# Date 1204300672 0
# Node ID 4d3bc1d04c1d0299817d8e5ade93ab4c779824f5
# Parent  061be2e64ecac10d881623c4eb6d0337e2ee2db4
Small improvements in min cost flow files.

diff -r 061be2e64eca -r 4d3bc1d04c1d lemon/capacity_scaling.h
--- a/lemon/capacity_scaling.h	Fri Feb 29 15:55:39 2008 +0000
+++ b/lemon/capacity_scaling.h	Fri Feb 29 15:57:52 2008 +0000
@@ -25,8 +25,6 @@
 /// \brief Capacity scaling algorithm for finding a minimum cost flow.
 
 #include <vector>
-
-#include <lemon/graph_adaptor.h>
 #include <lemon/bin_heap.h>
 
 namespace lemon {
@@ -90,9 +88,6 @@
     /// distance of the nodes.
     class ResidualDijkstra
     {
-      typedef typename Graph::template NodeMap<Cost> CostNodeMap;
-      typedef typename Graph::template NodeMap<Edge> PredMap;
-
       typedef typename Graph::template NodeMap<int> HeapCrossRef;
       typedef BinHeap<Cost, HeapCrossRef> Heap;
 
@@ -109,7 +104,7 @@
       PotentialMap &_potential;
 
       // The distance map
-      CostNodeMap _dist;
+      PotentialMap _dist;
       // The pred edge map
       PredMap &_pred;
       // The processed (i.e. permanently labeled) nodes
@@ -131,7 +126,7 @@
       {}
 
       /// Runs the algorithm from the given source node.
-      Node run(Node s, Capacity delta) {
+      Node run(Node s, Capacity delta = 1) {
         HeapCrossRef heap_cross_ref(_graph, Heap::PRE_HEAP);
         Heap heap(heap_cross_ref);
         heap.push(s, 0);
@@ -454,18 +449,18 @@
       return *_potential;
     }
 
-    /// \brief Returns the flow on the edge.
+    /// \brief Returns the flow on the given edge.
     ///
-    /// Returns the flow on the edge.
+    /// Returns the flow on the given edge.
     ///
     /// \pre \ref run() must be called before using this function.
     Capacity flow(const Edge& edge) const {
       return (*_flow)[edge];
     }
 
-    /// \brief Returns the potential of the node.
+    /// \brief Returns the potential of the given node.
     ///
-    /// Returns the potential of the node.
+    /// Returns the potential of the given node.
     ///
     /// \pre \ref run() must be called before using this function.
     Cost potential(const Node& node) const {
@@ -517,7 +512,11 @@
           if ( _supply[n] > max_sup) max_sup =  _supply[n];
           if (-_supply[n] > max_dem) max_dem = -_supply[n];
         }
-        if (max_dem < max_sup) max_sup = max_dem;
+        Capacity max_cap = 0;
+        for (EdgeIt e(_graph); e != INVALID; ++e) {
+          if (_capacity[e] > max_cap) max_cap = _capacity[e];
+        }
+        max_sup = std::min(std::min(max_sup, max_dem), max_cap);
         _phase_num = 0;
         for (_delta = 1; 2 * _delta <= max_sup; _delta *= 2)
           ++_phase_num;
@@ -595,7 +594,7 @@
           }
 
           // Augmenting along a shortest path from s to t.
-          Capacity d = _excess[s] < -_excess[t] ? _excess[s] : -_excess[t];
+          Capacity d = std::min(_excess[s], -_excess[t]);
           Node u = t;
           Edge e;
           if (d > _delta) {
@@ -657,23 +656,24 @@
       {
         // Running Dijkstra
         s = _excess_nodes[next_node];
-        if ((t = _dijkstra->run(s, 1)) == INVALID)
-          return false;
+        if ((t = _dijkstra->run(s)) == INVALID) break;
 
         // Augmenting along a shortest path from s to t
-        Capacity d = _excess[s] < -_excess[t] ? _excess[s] : -_excess[t];
+        Capacity d = std::min(_excess[s], -_excess[t]);
         Node u = t;
         Edge e;
-        while ((e = _pred[u]) != INVALID) {
-          Capacity rc;
-          if (u == _graph.target(e)) {
-            rc = _res_cap[e];
-            u = _graph.source(e);
-          } else {
-            rc = (*_flow)[e];
-            u = _graph.target(e);
+        if (d > 1) {
+          while ((e = _pred[u]) != INVALID) {
+            Capacity rc;
+            if (u == _graph.target(e)) {
+              rc = _res_cap[e];
+              u = _graph.source(e);
+            } else {
+              rc = (*_flow)[e];
+              u = _graph.target(e);
+            }
+            if (rc < d) d = rc;
           }
-          if (rc < d) d = rc;
         }
         u = t;
         while ((e = _pred[u]) != INVALID) {
diff -r 061be2e64eca -r 4d3bc1d04c1d lemon/cost_scaling.h
--- a/lemon/cost_scaling.h	Fri Feb 29 15:55:39 2008 +0000
+++ b/lemon/cost_scaling.h	Fri Feb 29 15:57:52 2008 +0000
@@ -399,18 +399,18 @@
       return *_potential;
     }
 
-    /// \brief Returns the flow on the edge.
+    /// \brief Returns the flow on the given edge.
     ///
-    /// Returns the flow on the edge.
+    /// Returns the flow on the given edge.
     ///
     /// \pre \ref run() must be called before using this function.
     Capacity flow(const Edge& edge) const {
       return (*_flow)[edge];
     }
 
-    /// \brief Returns the potential of the node.
+    /// \brief Returns the potential of the given node.
     ///
-    /// Returns the potential of the node.
+    /// Returns the potential of the given node.
     ///
     /// \pre \ref run() must be called before using this function.
     Cost potential(const Node& node) const {
diff -r 061be2e64eca -r 4d3bc1d04c1d lemon/cycle_canceling.h
--- a/lemon/cycle_canceling.h	Fri Feb 29 15:55:39 2008 +0000
+++ b/lemon/cycle_canceling.h	Fri Feb 29 15:57:52 2008 +0000
@@ -355,18 +355,18 @@
       return *_potential;
     }
 
-    /// \brief Returns the flow on the edge.
+    /// \brief Returns the flow on the given edge.
     ///
-    /// Returns the flow on the edge.
+    /// Returns the flow on the given edge.
     ///
     /// \pre \ref run() must be called before using this function.
     Capacity flow(const Edge& edge) const {
       return (*_flow)[edge];
     }
 
-    /// \brief Returns the potential of the node.
+    /// \brief Returns the potential of the given node.
     ///
-    /// Returns the potential of the node.
+    /// Returns the potential of the given node.
     ///
     /// \pre \ref run() must be called before using this function.
     Cost potential(const Node& node) const {
diff -r 061be2e64eca -r 4d3bc1d04c1d lemon/min_cost_flow.h
--- a/lemon/min_cost_flow.h	Fri Feb 29 15:55:39 2008 +0000
+++ b/lemon/min_cost_flow.h	Fri Feb 29 15:57:52 2008 +0000
@@ -44,10 +44,10 @@
   ///
   /// There are four implementations for the minimum cost flow problem,
   /// which can be used exactly the same way.
-  /// - \ref CapacityScaling The capacity scaling algorithm.
-  /// - \ref CostScaling The cost scaling algorithm.
-  /// - \ref CycleCanceling A cycle-canceling algorithm.
-  /// - \ref NetworkSimplex The network simplex algorithm.
+  /// - \ref CapacityScaling
+  /// - \ref CostScaling
+  /// - \ref CycleCanceling
+  /// - \ref NetworkSimplex
   ///
   /// \tparam Graph The directed graph type the algorithm runs on.
   /// \tparam LowerMap The type of the lower bound map.
diff -r 061be2e64eca -r 4d3bc1d04c1d lemon/min_mean_cycle.h
--- a/lemon/min_mean_cycle.h	Fri Feb 29 15:55:39 2008 +0000
+++ b/lemon/min_mean_cycle.h	Fri Feb 29 15:57:52 2008 +0000
@@ -134,7 +134,8 @@
     }
 
     /// \name Execution control
-    /// The simplest way to execute the algorithm is to call run().
+    /// The simplest way to execute the algorithm is to call the run()
+    /// function.
     /// \n
     /// If you only need the minimum mean value, you may call init()
     /// and findMinMean().
@@ -237,7 +238,7 @@
     /// \name Query Functions
     /// The result of the algorithm can be obtained using these
     /// functions.
-    /// \n run() must be called before using them.
+    /// \n The algorithm should be executed before using them.
 
     /// @{
     
diff -r 061be2e64eca -r 4d3bc1d04c1d lemon/network_simplex.h
--- a/lemon/network_simplex.h	Fri Feb 29 15:55:39 2008 +0000
+++ b/lemon/network_simplex.h	Fri Feb 29 15:57:52 2008 +0000
@@ -776,18 +776,18 @@
       return *_potential_result;
     }
 
-    /// \brief Returns the flow on the edge.
+    /// \brief Returns the flow on the given edge.
     ///
-    /// Returns the flow on the edge.
+    /// Returns the flow on the given edge.
     ///
     /// \pre \ref run() must be called before using this function.
     Capacity flow(const typename Graph::Edge& edge) const {
       return (*_flow_result)[edge];
     }
 
-    /// \brief Returns the potential of the node.
+    /// \brief Returns the potential of the given node.
     ///
-    /// Returns the potential of the node.
+    /// Returns the potential of the given node.
     ///
     /// \pre \ref run() must be called before using this function.
     Cost potential(const typename Graph::Node& node) const {