Changeset 941:186aa53d2802 in lemon-0.x for src/lemon/min_cost_flow.h

Timestamp:

10/08/04 15:07:51 (20 years ago)

Author:

marci

Branch:

default

Phase:

public

Convert:

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

Message:

Suurballe and MinCostFlow? classes are now able to increase the flow 1 by 1 with
this->augment()

File:

• src/lemon/min_cost_flow.h (modified) (4 diffs)

src/lemon/min_cost_flow.h

@@ -71 +71 @@
     typedef typename Graph::template EdgeMap<int> EdgeIntMap;
 
-
     typedef ResGraphWrapper<const Graph,int,CapacityMap,EdgeIntMap> ResGW;
     typedef typename ResGW::Edge ResGraphEdge;
 
+  protected:
+
+    const Graph& g;
+    const LengthMap& length;
+    const CapacityMap& capacity;
+
+    EdgeIntMap flow; 
+    typedef typename Graph::template NodeMap<Length> PotentialMap;
+    PotentialMap potential;
+
+    Node s;
+    Node t;
+    
+    Length total_length;
+
     class ModLengthMap {   
       typedef typename Graph::template NodeMap<Length> NodeMap;
-      const ResGW& G;
-      const LengthMap &ol;
+      const ResGW& g;
+      const LengthMap &length;
       const NodeMap &pot;
     public :
       typedef typename LengthMap::KeyType KeyType;
       typedef typename LengthMap::ValueType ValueType;
+
+      ModLengthMap(const ResGW& _g, 
+                   const LengthMap &_length, const NodeMap &_pot) : 
+        g(_g), /*rev(_rev),*/ length(_length), pot(_pot) { }
         
       ValueType operator[](typename ResGW::Edge e) const {     
-        if (G.forward(e))
-          return  ol[e]-(pot[G.head(e)]-pot[G.tail(e)]);   
+        if (g.forward(e))
+          return  length[e]-(pot[g.head(e)]-pot[g.tail(e)]);   
         else
-          return -ol[e]-(pot[G.head(e)]-pot[G.tail(e)]);   
+          return -length[e]-(pot[g.head(e)]-pot[g.tail(e)]);   
       }     
         
-      ModLengthMap(const ResGW& _G,
-                   const LengthMap &o,  const NodeMap &p) : 
-        G(_G), /*rev(_rev),*/ ol(o), pot(p){}; 
-    };//ModLengthMap
-
-
-  protected:
-    
-    //Input
-    const Graph& G;
-    const LengthMap& length;
-    const CapacityMap& capacity;
-
-
-    //auxiliary variables
-
-    //To store the flow
-    EdgeIntMap flow; 
-    //To store the potential (dual variables)
-    typedef typename Graph::template NodeMap<Length> PotentialMap;
-    PotentialMap potential;
-    
-
-    Length total_length;
-
+    }; //ModLengthMap
+
+    ResGW res_graph;
+    ModLengthMap mod_length;
+    Dijkstra<ResGW, ModLengthMap> dijkstra;
 
   public :
 
-    /// The constructor of the class.
-    
-    ///\param _G The directed graph the algorithm runs on. 
-    ///\param _length The length (weight or cost) of the edges. 
-    ///\param _cap The capacity of the edges. 
-    MinCostFlow(Graph& _G, LengthMap& _length, CapacityMap& _cap) : G(_G), 
-      length(_length), capacity(_cap), flow(_G), potential(_G){ }
-
-    
-    ///Runs the algorithm.
-    
-    ///Runs the algorithm.
-    ///Returns k if there is a flow of value at least k edge-disjoint 
-    ///from s to t.
-    ///Otherwise it returns the maximum value of a flow from s to t.
-    ///
-    ///\param s The source node.
-    ///\param t The target node.
-    ///\param k The value of the flow we are looking for.
-    ///
-    ///\todo May be it does make sense to be able to start with a nonzero 
-    /// feasible primal-dual solution pair as well.
-    int run(Node s, Node t, int k) {
-
-      //Resetting variables from previous runs
-      total_length = 0;
-      
-      for (typename Graph::EdgeIt e(G); e!=INVALID; ++e) flow.set(e, 0);
-
-      //Initialize the potential to zero
-      for (typename Graph::NodeIt n(G); n!=INVALID; ++n) potential.set(n, 0);
-      
-      
-      //We need a residual graph
-      ResGW res_graph(G, capacity, flow);
-
-
-      ModLengthMap mod_length(res_graph, length, potential);
-
-      Dijkstra<ResGW, ModLengthMap> dijkstra(res_graph, mod_length);
-
-      int i;
-      for (i=0; i<k; ++i){
-        dijkstra.run(s);
-        if (!dijkstra.reached(t)){
-          //There are no flow of value k from s to t
-          break;
-        };
+    /*! \brief The constructor of the class.
+    
+    \param _g The directed graph the algorithm runs on. 
+    \param _length The length (weight or cost) of the edges. 
+    \param _cap The capacity of the edges. 
+    \param _s Source node.
+    \param _t Target node.
+    */
+    MinCostFlow(Graph& _g, LengthMap& _length, CapacityMap& _cap, 
+                Node _s, Node _t) : 
+      g(_g), length(_length), capacity(_cap), flow(_g), potential(_g), 
+      s(_s), t(_t), 
+      res_graph(g, capacity, flow), 
+      mod_length(res_graph, length, potential),
+      dijkstra(res_graph, mod_length) { 
+      reset();
+      }
+
+    /*! Tries to augment the flow between s and t by 1.
+      The return value shows if the augmentation is successful.
+     */
+    bool augment() {
+      dijkstra.run(s);
+      if (!dijkstra.reached(t)) {
+
+        //Unsuccessful augmentation.
+        return false;
+      } else {
+
+        //We have to change the potential
+        for(typename ResGW::NodeIt n(res_graph); n!=INVALID; ++n)
+          potential[n] += dijkstra.distMap()[n];
         
-        //We have to change the potential
-        for(typename ResGW::NodeIt n(res_graph); n!=INVALID; ++n)
-          potential[n] += dijkstra.distMap()[n];
-
-
         //Augmenting on the sortest path
         Node n=t;
@@ -187 +164 @@
         }
 
-          
+        return true;
       }
-      
-
+    }
+    
+    /*! \brief Runs the algorithm.
+    
+    Runs the algorithm.
+    Returns k if there is a flow of value at least k from s to t.
+    Otherwise it returns the maximum value of a flow from s to t.
+    
+    \param k The value of the flow we are looking for.
+    
+    \todo May be it does make sense to be able to start with a nonzero 
+    feasible primal-dual solution pair as well.
+    
+    \todo If the actual flow value is bigger than k, then everything is 
+    cleared and the algorithm starts from zero flow. Is it a good approach?
+    */
+    int run(int k) {
+      if (flowValue()>k) reset();
+      while (flowValue()<k && augment()) { }
+      return flowValue();
+    }
+
+    /*! \brief The class is reset to zero flow and potential.
+      The class is reset to zero flow and potential.
+     */
+    void reset() {
+      total_length=0;
+      for (typename Graph::EdgeIt e(g); e!=INVALID; ++e) flow.set(e, 0);
+      for (typename Graph::NodeIt n(g); n!=INVALID; ++n) potential.set(n, 0);  
+    }
+
+    /*! Returns the value of the actual flow. 
+     */
+    int flowValue() const {
+      int i=0;
+      for (typename Graph::OutEdgeIt e(g, s); e!=INVALID; ++e) i+=flow[e];
+      for (typename Graph::InEdgeIt e(g, s); e!=INVALID; ++e) i-=flow[e];
       return i;
     }
 
-
-
-    /// Gives back the total weight of the found flow.
-
-    ///This function gives back the total weight of the found flow.
-    ///Assumes that \c run() has been run and nothing changed since then.
+    /// Total weight of the found flow.
+
+    /// This function gives back the total weight of the found flow.
     Length totalLength(){
       return total_length;
@@ -207 +216 @@
 
     ///Returns a const reference to the EdgeMap \c flow. 
-    ///\pre \ref run() must
-    ///be called before using this function.
     const EdgeIntMap &getFlow() const { return flow;}
 
-    ///Returns a const reference to the NodeMap \c potential (the dual solution).
-
-    ///Returns a const reference to the NodeMap \c potential (the dual solution).
-    /// \pre \ref run() must be called before using this function.
+    /*! \brief Returns a const reference to the NodeMap \c potential (the dual solution).
+
+    Returns a const reference to the NodeMap \c potential (the dual solution).
+    */
     const PotentialMap &getPotential() const { return potential;}
 
-    /// Checking the complementary slackness optimality criteria
-
-    ///This function checks, whether the given solution is optimal
-    ///If executed after the call of \c run() then it should return with true.
-    ///This function only checks optimality, doesn't bother with feasibility.
-    ///It is meant for testing purposes.
-    ///
+    /*! \brief Checking the complementary slackness optimality criteria.
+
+    This function checks, whether the given flow and potential 
+    satisfiy the complementary slackness cnditions (i.e. these are optimal).
+    This function only checks optimality, doesn't bother with feasibility.
+    For testing purpose.
+    */
     bool checkComplementarySlackness(){
       Length mod_pot;
       Length fl_e;
-        for(typename Graph::EdgeIt e(G); e!=INVALID; ++e) {
+        for(typename Graph::EdgeIt e(g); e!=INVALID; ++e) {
         //C^{\Pi}_{i,j}
-        mod_pot = length[e]-potential[G.head(e)]+potential[G.tail(e)];
+        mod_pot = length[e]-potential[g.head(e)]+potential[g.tail(e)];
         fl_e = flow[e];
         if (0<fl_e && fl_e<capacity[e]) {
@@ -247 +254 @@
     }
     
-
   }; //class MinCostFlow