Changeset 2581:054566ac0934 in lemon-0.x for lemon/capacity_scaling.h

Timestamp:

02/28/08 03:54:27 (16 years ago)

Author:

Peter Kovacs

Branch:

default

Phase:

public

Convert:

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

Message:

Query improvements in the min cost flow algorithms.

• External flow and potential maps can be used.
• New query functions: flow() and potential().
• CycleCanceling? also provides dual solution (node potentials).
• Doc improvements.

File:

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

lemon/capacity_scaling.h

@@ -51 +51 @@
   /// - Edge capacities and costs should be \e non-negative \e integers.
   /// - Supply values should be \e signed \e integers.
-  /// - \c LowerMap::Value must be convertible to \c CapacityMap::Value.
-  /// - \c CapacityMap::Value and \c SupplyMap::Value must be
-  ///   convertible to each other.
-  /// - All value types must be convertible to \c CostMap::Value, which
-  ///   must be signed type.
+  /// - The value types of the maps should be convertible to each other.
+  /// - \c CostMap::Value must be signed type.
   ///
   /// \author Peter Kovacs
@@ -121 +118 @@
     public:
 
-      /// The constructor of the class.
+      /// Constructor.
       ResidualDijkstra( const Graph &graph,
                         const FlowMap &flow,
@@ -222 +219 @@
 
     // Edge map of the current flow
-    FlowMap _flow;
+    FlowMap *_flow;
+    bool _local_flow;
     // Node map of the current potentials
-    PotentialMap _potential;
+    PotentialMap *_potential;
+    bool _local_potential;
 
     // The residual capacity map
@@ -244 +243 @@
     // Implementation of the Dijkstra algorithm for finding augmenting
     // shortest paths in the residual network
-    ResidualDijkstra _dijkstra;
-
-  public :
-
-    /// \brief General constructor of the class (with lower bounds).
-    ///
-    /// General constructor of the class (with lower bounds).
+    ResidualDijkstra *_dijkstra;
+
+  public:
+
+    /// \brief General constructor (with lower bounds).
+    ///
+    /// General constructor (with lower bounds).
     ///
     /// \param graph The directed graph the algorithm runs on.
@@ -263 +262 @@
                      const SupplyMap &supply ) :
       _graph(graph), _lower(&lower), _capacity(graph), _cost(cost),
-      _supply(graph), _flow(graph, 0), _potential(graph, 0),
-      _res_cap(graph), _excess(graph), _pred(graph),
-      _dijkstra(_graph, _flow, _res_cap, _cost, _excess, _potential, _pred)
+      _supply(graph), _flow(0), _local_flow(false),
+      _potential(0), _local_potential(false),
+      _res_cap(graph), _excess(graph), _pred(graph)
     {
       // Removing non-zero lower bounds
@@ -283 +282 @@
     }
 
-    /// \brief General constructor of the class (without lower bounds).
-    ///
-    /// General constructor of the class (without lower bounds).
+    /// \brief General constructor (without lower bounds).
+    ///
+    /// General constructor (without lower bounds).
     ///
     /// \param graph The directed graph the algorithm runs on.
@@ -296 +295 @@
                      const SupplyMap &supply ) :
       _graph(graph), _lower(NULL), _capacity(capacity), _cost(cost),
-      _supply(supply), _flow(graph, 0), _potential(graph, 0),
-      _res_cap(capacity), _excess(graph), _pred(graph),
-      _dijkstra(_graph, _flow, _res_cap, _cost, _excess, _potential, _pred)
+      _supply(supply), _flow(0), _local_flow(false),
+      _potential(0), _local_potential(false),
+      _res_cap(capacity), _excess(graph), _pred(graph)
     {
       // Checking the sum of supply values
@@ -306 +305 @@
     }
 
-    /// \brief Simple constructor of the class (with lower bounds).
-    ///
-    /// Simple constructor of the class (with lower bounds).
+    /// \brief Simple constructor (with lower bounds).
+    ///
+    /// Simple constructor (with lower bounds).
     ///
     /// \param graph The directed graph the algorithm runs on.
@@ -325 +324 @@
                      Supply flow_value ) :
       _graph(graph), _lower(&lower), _capacity(graph), _cost(cost),
-      _supply(graph), _flow(graph, 0), _potential(graph, 0),
-      _res_cap(graph), _excess(graph), _pred(graph),
-      _dijkstra(_graph, _flow, _res_cap, _cost, _excess, _potential, _pred)
+      _supply(graph), _flow(0), _local_flow(false),
+      _potential(0), _local_potential(false),
+      _res_cap(graph), _excess(graph), _pred(graph)
     {
       // Removing non-zero lower bounds
@@ -345 +344 @@
     }
 
-    /// \brief Simple constructor of the class (without lower bounds).
-    ///
-    /// Simple constructor of the class (without lower bounds).
+    /// \brief Simple constructor (without lower bounds).
+    ///
+    /// Simple constructor (without lower bounds).
     ///
     /// \param graph The directed graph the algorithm runs on.
@@ -362 +361 @@
                      Supply flow_value ) :
       _graph(graph), _lower(NULL), _capacity(capacity), _cost(cost),
-      _supply(graph, 0), _flow(graph, 0), _potential(graph, 0),
-      _res_cap(capacity), _excess(graph), _pred(graph),
-      _dijkstra(_graph, _flow, _res_cap, _cost, _excess, _potential, _pred)
+      _supply(graph, 0), _flow(0), _local_flow(false),
+      _potential(0), _local_potential(false),
+      _res_cap(capacity), _excess(graph), _pred(graph)
     {
       _supply[s] =  flow_value;
@@ -371 +370 @@
     }
 
+    /// Destructor.
+    ~CapacityScaling() {
+      if (_local_flow) delete _flow;
+      if (_local_potential) delete _potential;
+      delete _dijkstra;
+    }
+
+    /// \brief Sets the flow map.
+    ///
+    /// Sets the flow map.
+    ///
+    /// \return \c (*this)
+    CapacityScaling& flowMap(FlowMap &map) {
+      if (_local_flow) {
+        delete _flow;
+        _local_flow = false;
+      }
+      _flow = ↦
+      return *this;
+    }
+
+    /// \brief Sets the potential map.
+    ///
+    /// Sets the potential map.
+    ///
+    /// \return \c (*this)
+    CapacityScaling& potentialMap(PotentialMap &map) {
+      if (_local_potential) {
+        delete _potential;
+        _local_potential = false;
+      }
+      _potential = ↦
+      return *this;
+    }
+
+    /// \name Execution control
+    /// The only way to execute the algorithm is to call the run()
+    /// function.
+
+    /// @{
+
     /// \brief Runs the algorithm.
     ///
@@ -385 +425 @@
     }
 
+    /// @}
+
+    /// \name Query Functions
+    /// The result of the algorithm can be obtained using these
+    /// functions.
+    /// \n run() must be called before using them.
+
+    /// @{
+
     /// \brief Returns a const reference to the edge map storing the
     /// found flow.
@@ -392 +441 @@
     /// \pre \ref run() must be called before using this function.
     const FlowMap& flowMap() const {
-      return _flow;
+      return *_flow;
     }
 
@@ -403 +452 @@
     /// \pre \ref run() must be called before using this function.
     const PotentialMap& potentialMap() const {
-      return _potential;
+      return *_potential;
+    }
+
+    /// \brief Returns the flow on the edge.
+    ///
+    /// Returns the flow on the 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.
+    ///
+    /// Returns the potential of the node.
+    ///
+    /// \pre \ref run() must be called before using this function.
+    Cost potential(const Node& node) const {
+      return (*_potential)[node];
     }
 
@@ -415 +482 @@
       Cost c = 0;
       for (EdgeIt e(_graph); e != INVALID; ++e)
-        c += _flow[e] * _cost[e];
+        c += (*_flow)[e] * _cost[e];
       return c;
     }
+
+    /// @}
 
   private:
@@ -424 +493 @@
     bool init(bool scaling) {
       if (!_valid_supply) return false;
+
+      // Initializing maps
+      if (!_flow) {
+        _flow = new FlowMap(_graph);
+        _local_flow = true;
+      }
+      if (!_potential) {
+        _potential = new PotentialMap(_graph);
+        _local_potential = true;
+      }
+      for (EdgeIt e(_graph); e != INVALID; ++e) (*_flow)[e] = 0;
+      for (NodeIt n(_graph); n != INVALID; ++n) (*_potential)[n] = 0;
       _excess = _supply;
 
-      // Initilaizing delta value
+      _dijkstra = new ResidualDijkstra( _graph, *_flow, _res_cap, _cost,
+                                        _excess, *_potential, _pred );
+
+      // Initializing delta value
       if (scaling) {
         // With scaling
@@ -442 +526 @@
         _delta = 1;
       }
+
       return true;
     }
@@ -462 +547 @@
         for (EdgeIt e(_graph); e != INVALID; ++e) {
           Node u = _graph.source(e), v = _graph.target(e);
-          Cost c = _cost[e] + _potential[u] - _potential[v];
+          Cost c = _cost[e] + (*_potential)[u] - (*_potential)[v];
           if (c < 0 && _res_cap[e] >= _delta) {
             _excess[u] -= _res_cap[e];
             _excess[v] += _res_cap[e];
-            _flow[e] = _capacity[e];
+            (*_flow)[e] = _capacity[e];
             _res_cap[e] = 0;
           }
-          else if (c > 0 && _flow[e] >= _delta) {
-            _excess[u] += _flow[e];
-            _excess[v] -= _flow[e];
-            _flow[e] = 0;
+          else if (c > 0 && (*_flow)[e] >= _delta) {
+            _excess[u] += (*_flow)[e];
+            _excess[v] -= (*_flow)[e];
+            (*_flow)[e] = 0;
             _res_cap[e] = _capacity[e];
           }
@@ -502 +587 @@
           // Running Dijkstra
           s = _excess_nodes[next_node];
-          if ((t = _dijkstra.run(s, _delta)) == INVALID) {
+          if ((t = _dijkstra->run(s, _delta)) == INVALID) {
             if (_delta > 1) {
               ++next_node;
@@ -521 +606 @@
                 u = _graph.source(e);
               } else {
-                rc = _flow[e];
+                rc = (*_flow)[e];
                 u = _graph.target(e);
               }
@@ -530 +615 @@
           while ((e = _pred[u]) != INVALID) {
             if (u == _graph.target(e)) {
-              _flow[e] += d;
+              (*_flow)[e] += d;
               _res_cap[e] -= d;
               u = _graph.source(e);
             } else {
-              _flow[e] -= d;
+              (*_flow)[e] -= d;
               _res_cap[e] += d;
               u = _graph.target(e);
@@ -553 +638 @@
       if (_lower) {
         for (EdgeIt e(_graph); e != INVALID; ++e)
-          _flow[e] += (*_lower)[e];
+          (*_flow)[e] += (*_lower)[e];
       }
       return true;
@@ -573 +658 @@
         // Running Dijkstra
         s = _excess_nodes[next_node];
-        if ((t = _dijkstra.run(s, 1)) == INVALID)
+        if ((t = _dijkstra->run(s, 1)) == INVALID)
           return false;
 
@@ -586 +671 @@
             u = _graph.source(e);
           } else {
-            rc = _flow[e];
+            rc = (*_flow)[e];
             u = _graph.target(e);
           }
@@ -594 +679 @@
         while ((e = _pred[u]) != INVALID) {
           if (u == _graph.target(e)) {
-            _flow[e] += d;
+            (*_flow)[e] += d;
             _res_cap[e] -= d;
             u = _graph.source(e);
           } else {
-            _flow[e] -= d;
+            (*_flow)[e] -= d;
             _res_cap[e] += d;
             u = _graph.target(e);
@@ -610 +695 @@
       if (_lower) {
         for (EdgeIt e(_graph); e != INVALID; ++e)
-          _flow[e] += (*_lower)[e];
+          (*_flow)[e] += (*_lower)[e];
       }
       return true;