Changeset 641:756a5ec551c8 in lemon-1.2

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.

Location:

lemon

Files:

• circulation.h (modified) (11 diffs)
• network_simplex.h (modified) (20 diffs)
• preflow.h (modified) (15 diffs)

lemon/circulation.h

@@ -65 +65 @@
     typedef SM SupplyMap;
 
-    /// \brief The type of the flow values.
-    typedef typename SupplyMap::Value Flow;
+    /// \brief The type of the flow and supply values.
+    typedef typename SupplyMap::Value Value;
 
     /// \brief The type of the map that stores the flow values.
@@ -73 +73 @@
     /// It must conform to the \ref concepts::ReadWriteMap "ReadWriteMap"
     /// concept.
-    typedef typename Digraph::template ArcMap<Flow> FlowMap;
+    typedef typename Digraph::template ArcMap<Value> FlowMap;
 
     /// \brief Instantiates a FlowMap.
@@ -105 +105 @@
     ///
     /// The tolerance used by the algorithm to handle inexact computation.
-    typedef lemon::Tolerance<Flow> Tolerance;
+    typedef lemon::Tolerance<Value> Tolerance;
 
   };
@@ -188 +188 @@
     ///The type of the digraph the algorithm runs on.
     typedef typename Traits::Digraph Digraph;
-    ///The type of the flow values.
-    typedef typename Traits::Flow Flow;
+    ///The type of the flow and supply values.
+    typedef typename Traits::Value Value;
 
     ///The type of the lower bound map.
@@ -222 +222 @@
     bool _local_level;
 
-    typedef typename Digraph::template NodeMap<Flow> ExcessMap;
+    typedef typename Digraph::template NodeMap<Value> ExcessMap;
     ExcessMap* _excess;
 
@@ -531 +531 @@
           (*_excess)[_g.source(e)] -= (*_lo)[e];
         } else {
-          Flow fc = -(*_excess)[_g.target(e)];
+          Value fc = -(*_excess)[_g.target(e)];
           _flow->set(e, fc);
           (*_excess)[_g.target(e)] = 0;
@@ -564 +564 @@
         int actlevel=(*_level)[act];
         int mlevel=_node_num;
-        Flow exc=(*_excess)[act];
+        Value exc=(*_excess)[act];
 
         for(OutArcIt e(_g,act);e!=INVALID; ++e) {
           Node v = _g.target(e);
-          Flow fc=(*_up)[e]-(*_flow)[e];
+          Value fc=(*_up)[e]-(*_flow)[e];
           if(!_tol.positive(fc)) continue;
           if((*_level)[v]<actlevel) {
@@ -592 +592 @@
         for(InArcIt e(_g,act);e!=INVALID; ++e) {
           Node v = _g.source(e);
-          Flow fc=(*_flow)[e]-(*_lo)[e];
+          Value fc=(*_flow)[e]-(*_lo)[e];
           if(!_tol.positive(fc)) continue;
           if((*_level)[v]<actlevel) {
@@ -662 +662 @@
     ///@{
 
-    /// \brief Returns the flow on the given arc.
-    ///
-    /// Returns the flow on the given arc.
+    /// \brief Returns the flow value on the given arc.
+    ///
+    /// Returns the flow value on the given arc.
     ///
     /// \pre Either \ref run() or \ref init() must be called before
     /// using this function.
-    Flow flow(const Arc& arc) const {
+    Value flow(const Arc& arc) const {
       return (*_flow)[arc];
     }
@@ -751 +751 @@
       for(NodeIt n(_g);n!=INVALID;++n)
         {
-          Flow dif=-(*_supply)[n];
+          Value dif=-(*_supply)[n];
           for(InArcIt e(_g,n);e!=INVALID;++e) dif-=(*_flow)[e];
           for(OutArcIt e(_g,n);e!=INVALID;++e) dif+=(*_flow)[e];
@@ -766 +766 @@
     bool checkBarrier() const
     {
-      Flow delta=0;
-      Flow inf_cap = std::numeric_limits<Flow>::has_infinity ?
-        std::numeric_limits<Flow>::infinity() :
-        std::numeric_limits<Flow>::max();
+      Value delta=0;
+      Value inf_cap = std::numeric_limits<Value>::has_infinity ?
+        std::numeric_limits<Value>::infinity() :
+        std::numeric_limits<Value>::max();
       for(NodeIt n(_g);n!=INVALID;++n)
         if(barrier(n))

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]) {

lemon/preflow.h

@@ -47 +47 @@
 
     /// \brief The type of the flow values.
-    typedef typename CapacityMap::Value Flow;
+    typedef typename CapacityMap::Value Value;
 
     /// \brief The type of the map that stores the flow values.
@@ -53 +53 @@
     /// The type of the map that stores the flow values.
     /// It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
-    typedef typename Digraph::template ArcMap<Flow> FlowMap;
+    typedef typename Digraph::template ArcMap<Value> FlowMap;
 
     /// \brief Instantiates a FlowMap.
@@ -85 +85 @@
     ///
     /// The tolerance used by the algorithm to handle inexact computation.
-    typedef lemon::Tolerance<Flow> Tolerance;
+    typedef lemon::Tolerance<Value> Tolerance;
 
   };
@@ -126 +126 @@
     typedef typename Traits::CapacityMap CapacityMap;
     ///The type of the flow values.
-    typedef typename Traits::Flow Flow;
+    typedef typename Traits::Value Value;
 
     ///The type of the flow map.
@@ -152 +152 @@
     bool _local_level;
 
-    typedef typename Digraph::template NodeMap<Flow> ExcessMap;
+    typedef typename Digraph::template NodeMap<Value> ExcessMap;
     ExcessMap* _excess;
 
@@ -471 +471 @@
 
       for (NodeIt n(_graph); n != INVALID; ++n) {
-        Flow excess = 0;
+        Value excess = 0;
         for (InArcIt e(_graph, n); e != INVALID; ++e) {
           excess += (*_flow)[e];
@@ -520 +520 @@
 
       for (OutArcIt e(_graph, _source); e != INVALID; ++e) {
-        Flow rem = (*_capacity)[e] - (*_flow)[e];
+        Value rem = (*_capacity)[e] - (*_flow)[e];
         if (_tolerance.positive(rem)) {
           Node u = _graph.target(e);
@@ -532 +532 @@
       }
       for (InArcIt e(_graph, _source); e != INVALID; ++e) {
-        Flow rem = (*_flow)[e];
+        Value rem = (*_flow)[e];
         if (_tolerance.positive(rem)) {
           Node v = _graph.source(e);
@@ -565 +565 @@
 
         while (num > 0 && n != INVALID) {
-          Flow excess = (*_excess)[n];
+          Value excess = (*_excess)[n];
           int new_level = _level->maxLevel();
 
           for (OutArcIt e(_graph, n); e != INVALID; ++e) {
-            Flow rem = (*_capacity)[e] - (*_flow)[e];
+            Value rem = (*_capacity)[e] - (*_flow)[e];
             if (!_tolerance.positive(rem)) continue;
             Node v = _graph.target(e);
@@ -592 +592 @@
 
           for (InArcIt e(_graph, n); e != INVALID; ++e) {
-            Flow rem = (*_flow)[e];
+            Value rem = (*_flow)[e];
             if (!_tolerance.positive(rem)) continue;
             Node v = _graph.source(e);
@@ -638 +638 @@
         num = _node_num * 20;
         while (num > 0 && n != INVALID) {
-          Flow excess = (*_excess)[n];
+          Value excess = (*_excess)[n];
           int new_level = _level->maxLevel();
 
           for (OutArcIt e(_graph, n); e != INVALID; ++e) {
-            Flow rem = (*_capacity)[e] - (*_flow)[e];
+            Value rem = (*_capacity)[e] - (*_flow)[e];
             if (!_tolerance.positive(rem)) continue;
             Node v = _graph.target(e);
@@ -665 +665 @@
 
           for (InArcIt e(_graph, n); e != INVALID; ++e) {
-            Flow rem = (*_flow)[e];
+            Value rem = (*_flow)[e];
             if (!_tolerance.positive(rem)) continue;
             Node v = _graph.source(e);
@@ -779 +779 @@
       Node n;
       while ((n = _level->highestActive()) != INVALID) {
-        Flow excess = (*_excess)[n];
+        Value excess = (*_excess)[n];
         int level = _level->highestActiveLevel();
         int new_level = _level->maxLevel();
 
         for (OutArcIt e(_graph, n); e != INVALID; ++e) {
-          Flow rem = (*_capacity)[e] - (*_flow)[e];
+          Value rem = (*_capacity)[e] - (*_flow)[e];
           if (!_tolerance.positive(rem)) continue;
           Node v = _graph.target(e);
@@ -807 +807 @@
 
         for (InArcIt e(_graph, n); e != INVALID; ++e) {
-          Flow rem = (*_flow)[e];
+          Value rem = (*_flow)[e];
           if (!_tolerance.positive(rem)) continue;
           Node v = _graph.source(e);
@@ -898 +898 @@
     /// \pre Either \ref run() or \ref init() must be called before
     /// using this function.
-    Flow flowValue() const {
+    Value flowValue() const {
       return (*_excess)[_target];
     }
 
-    /// \brief Returns the flow on the given arc.
-    ///
-    /// Returns the flow on the given arc. This method can
+    /// \brief Returns the flow value on the given arc.
+    ///
+    /// Returns the flow value on the given arc. This method can
     /// be called after the second phase of the algorithm.
     ///
     /// \pre Either \ref run() or \ref init() must be called before
     /// using this function.
-    Flow flow(const Arc& arc) const {
+    Value flow(const Arc& arc) const {
       return (*_flow)[arc];
     }