Changeset 633:305bd9c56f10 in lemon-0.x for src/work/athos/mincostflow.h

Timestamp:

05/13/04 18:00:18 (20 years ago)

Author:

athos

Branch:

default

Phase:

public

Convert:

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

Message:

Slight modifications.

File:

• src/work/athos/mincostflow.h (copied) (copied from src/hugo/mincostflows.h) (13 diffs)

src/work/athos/mincostflow.h

@@ -1 +1 @@
 // -*- c++ -*-
-#ifndef HUGO_MINCOSTFLOWS_H
-#define HUGO_MINCOSTFLOWS_H
+#ifndef HUGO_MINCOSTFLOW_H
+#define HUGO_MINCOSTFLOW_H
 
 ///\ingroup galgs
@@ -23 +23 @@
   /// 
   ///
-  /// The class \ref hugo::MinCostFlows "MinCostFlows" implements
-  /// an algorithm for finding a flow of value \c k 
-  ///(for small values of \c k) having minimal total cost  
-  /// from a given source node to a given target node in an
-  /// edge-weighted directed graph having nonnegative integer capacities.
+  /// The class \ref hugo::MinCostFlow "MinCostFlow" implements
+  /// an algorithm for solving the following general minimum cost flow problem>
+  /// 
+  ///
+  ///
+  /// \warning It is assumed here that the problem has a feasible solution
+  ///
   /// The range of the length (weight) function is nonnegative reals but 
   /// the range of capacity function is the set of nonnegative integers. 
@@ -35 +37 @@
   ///
   ///\author Attila Bernath
-  template <typename Graph, typename LengthMap, typename CapacityMap>
-  class MinCostFlows {
+  template <typename Graph, typename LengthMap, typename SupplyMap>
+  class MinCostFlow {
 
     typedef typename LengthMap::ValueType Length;
 
-    //Warning: this should be integer type
-    typedef typename CapacityMap::ValueType Capacity;
+
+    typedef typename SupplyMap::ValueType Supply;
     
     typedef typename Graph::Node Node;
@@ -83 +85 @@
     const Graph& G;
     const LengthMap& length;
-    const CapacityMap& capacity;
+    const SupplyMap& supply;//supply or demand of nodes
 
 
@@ -92 +94 @@
     //To store the potentila (dual variables)
     typename Graph::template NodeMap<Length> potential;
-    
-    //Container to store found paths
-    //std::vector< std::vector<Edge> > paths;
-    //typedef DirPath<Graph> DPath;
-    //DPath paths;
-
+    //To store excess-deficit values
+    SupplyMap excess;
+    
 
     Length total_length;
@@ -105 +104 @@
 
 
-    MinCostFlows(Graph& _G, LengthMap& _length, CapacityMap& _cap) : G(_G), 
-      length(_length), capacity(_cap), flow(_G), potential(_G){ }
+    MinCostFlow(Graph& _G, LengthMap& _length, SupplyMap& _supply) : G(_G), 
+      length(_length), supply(_supply), flow(_G), potential(_G){ }
 
     
@@ -116 +115 @@
     ///\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) {
+    int run() {
 
       //Resetting variables from previous runs
@@ -124 +123 @@
         flow.set(e,0);
       }
+
+      //Initial value for delta
+      Supply delta = 0;
       
       FOR_EACH_LOC(typename Graph::NodeIt, n, G){
-        //cout << potential[n]<<endl;
+        if (delta < abs(supply[e])){
+          delta = abs(supply[e]);
+        }
+        excess.set(n,supply[e]);
+        //Initialize the copy of the Dijkstra potential to zero
         potential.set(n,0);
       }
@@ -132 +138 @@
 
       
-      //We need a residual graph
-      ResGraphType res_graph(G, capacity, flow);
-
-      //Initialize the copy of the Dijkstra potential to zero
-      
-      //typename ResGraphType::template NodeMap<Length> potential(res_graph);
-
-
+      //We need a residual graph which is uncapacitated
+      ResGraphType res_graph(G, flow);
+
+
+      
       ModLengthMap mod_length(res_graph, length, potential);
 
       Dijkstra<ResGraphType, ModLengthMap> dijkstra(res_graph, mod_length);
+
 
       int i;
@@ -152 +156 @@
         };
         
+        //We have to copy the potential
+        FOR_EACH_LOC(typename ResGraphType::NodeIt, n, res_graph){
+          potential[n] += dijkstra.distMap()[n];
+        }
+
+        /*
         {
-          //We have to copy the potential
+
           typename ResGraphType::NodeIt n;
           for ( res_graph.first(n) ; res_graph.valid(n) ; res_graph.next(n) ) {
@@ -159 +169 @@
           }
         }
-
+        */
 
         //Augmenting on the sortest path
@@ -167 +177 @@
           e = dijkstra.pred(n);
           n = dijkstra.predNode(n);
-          res_graph.augment(e,1);
+          res_graph.augment(e,delta);
           //Let's update the total length
           if (res_graph.forward(e))
@@ -226 +236 @@
     }
     
-    /*
-      ///\todo To be implemented later
-
-    ///This function gives back the \c j-th path in argument p.
-    ///Assumes that \c run() has been run and nothing changed since then.
-    /// \warning It is assumed that \c p is constructed to be a path of graph \c G. If \c j is greater than the result of previous \c run, then the result here will be an empty path.
-    template<typename DirPath>
-    void getPath(DirPath& p, int j){
-      p.clear();
-      typename DirPath::Builder B(p);
-      for(typename std::vector<Edge>::iterator i=paths[j].begin(); 
-          i!=paths[j].end(); ++i ){
-        B.pushBack(*i);
-      }
-
-      B.commit();
-    }
-
-    */
-
-  }; //class MinCostFlows
+
+  }; //class MinCostFlow
 
   ///@}