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

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()

Location:

src

Files:

• lemon/min_cost_flow.h (modified) (4 diffs)
• lemon/suurballe.h (modified) (8 diffs)
• test/min_cost_flow_test.cc (modified) (6 diffs)
• test/suurballe_test.cc (modified) (7 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
 

src/lemon/suurballe.h

@@ -69 +69 @@
     typedef ConstMap<Edge,int> ConstMap;
 
-    //Input
     const Graph& G;
+
+    Node s;
+    Node t;
 
     //Auxiliary variables
@@ -76 +78 @@
     ConstMap const1map;
     //This MinCostFlow instance will actually solve the problem
-    MinCostFlow<Graph, LengthMap, ConstMap> mincost_flow;
+    MinCostFlow<Graph, LengthMap, ConstMap> min_cost_flow;
 
     //Container to store found paths
@@ -84 +86 @@
 
 
-    /// The constructor of the class.
-    
-    ///\param _G The directed graph the algorithm runs on. 
-    ///\param _length The length (weight or cost) of the edges. 
-    Suurballe(Graph& _G, LengthMap& _length) : G(_G),
-      const1map(1), mincost_flow(_G, _length, const1map){}
+    /*! \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 _s Source node.
+    \param _t Target node.
+    */
+    Suurballe(Graph& _G, LengthMap& _length, Node _s, Node _t) : 
+      G(_G), s(_s), t(_t), const1map(1), 
+      min_cost_flow(_G, _length, const1map, _s, _t) { }
 
     ///Runs the algorithm.
@@ -95 +101 @@
     ///Runs the algorithm.
     ///Returns k if there are at least k edge-disjoint paths from s to t.
-    ///Otherwise it returns the number of found edge-disjoint paths from s to t.
+    ///Otherwise it returns the number of edge-disjoint paths found 
+    ///from s to t.
     ///
-    ///\param s The source node.
-    ///\param t The target node.
     ///\param k How many paths are we looking for?
     ///
-    int run(Node s, Node t, int k) {
-
-      int i = mincost_flow.run(s,t,k);
-    
+    int run(int k) {
+      int i = min_cost_flow.run(k);
 
       //Let's find the paths
@@ -111 +114 @@
       //We suppose the lengths to be positive now.
 
-      //We don't want to change the flow of mincost_flow, so we make a copy
+      //We don't want to change the flow of min_cost_flow, so we make a copy
       //The name here suggests that the flow has only 0/1 values.
       EdgeIntMap reversed(G); 
 
       for(typename Graph::EdgeIt e(G); e!=INVALID; ++e) 
-        reversed[e] = mincost_flow.getFlow()[e];
+        reversed[e] = min_cost_flow.getFlow()[e];
       
       paths.clear();
@@ -144 +147 @@
 
     
-    ///Returns the total length of the paths
+    ///Returns the total length of the paths.
     
     ///This function gives back the total length of the found paths.
-    ///\pre \ref run() must
-    ///be called before using this function.
     Length totalLength(){
-      return mincost_flow.totalLength();
+      return min_cost_flow.totalLength();
     }
 
@@ -156 +157 @@
 
     ///This function returns a const reference to the EdgeMap \c flow.
-    ///\pre \ref run() must
-    ///be called before using this function.
-    const EdgeIntMap &getFlow() const { return mincost_flow.flow;}
+    const EdgeIntMap &getFlow() const { return min_cost_flow.flow;}
 
     /// Returns the optimal dual solution
@@ -164 +163 @@
     ///This function returns a const reference to the NodeMap
     ///\c potential (the dual solution).
-    /// \pre \ref run() must be called before using this function.
-    const EdgeIntMap &getPotential() const { return mincost_flow.potential;}
+    const EdgeIntMap &getPotential() const { return min_cost_flow.potential;}
 
     ///Checks whether the complementary slackness holds.
 
     ///This function checks, whether the given solution is optimal.
-    ///It should return true after calling \ref run() 
     ///Currently this function only checks optimality,
     ///doesn't bother with feasibility
     ///It is meant for testing purposes.
-    ///
     bool checkComplementarySlackness(){
-      return mincost_flow.checkComplementarySlackness();
+      return min_cost_flow.checkComplementarySlackness();
     }
 

src/test/min_cost_flow_test.cc

@@ -22 +22 @@
 //#include <maps.h>
 
-using namespace std;
 using namespace lemon;
-
 
 
@@ -42 +40 @@
 int main()
 {
+  typedef ListGraph Graph;
+  typedef Graph::Node Node;
+  typedef Graph::Edge Edge;
 
-  typedef ListGraph::Node Node;
-  typedef ListGraph::Edge Edge;
-
-  ListGraph graph;
+  Graph graph;
 
   //Ahuja könyv példája
@@ -68 +66 @@
   
 
-  ListGraph::EdgeMap<int> length(graph);
+  Graph::EdgeMap<int> length(graph);
 
   length.set(s_v1, 6);
@@ -79 +77 @@
   length.set(v5_t, 8);
 
-  ListGraph::EdgeMap<int> capacity(graph);
+  Graph::EdgeMap<int> capacity(graph);
 
   capacity.set(s_v1, 2);
@@ -93 +91 @@
   std::cout << "Mincostflows algorithm test..." << std::endl;
 
-  MinCostFlow< ListGraph, ListGraph::EdgeMap<int>, ListGraph::EdgeMap<int> >
-    surb_test(graph, length, capacity);
+  MinCostFlow< Graph, Graph::EdgeMap<int>, Graph::EdgeMap<int> >
+    surb_test(graph, length, capacity, s, t);
 
   int k=1;
 
-  check(  surb_test.run(s,t,k) == 1 && surb_test.totalLength() == 19,"One path, total length should be 19");
+  surb_test.augment();
+  check(  surb_test.flowValue() == 1 && surb_test.totalLength() == 19,"One path, total length should be 19");
+
+  check(  surb_test.run(k) == 1 && surb_test.totalLength() == 19,"One path, total length should be 19");
 
   check(surb_test.checkComplementarySlackness(), "Is the primal-dual solution pair really optimal?");
@@ -104 +105 @@
   k=2;
   
-  check(  surb_test.run(s,t,k) == 2 && surb_test.totalLength() == 41,"Two paths, total length should be 41");
+  check(  surb_test.run(k) == 2 && surb_test.totalLength() == 41,"Two paths, total length should be 41");
 
   check(surb_test.checkComplementarySlackness(), "Is the primal-dual solution pair really optimal?");
   
-  
+  surb_test.augment();
+  surb_test.augment();
+  surb_test.augment();
   k=4;
 
-  check(  surb_test.run(s,t,k) == 3 && surb_test.totalLength() == 64,"Three paths, total length should be 64");
+  check(  surb_test.run(k) == 3 && surb_test.totalLength() == 64,"Three paths, total length should be 64");
 
   check(surb_test.checkComplementarySlackness(), "Is the primal-dual solution pair really optimal?");
 
 
-  cout << (passed ? "All tests passed." : "Some of the tests failed!!!")
-       << endl;
+  std::cout << (passed ? "All tests passed." : "Some of the tests failed!!!")
+            << std::endl;
 
   return passed ? 0 : 1;

src/test/suurballe_test.cc

@@ -21 +21 @@
 #include "test_tools.h"
 
-using namespace std;
 using namespace lemon;
-
 
 
@@ -31 +29 @@
 int main()
 {
+  typedef ListGraph Graph;
+  typedef Graph::Node Node;
+  typedef Graph::Edge Edge;
 
-  typedef ListGraph::Node Node;
-  typedef ListGraph::Edge Edge;
-
-  ListGraph graph;
+  Graph graph;
 
   //Ahuja könyv példája
@@ -57 +55 @@
   
 
-  ListGraph::EdgeMap<int> length(graph);
+  Graph::EdgeMap<int> length(graph);
 
   length.set(s_v1, 6);
@@ -72 +70 @@
   
   int k=3;
-  Suurballe< ListGraph, ListGraph::EdgeMap<int> >
-    surb_test(graph, length);
+  Suurballe< Graph, Graph::EdgeMap<int> >
+    surb_test(graph, length, s, t);
 
-  check(  surb_test.run(s,t,k) == 2 && surb_test.totalLength() == 46,
+  check(  surb_test.run(k) == 2 && surb_test.totalLength() == 46,
           "Two paths, total length should be 46");
 
@@ -81 +79 @@
           "Complementary slackness conditions are not met.");
 
-  //  typedef DirPath<ListGraph> DPath;
+  //  typedef DirPath<Graph> DPath;
   //  DPath P(graph);
 
@@ -87 +85 @@
   surb_test.getPath(P,0);
   check(P.length() == 4, "First path should contain 4 edges.");  
-  cout<<P.length()<<endl;
+  std::cout<<P.length()<<std::endl;
   surb_test.getPath(P,1);
   check(P.length() == 3, "Second path: 3 edges.");
-  cout<<P.length()<<endl;
+  std::cout<<P.length()<<std::endl;
   */  
 
   k=1;
-  check(  surb_test.run(s,t,k) == 1 && surb_test.totalLength() == 19,
+  check(  surb_test.run(k) == 1 && surb_test.totalLength() == 19,
           "One path, total length should be 19");
 
@@ -103 +101 @@
   //  check(P.length() == 4, "First path should contain 4 edges.");  
 
-  cout << (passed ? "All tests passed." : "Some of the tests failed!!!")
-       << endl;
+  std::cout << (passed ? "All tests passed." : "Some of the tests failed!!!")
+            << std::endl;
 
   return passed ? 0 : 1;