Changeset 2581:054566ac0934 in lemon-0.x for lemon/network_simplex.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/network_simplex.h (modified) (17 diffs)

lemon/network_simplex.h

@@ -53 +53 @@
   /// - 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.
   ///
   /// \note \ref NetworkSimplex provides six different pivot rule
@@ -470 +467 @@
 
     // Members for handling the original graph
-    FlowMap _flow_result;
-    PotentialMap _potential_result;
+    FlowMap *_flow_result;
+    PotentialMap *_potential_result;
+    bool _local_flow;
+    bool _local_potential;
     NodeRefMap _node_ref;
     EdgeRefMap _edge_ref;
@@ -488 +487 @@
   public :
 
-    /// \brief General constructor of the class (with lower bounds).
-    ///
-    /// General constructor of the class (with lower bounds).
+    /// \brief General constructor (with lower bounds).
+    ///
+    /// General constructor (with lower bounds).
     ///
     /// \param graph The directed graph the algorithm runs on.
@@ -507 +506 @@
       _pred_edge(_graph), _thread(_graph), _forward(_graph),
       _state(_graph), _red_cost(_graph, _cost, _potential),
-      _flow_result(graph), _potential_result(graph),
+      _flow_result(0), _potential_result(0),
+      _local_flow(false), _local_potential(false),
       _node_ref(graph), _edge_ref(graph)
     {
@@ -539 +539 @@
     }
 
-    /// \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.
@@ -556 +556 @@
       _pred_edge(_graph), _thread(_graph), _forward(_graph),
       _state(_graph), _red_cost(_graph, _cost, _potential),
-      _flow_result(graph), _potential_result(graph),
+      _flow_result(0), _potential_result(0),
+      _local_flow(false), _local_potential(false),
       _node_ref(graph), _edge_ref(graph)
     {
@@ -575 +576 @@
     }
 
-    /// \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.
@@ -599 +600 @@
       _pred_edge(_graph), _thread(_graph), _forward(_graph),
       _state(_graph), _red_cost(_graph, _cost, _potential),
-      _flow_result(graph), _potential_result(graph),
+      _flow_result(0), _potential_result(0),
+      _local_flow(false), _local_potential(false),
       _node_ref(graph), _edge_ref(graph)
     {
@@ -626 +628 @@
     }
 
-    /// \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.
@@ -648 +650 @@
       _pred_edge(_graph), _thread(_graph), _forward(_graph),
       _state(_graph), _red_cost(_graph, _cost, _potential),
-      _flow_result(graph), _potential_result(graph),
+      _flow_result(0), _potential_result(0),
+      _local_flow(false), _local_potential(false),
       _node_ref(graph), _edge_ref(graph)
     {
@@ -663 +666 @@
     }
 
+    /// Destructor.
+    ~NetworkSimplex() {
+      if (_local_flow) delete _flow_result;
+      if (_local_potential) delete _potential_result;
+    }
+
+    /// \brief Sets the flow map.
+    ///
+    /// Sets the flow map.
+    ///
+    /// \return \c (*this)
+    NetworkSimplex& flowMap(FlowMap &map) {
+      if (_local_flow) {
+        delete _flow_result;
+        _local_flow = false;
+      }
+      _flow_result = ↦
+      return *this;
+    }
+
+    /// \brief Sets the potential map.
+    ///
+    /// Sets the potential map.
+    ///
+    /// \return \c (*this)
+    NetworkSimplex& potentialMap(PotentialMap &map) {
+      if (_local_potential) {
+        delete _potential_result;
+        _local_potential = false;
+      }
+      _potential_result = ↦
+      return *this;
+    }
+
+    /// \name Execution control
+    /// The only way to execute the algorithm is to call the run()
+    /// function.
+
+    /// @{
+
     /// \brief Runs the algorithm.
     ///
@@ -704 +747 @@
     }
 
+    /// @}
+
+    /// \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.
@@ -711 +763 @@
     /// \pre \ref run() must be called before using this function.
     const FlowMap& flowMap() const {
-      return _flow_result;
+      return *_flow_result;
     }
 
@@ -722 +774 @@
     /// \pre \ref run() must be called before using this function.
     const PotentialMap& potentialMap() const {
-      return _potential_result;
+      return *_potential_result;
+    }
+
+    /// \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 typename Graph::Edge& edge) const {
+      return (*_flow_result)[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 typename Graph::Node& node) const {
+      return (*_potential_result)[node];
     }
 
@@ -734 +804 @@
       Cost c = 0;
       for (typename Graph::EdgeIt e(_graph_ref); e != INVALID; ++e)
-        c += _flow_result[e] * _cost[_edge_ref[e]];
+        c += (*_flow_result)[e] * _cost[_edge_ref[e]];
       return c;
     }
+
+    /// @}
 
   private:
@@ -744 +816 @@
     bool init() {
       if (!_valid_supply) return false;
+
+      // Initializing result maps
+      if (!_flow_result) {
+        _flow_result = new FlowMap(_graph_ref);
+        _local_flow = true;
+      }
+      if (!_potential_result) {
+        _potential_result = new PotentialMap(_graph_ref);
+        _local_potential = true;
+      }
 
       // Initializing state and flow maps
@@ -1016 +1098 @@
       if (_lower) {
         for (typename Graph::EdgeIt e(_graph_ref); e != INVALID; ++e)
-          _flow_result[e] = (*_lower)[e] + _flow[_edge_ref[e]];
+          (*_flow_result)[e] = (*_lower)[e] + _flow[_edge_ref[e]];
       } else {
         for (typename Graph::EdgeIt e(_graph_ref); e != INVALID; ++e)
-          _flow_result[e] = _flow[_edge_ref[e]];
+          (*_flow_result)[e] = _flow[_edge_ref[e]];
       }
       // Copying potential values to _potential_result
       for (typename Graph::NodeIt n(_graph_ref); n != INVALID; ++n)
-        _potential_result[n] = _potential[_node_ref[n]];
+        (*_potential_result)[n] = _potential[_node_ref[n]];
 
       return true;