Changeset 2509:a8081c9cd96a in lemon-0.x for lemon/capacity_scaling.h

Timestamp:

11/14/07 07:28:08 (16 years ago)

Author:

Peter Kovacs

Branch:

default

Phase:

public

Convert:

svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@3374

Message:

Small changes in the min. cost flow classes.

File:

• lemon/capacity_scaling.h (modified) (12 diffs)

lemon/capacity_scaling.h

@@ -27 +27 @@
 
 #include <vector>
+#include <lemon/graph_adaptor.h>
 #include <lemon/dijkstra.h>
-#include <lemon/graph_adaptor.h>
 
 #define WITH_SCALING
@@ -44 +44 @@
 
   /// \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.
@@ -58 +60 @@
   /// - 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
@@ -114 +116 @@
     public:
 
-      typedef typename MapBase<ResEdge, Cost>::Value Value;
-      typedef typename MapBase<ResEdge, Cost>::Key Key;
-
       ReducedCostMap( const ResGraph &_gr,
                       const CostMap &_cost,
@@ -122 +121 @@
         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)] :
@@ -130 +129 @@
     }; //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>
     {
@@ -142 +141 @@
     public:
 
-      typedef typename MapBase<ResNode, Cost>::Value Value;
-      typedef typename MapBase<ResNode, Cost>::Key Key;
-
       void potentialMap(PotentialMap &_pot) {
         pot = &_pot;
@@ -153 +149 @@
       }
 
-      void set(const Key &n, const Value &v) {
+      void set(const ResNode &n, const Cost &v) {
         data.push_back(Pair(n, v));
       }
@@ -186 +182 @@
 
     /// \brief Map adaptor class for filtering edges with at least
-    /// \c delta residual capacity
+    /// \c delta residual capacity.
     class DeltaFilterMap : public MapBase<ResEdge, bool>
     {
@@ -196 +192 @@
     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;
       }
@@ -299 +292 @@
     /// \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.
@@ -574 +570 @@
           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;
           }
         }