# HG changeset patch
# User kpeter
# Date 1195021688 0
# Node ID a8081c9cd96a5d9ebfc2fbb403302911edcc7f0e
# Parent  c86db0f7f9174b4fc8c4b4573ccde0a4b08613c8
Small changes in the min. cost flow classes.

diff -r c86db0f7f917 -r a8081c9cd96a lemon/capacity_scaling.h
--- a/lemon/capacity_scaling.h	Thu Nov 08 14:21:28 2007 +0000
+++ b/lemon/capacity_scaling.h	Wed Nov 14 06:28:08 2007 +0000
@@ -26,8 +26,8 @@
 /// flow.
 
 #include <vector>
+#include <lemon/graph_adaptor.h>
 #include <lemon/dijkstra.h>
-#include <lemon/graph_adaptor.h>
 
 #define WITH_SCALING
 
@@ -43,10 +43,12 @@
   /// @{
 
   /// \brief Implementation of the capacity scaling version of the
-  /// successive shortest path algorithm for finding a minimum cost flow.
+  /// successive shortest path algorithm for finding a minimum cost
+  /// flow.
   ///
-  /// \ref lemon::CapacityScaling "CapacityScaling" implements a
-  /// capacity scaling algorithm for finding a minimum cost flow.
+  /// \ref lemon::CapacityScaling "CapacityScaling" implements the
+  /// capacity scaling version of the successive shortest path
+  /// algorithm for finding a minimum cost flow.
   ///
   /// \param Graph The directed graph type the algorithm runs on.
   /// \param LowerMap The type of the lower bound map.
@@ -57,7 +59,7 @@
   /// \warning
   /// - Edge capacities and costs should be nonnegative integers.
   ///	However \c CostMap::Value should be signed type.
-  /// - Supply values should be integers.
+  /// - Supply values should be signed integers.
   /// - \c LowerMap::Value must be convertible to
   ///	\c CapacityMap::Value and \c CapacityMap::Value must be
   ///	convertible to \c SupplyMap::Value.
@@ -113,15 +115,12 @@
 
     public:
 
-      typedef typename MapBase<ResEdge, Cost>::Value Value;
-      typedef typename MapBase<ResEdge, Cost>::Key Key;
-
       ReducedCostMap( const ResGraph &_gr,
 		      const CostMap &_cost,
 		      const PotentialMap &_pot ) :
 	gr(_gr), cost_map(_cost), pot_map(_pot) {}
 
-      Value operator[](const Key &e) const {
+      Cost operator[](const ResEdge &e) const {
 	return ResGraph::forward(e) ?
 	   cost_map[e] - pot_map[gr.source(e)] + pot_map[gr.target(e)] :
 	  -cost_map[e] - pot_map[gr.source(e)] + pot_map[gr.target(e)];
@@ -129,8 +128,8 @@
 
     }; //class ReducedCostMap
 
-    /// \brief Map adaptor for \ref lemon::Dijkstra "Dijkstra" class to
-    /// update node potentials.
+    /// \brief Map class for the \ref lemon::Dijkstra "Dijkstra"
+    /// algorithm to update node potentials.
     class PotentialUpdateMap : public MapBase<ResNode, Cost>
     {
     private:
@@ -141,9 +140,6 @@
 
     public:
 
-      typedef typename MapBase<ResNode, Cost>::Value Value;
-      typedef typename MapBase<ResNode, Cost>::Key Key;
-
       void potentialMap(PotentialMap &_pot) {
 	pot = &_pot;
       }
@@ -152,7 +148,7 @@
 	data.clear();
       }
 
-      void set(const Key &n, const Value &v) {
+      void set(const ResNode &n, const Cost &v) {
 	data.push_back(Pair(n, v));
       }
 
@@ -185,7 +181,7 @@
     }; //class DeficitBoolMap
 
     /// \brief Map adaptor class for filtering edges with at least
-    /// \c delta residual capacity
+    /// \c delta residual capacity.
     class DeltaFilterMap : public MapBase<ResEdge, bool>
     {
     private:
@@ -195,13 +191,10 @@
 
     public:
 
-      typedef typename MapBase<ResEdge, Cost>::Value Value;
-      typedef typename MapBase<ResEdge, Cost>::Key Key;
-
       DeltaFilterMap(const ResGraph &_gr, const Capacity &_delta) :
 	gr(_gr), delta(_delta) {}
 
-      Value operator[](const Key &e) const {
+      bool operator[](const ResEdge &e) const {
 	return gr.rescap(e) >= delta;
       }
 
@@ -298,9 +291,12 @@
 
     /// \brief The delta parameter used for capacity scaling.
     Capacity delta;
-    /// \brief Edge filter map.
+    /// \brief Edge filter map for filtering edges with at least
+    /// \c delta residual capacity.
     DeltaFilterMap delta_filter;
-    /// \brief The delta residual graph.
+    /// \brief The delta residual graph (i.e. the subgraph of the
+    /// residual graph consisting of edges with at least \c delta
+    /// residual capacity).
     DeltaResGraph dres_graph;
     /// \brief Map for identifing deficit nodes.
     DeficitBoolMap delta_deficit;
@@ -573,8 +569,8 @@
 	for (DeltaResEdgeIt e(dres_graph); e != INVALID; ++e) {
 	  if (red_cost[e] < 0) {
 	    res_graph.augment(e, r = res_graph.rescap(e));
+	    imbalance[dres_graph.source(e)] -= r;
 	    imbalance[dres_graph.target(e)] += r;
-	    imbalance[dres_graph.source(e)] -= r;
 	  }
 	}
 
diff -r c86db0f7f917 -r a8081c9cd96a lemon/cycle_canceling.h
--- a/lemon/cycle_canceling.h	Thu Nov 08 14:21:28 2007 +0000
+++ b/lemon/cycle_canceling.h	Wed Nov 14 06:28:08 2007 +0000
@@ -25,8 +25,8 @@
 /// \brief A cycle-canceling algorithm for finding a minimum cost flow.
 
 #include <vector>
+#include <lemon/graph_adaptor.h>
 #include <lemon/circulation.h>
-#include <lemon/graph_adaptor.h>
 
 /// \brief The used cycle-canceling method.
 #define LIMITED_CYCLE_CANCELING
@@ -79,7 +79,7 @@
   /// \warning
   /// - Edge capacities and costs should be nonnegative integers.
   ///	However \c CostMap::Value should be signed type.
-  /// - Supply values should be integers.
+  /// - Supply values should be signed integers.
   /// - \c LowerMap::Value must be convertible to
   ///	\c CapacityMap::Value and \c CapacityMap::Value must be
   ///	convertible to \c SupplyMap::Value.
@@ -131,12 +131,9 @@
 
     public:
 
-      typedef typename MapBase<ResEdge, Cost>::Value Value;
-      typedef typename MapBase<ResEdge, Cost>::Key Key;
-
       ResCostMap(const CostMap &_cost) : cost_map(_cost) {}
 
-      Value operator[](const Key &e) const {
+      Cost operator[](const ResEdge &e) const {
 	return ResGraph::forward(e) ? cost_map[e] : -cost_map[e];
       }
 
diff -r c86db0f7f917 -r a8081c9cd96a lemon/min_cost_flow.h
--- a/lemon/min_cost_flow.h	Thu Nov 08 14:21:28 2007 +0000
+++ b/lemon/min_cost_flow.h	Wed Nov 14 06:28:08 2007 +0000
@@ -56,7 +56,7 @@
   /// \warning
   /// - Edge capacities and costs should be nonnegative integers.
   ///	However \c CostMap::Value should be signed type.
-  /// - Supply values should be integers.
+  /// - Supply values should be signed integers.
   /// - \c LowerMap::Value must be convertible to
   ///	\c CapacityMap::Value and \c CapacityMap::Value must be
   ///	convertible to \c SupplyMap::Value.
diff -r c86db0f7f917 -r a8081c9cd96a lemon/min_mean_cycle.h
--- a/lemon/min_mean_cycle.h	Thu Nov 08 14:21:28 2007 +0000
+++ b/lemon/min_mean_cycle.h	Wed Nov 14 06:28:08 2007 +0000
@@ -22,8 +22,9 @@
 /// \ingroup min_cost_flow
 ///
 /// \file
-/// \brief Karp algorithm for finding a minimum mean cycle.
+/// \brief Karp's algorithm for finding a minimum mean (directed) cycle.
 
+#include <vector>
 #include <lemon/graph_utils.h>
 #include <lemon/topology.h>
 #include <lemon/path.h>
@@ -63,7 +64,7 @@
 
   protected:
 
-    /// \brief Data sturcture for path data.
+    /// \brief Data structure for path data.
     struct PathData
     {
       bool found;
@@ -150,7 +151,7 @@
       }
       // Creating vectors for all nodes
       int n = nodes.size();
-      for (int i = 0; i < nodes.size(); ++i) {
+      for (int i = 0; i < n; ++i) {
 	dmap[nodes[i]].resize(n + 1);
       }
     }
diff -r c86db0f7f917 -r a8081c9cd96a lemon/network_simplex.h
--- a/lemon/network_simplex.h	Thu Nov 08 14:21:28 2007 +0000
+++ b/lemon/network_simplex.h	Wed Nov 14 06:28:08 2007 +0000
@@ -26,8 +26,9 @@
 /// flow.
 
 #include <limits>
+#include <lemon/graph_adaptor.h>
+#include <lemon/graph_utils.h>
 #include <lemon/smart_graph.h>
-#include <lemon/graph_utils.h>
 
 /// \brief The pivot rule used in the algorithm.
 //#define FIRST_ELIGIBLE_PIVOT
@@ -85,7 +86,7 @@
   /// \warning
   /// - Edge capacities and costs should be nonnegative integers.
   ///	However \c CostMap::Value should be signed type.
-  /// - Supply values should be integers.
+  /// - Supply values should be signed integers.
   /// - \c LowerMap::Value must be convertible to
   ///	\c CapacityMap::Value and \c CapacityMap::Value must be
   ///	convertible to \c SupplyMap::Value.
@@ -148,15 +149,12 @@
 
     public:
 
-      typedef typename MapBase<Edge, Cost>::Value Value;
-      typedef typename MapBase<Edge, Cost>::Key Key;
-
       ReducedCostMap( const SGraph &_gr,
 		      const SCostMap &_cm,
 		      const SPotentialMap &_pm ) :
 	gr(_gr), cost_map(_cm), pot_map(_pm) {}
 
-      Value operator[](const Key &e) const {
+      Cost operator[](const Edge &e) const {
 	return cost_map[e] - pot_map[gr.source(e)] + pot_map[gr.target(e)];
       }