Changeset 688:756a5ec551c8 in lemon for lemon/network_simplex.h

Timestamp:

04/29/09 14:25:51 (16 years ago)

Author:

Peter Kovacs <kpeter@…>

Branch:

default

Phase:

public

Message:

Rename Flow to Value in the flow algorithms (#266)

We agreed that using Flow for the value type is misleading, since
a flow should be rather a function on the arcs, not a single value.

This patch reverts the changes of [dacc2cee2b4c] for Preflow and
Circulation.

File:

• lemon/network_simplex.h (modified) (20 diffs)

lemon/network_simplex.h

@@ -57 +57 @@
   ///
   /// \tparam GR The digraph type the algorithm runs on.
-  /// \tparam F The value type used for flow amounts, capacity bounds
+  /// \tparam V The value type used for flow amounts, capacity bounds
   /// and supply values in the algorithm. By default it is \c int.
   /// \tparam C The value type used for costs and potentials in the
-  /// algorithm. By default it is the same as \c F.
+  /// algorithm. By default it is the same as \c V.
   ///
   /// \warning Both value types must be signed and all input data must
@@ -68 +68 @@
   /// implementations, from which the most efficient one is used
   /// by default. For more information see \ref PivotRule.
-  template <typename GR, typename F = int, typename C = F>
+  template <typename GR, typename V = int, typename C = V>
   class NetworkSimplex
   {
@@ -74 +74 @@
 
     /// The flow type of the algorithm
-    typedef F Flow;
+    typedef V Value;
     /// The cost type of the algorithm
     typedef C Cost;
 #ifdef DOXYGEN
     /// The type of the flow map
-    typedef GR::ArcMap<Flow> FlowMap;
+    typedef GR::ArcMap<Value> FlowMap;
     /// The type of the potential map
     typedef GR::NodeMap<Cost> PotentialMap;
 #else
     /// The type of the flow map
-    typedef typename GR::template ArcMap<Flow> FlowMap;
+    typedef typename GR::template ArcMap<Value> FlowMap;
     /// The type of the potential map
     typedef typename GR::template NodeMap<Cost> PotentialMap;
@@ -207 +207 @@
     TEMPLATE_DIGRAPH_TYPEDEFS(GR);
 
-    typedef typename GR::template ArcMap<Flow> FlowArcMap;
+    typedef typename GR::template ArcMap<Value> ValueArcMap;
     typedef typename GR::template ArcMap<Cost> CostArcMap;
-    typedef typename GR::template NodeMap<Flow> FlowNodeMap;
+    typedef typename GR::template NodeMap<Value> ValueNodeMap;
 
     typedef std::vector<Arc> ArcVector;
@@ -215 +215 @@
     typedef std::vector<int> IntVector;
     typedef std::vector<bool> BoolVector;
-    typedef std::vector<Flow> FlowVector;
+    typedef std::vector<Value> FlowVector;
     typedef std::vector<Cost> CostVector;
 
@@ -233 +233 @@
 
     // Parameters of the problem
-    FlowArcMap *_plower;
-    FlowArcMap *_pupper;
+    ValueArcMap *_plower;
+    ValueArcMap *_pupper;
     CostArcMap *_pcost;
-    FlowNodeMap *_psupply;
+    ValueNodeMap *_psupply;
     bool _pstsup;
     Node _psource, _ptarget;
-    Flow _pstflow;
+    Value _pstflow;
     SupplyType _stype;
     
-    Flow _sum_supply;
+    Value _sum_supply;
 
     // Result maps
@@ -279 +279 @@
     int first, second, right, last;
     int stem, par_stem, new_stem;
-    Flow delta;
+    Value delta;
 
   public:
@@ -286 +286 @@
     ///
     /// Constant for infinite upper bounds (capacities).
-    /// It is \c std::numeric_limits<Flow>::infinity() if available,
-    /// \c std::numeric_limits<Flow>::max() otherwise.
-    const Flow INF;
+    /// It is \c std::numeric_limits<Value>::infinity() if available,
+    /// \c std::numeric_limits<Value>::max() otherwise.
+    const Value INF;
 
   private:
@@ -696 +696 @@
       _local_flow(false), _local_potential(false),
       _node_id(graph),
-      INF(std::numeric_limits<Flow>::has_infinity ?
-          std::numeric_limits<Flow>::infinity() :
-          std::numeric_limits<Flow>::max())
+      INF(std::numeric_limits<Value>::has_infinity ?
+          std::numeric_limits<Value>::infinity() :
+          std::numeric_limits<Value>::max())
     {
       // Check the value types
-      LEMON_ASSERT(std::numeric_limits<Flow>::is_signed,
+      LEMON_ASSERT(std::numeric_limits<Value>::is_signed,
         "The flow type of NetworkSimplex must be signed");
       LEMON_ASSERT(std::numeric_limits<Cost>::is_signed,
@@ -726 +726 @@
     ///
     /// \param map An arc map storing the lower bounds.
-    /// Its \c Value type must be convertible to the \c Flow type
+    /// Its \c Value type must be convertible to the \c Value type
     /// of the algorithm.
     ///
@@ -733 +733 @@
     NetworkSimplex& lowerMap(const LowerMap& map) {
       delete _plower;
-      _plower = new FlowArcMap(_graph);
+      _plower = new ValueArcMap(_graph);
       for (ArcIt a(_graph); a != INVALID; ++a) {
         (*_plower)[a] = map[a];
@@ -748 +748 @@
     ///
     /// \param map An arc map storing the upper bounds.
-    /// Its \c Value type must be convertible to the \c Flow type
+    /// Its \c Value type must be convertible to the \c Value type
     /// of the algorithm.
     ///
@@ -755 +755 @@
     NetworkSimplex& upperMap(const UpperMap& map) {
       delete _pupper;
-      _pupper = new FlowArcMap(_graph);
+      _pupper = new ValueArcMap(_graph);
       for (ArcIt a(_graph); a != INVALID; ++a) {
         (*_pupper)[a] = map[a];
@@ -791 +791 @@
     ///
     /// \param map A node map storing the supply values.
-    /// Its \c Value type must be convertible to the \c Flow type
+    /// Its \c Value type must be convertible to the \c Value type
     /// of the algorithm.
     ///
@@ -799 +799 @@
       delete _psupply;
       _pstsup = false;
-      _psupply = new FlowNodeMap(_graph);
+      _psupply = new ValueNodeMap(_graph);
       for (NodeIt n(_graph); n != INVALID; ++n) {
         (*_psupply)[n] = map[n];
@@ -824 +824 @@
     ///
     /// \return <tt>(*this)</tt>
-    NetworkSimplex& stSupply(const Node& s, const Node& t, Flow k) {
+    NetworkSimplex& stSupply(const Node& s, const Node& t, Value k) {
       delete _psupply;
       _psupply = NULL;
@@ -1026 +1026 @@
     ///
     /// \pre \ref run() must be called before using this function.
-    Flow flow(const Arc& a) const {
+    Value flow(const Arc& a) const {
       return (*_flow_map)[a];
     }
@@ -1205 +1205 @@
       if (_plower) {
         for (int i = 0; i != _arc_num; ++i) {
-          Flow c = (*_plower)[_arc_ref[i]];
+          Value c = (*_plower)[_arc_ref[i]];
           if (c > 0) {
             if (_cap[i] < INF) _cap[i] -= c;
@@ -1276 +1276 @@
       delta = _cap[in_arc];
       int result = 0;
-      Flow d;
+      Value d;
       int e;
 
@@ -1316 +1316 @@
       // Augment along the cycle
       if (delta > 0) {
-        Flow val = _state[in_arc] * delta;
+        Value val = _state[in_arc] * delta;
         _flow[in_arc] += val;
         for (int u = _source[in_arc]; u != join; u = _parent[u]) {