Changeset 530:d9c06ac0b3a3 in lemon-0.x

Timestamp:

05/04/04 18:52:15 (20 years ago)

Author:

athos

Branch:

default

Phase:

public

Convert:

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

Message:

Minimum cost flows of small values: algorithm from Andras Frank's lecture notes (approximately)

Location:

src/work/athos

Files:

• mincostflows.h (modified) (11 diffs)
• mincostflows_test.cc (modified) (2 diffs)

src/work/athos/mincostflows.h

@@ -12 +12 @@
 #include <maps.h>
 #include <vector.h>
-
+#include <for_each_macros.h>
 
 namespace hugo {
@@ -35 +35 @@
   ///
   ///\author Attila Bernath
-  template <typename Graph, typename LengthMap>
+  template <typename Graph, typename LengthMap, typename CapacityMap>
   class MinCostFlows {
 
     typedef typename LengthMap::ValueType Length;
 
-    typedef typename LengthMap::ValueType Length;
+    //Warning: this should be integer type
+    typedef typename CapacityMap::ValueType Capacity;
     
     typedef typename Graph::Node Node;
@@ -50 +51 @@
     //    typedef ConstMap<Edge,int> ConstMap;
 
-    typedef ResGraphWrapper<const Graph,int,EdgeIntMap,EdgeIntMap> ResGraphType;
-
+    typedef ResGraphWrapper<const Graph,int,CapacityMap,EdgeIntMap> ResGraphType;
+    typedef typename ResGraphType::Edge ResGraphEdge;
     class ModLengthMap {   
       typedef typename ResGraphType::template NodeMap<Length> NodeMap;
@@ -69 +70 @@
       }     
         
-      ModLengthMap(const ResGraphType& _G, const EdgeIntMap& _rev, 
+      ModLengthMap(const ResGraphType& _G,
                    const LengthMap &o,  const NodeMap &p) : 
         G(_G), /*rev(_rev),*/ ol(o), pot(p){}; 
@@ -79 +80 @@
     const Graph& G;
     const LengthMap& length;
-    const EdgeIntMap& capacity;
+    const CapacityMap& capacity;
 
     //auxiliary variables
@@ -99 +100 @@
 
 
-    MinLengthPaths(Graph& _G, LengthMap& _length, EdgeIntMap& _cap) : G(_G), 
+    MinCostFlows(Graph& _G, LengthMap& _length, CapacityMap& _cap) : G(_G), 
       length(_length), capacity(_cap), flow(_G)/*, dijkstra_dist(_G)*/{ }
 
@@ -110 +111 @@
     int run(Node s, Node t, int k) {
 
-
+      //Resetting variables from previous runs
+      total_length = 0;
+      FOR_EACH_LOC(typename Graph::EdgeIt, e, G){
+        flow.set(e,0);
+      }
+
+      
       //We need a residual graph
       ResGraphType res_graph(G, capacity, flow);
@@ -139 +146 @@
         //Augmenting on the sortest path
         Node n=t;
-        Edge e;
+        ResGraphEdge e;
         while (n!=s){
           e = dijkstra.pred(n);
           n = dijkstra.predNode(n);
-          G.augment(e,1);
+          res_graph.augment(e,1);
+          //Let's update the total length
+          if (res_graph.forward(e))
+            total_length += length[e];
+          else 
+            total_length -= length[e];      
         }
 
@@ -149 +161 @@
       }
       
-      /*
-        ///\TODO To be implemented later
-
-      //Let's find the paths
-      //We put the paths into stl vectors (as an inner representation). 
-      //In the meantime we lose the information stored in 'reversed'.
-      //We suppose the lengths to be positive now.
-
-      //Meanwhile we put the total length of the found paths 
-      //in the member variable total_length
-      paths.clear();
-      total_length=0;
-      paths.resize(k);
-      for (int j=0; j<i; ++j){
-        Node n=s;
-        OutEdgeIt e;
-
-        while (n!=t){
-
-
-          G.first(e,n);
-          
-          while (!reversed[e]){
-            G.next(e);
-          }
-          n = G.head(e);
-          paths[j].push_back(e);
-          total_length += length[e];
-          reversed[e] = 1-reversed[e];
-        }
-        
-      }
-      */
 
       return i;
     }
+
+
 
     ///This function gives back the total length of the found paths.
@@ -191 +172 @@
       return total_length;
     }
+
+    /*
+      ///\todo To be implemented later
 
     ///This function gives back the \c j-th path in argument p.
@@ -207 +191 @@
     }
 
-  }; //class MinLengthPaths
+    */
+
+  }; //class MinCostFlows
 
   ///@}

src/work/athos/mincostflows_test.cc

@@ -62 +62 @@
   length.set(v5_t, 8);
 
-  ConstMap const1map(1);
-  std::cout << "Minlengthpaths algorithm test..." << std::endl;
+  ConstMap<Edge, int> const1map(1);
+  std::cout << "Mincostflows algorithm test..." << std::endl;
 
   
   int k=3;
-  MinCostFlows< ListGraph, ListGraph::EdgeMap<int> >
+  MinCostFlows< ListGraph, ListGraph::EdgeMap<int>, ConstMap<Edge, int> >
     surb_test(graph, length, const1map);
 
   check(  surb_test.run(s,t,k) == 2 && surb_test.totalLength() == 46,"Two paths, total length should be 46");
 
+  k=1;
+  check(  surb_test.run(s,t,k) == 1 && surb_test.totalLength() == 19,"One path, total length should be 19");
+  
+  //cout << surb_test.run(s,t,k) << surb_test.totalLength()<<endl;
+  /*
   typedef DirPath<ListGraph> DPath;
   DPath P(graph);
@@ -86 +91 @@
   surb_test.getPath(P,0);
   check(P.length() == 4, "First path should contain 4 edges.");  
-
+  */
   cout << (passed ? "All tests passed." : "Some of the tests failed!!!")
        << endl;