# HG changeset patch
# User marci
# Date 1097240871 0
# Node ID 186aa53d2802348542bf3e993f06b42fc80be386
# Parent  50a153b08f07358ff45633abdbcb5e4f57115168
Suurballe and MinCostFlow classes are now able to increase the flow 1 by 1 with
this->augment()

diff -r 50a153b08f07 -r 186aa53d2802 src/lemon/min_cost_flow.h
--- a/src/lemon/min_cost_flow.h	Thu Oct 07 17:21:27 2004 +0000
+++ b/src/lemon/min_cost_flow.h	Fri Oct 08 13:07:51 2004 +0000
@@ -70,108 +70,85 @@
     typedef typename Graph::OutEdgeIt OutEdgeIt;
     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
+    }; //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;
-
+    ResGW res_graph;
+    ModLengthMap mod_length;
+    Dijkstra<ResGW, ModLengthMap> dijkstra;
 
   public :
 
-    /// The constructor of the class.
+    /*! \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. 
-    MinCostFlow(Graph& _G, LengthMap& _length, CapacityMap& _cap) : G(_G), 
-      length(_length), capacity(_cap), flow(_G), potential(_G){ }
+    \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();
+      }
 
-    
-    ///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) {
+    /*! 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)) {
 
-      //Resetting variables from previous runs
-      total_length = 0;
-      
-      for (typename Graph::EdgeIt e(G); e!=INVALID; ++e) flow.set(e, 0);
+	//Unsuccessful augmentation.
+	return false;
+      } else {
 
-      //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;
-	};
+	//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;
 	ResGraphEdge e;
@@ -186,19 +163,51 @@
 	    total_length -= length[e];	    
 	}
 
-	  
+	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;
     }
 
+    /// Total weight of the found flow.
 
-
-    /// 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.
+    /// This function gives back the total weight of the found flow.
     Length totalLength(){
       return total_length;
     }
@@ -206,29 +215,27 @@
     ///Returns a const reference to the EdgeMap \c flow. 
 
     ///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).
+    /*! \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).
-    /// \pre \ref run() must be called before using this function.
+    Returns a const reference to the NodeMap \c potential (the dual solution).
+    */
     const PotentialMap &getPotential() const { return potential;}
 
-    /// Checking the complementary slackness optimality criteria
+    /*! \brief 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.
-    ///
+    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]) {
 	  /// \todo better comparison is needed for real types, moreover, 
@@ -246,7 +253,6 @@
       return true;
     }
     
-
   }; //class MinCostFlow
 
   ///@}
diff -r 50a153b08f07 -r 186aa53d2802 src/lemon/suurballe.h
--- a/src/lemon/suurballe.h	Thu Oct 07 17:21:27 2004 +0000
+++ b/src/lemon/suurballe.h	Fri Oct 08 13:07:51 2004 +0000
@@ -68,14 +68,16 @@
 
     typedef ConstMap<Edge,int> ConstMap;
 
-    //Input
     const Graph& G;
 
+    Node s;
+    Node t;
+
     //Auxiliary variables
     //This is the capacity map for the mincostflow problem
     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
     std::vector< std::vector<Edge> > paths;
@@ -83,39 +85,40 @@
   public :
 
 
-    /// The constructor of the class.
+    /*! \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. 
-    Suurballe(Graph& _G, LengthMap& _length) : G(_G),
-      const1map(1), mincost_flow(_G, _length, const1map){}
+    \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.
 
     ///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
       //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.
 
-      //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();
       //total_length=0;
@@ -143,39 +146,32 @@
     }
 
     
-    ///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();
     }
 
     ///Returns the found flow.
 
     ///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
     
     ///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();
     }
 
     ///Read the found paths.
diff -r 50a153b08f07 -r 186aa53d2802 src/test/min_cost_flow_test.cc
--- a/src/test/min_cost_flow_test.cc	Thu Oct 07 17:21:27 2004 +0000
+++ b/src/test/min_cost_flow_test.cc	Fri Oct 08 13:07:51 2004 +0000
@@ -21,11 +21,9 @@
 //#include <path.h>
 //#include <maps.h>
 
-using namespace std;
 using namespace lemon;
 
 
-
 bool passed = true;
 /*
 void check(bool rc, char *msg="") {
@@ -41,11 +39,11 @@
 
 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
 
@@ -67,7 +65,7 @@
   Edge v5_t=graph.addEdge(v5, t);
   
 
-  ListGraph::EdgeMap<int> length(graph);
+  Graph::EdgeMap<int> length(graph);
 
   length.set(s_v1, 6);
   length.set(v1_v2, 4);
@@ -78,7 +76,7 @@
   length.set(v4_t, 8);
   length.set(v5_t, 8);
 
-  ListGraph::EdgeMap<int> capacity(graph);
+  Graph::EdgeMap<int> capacity(graph);
 
   capacity.set(s_v1, 2);
   capacity.set(v1_v2, 2);
@@ -92,31 +90,36 @@
   //  ConstMap<Edge, int> const1map(1);
   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?");
   
   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;
 
diff -r 50a153b08f07 -r 186aa53d2802 src/test/suurballe_test.cc
--- a/src/test/suurballe_test.cc	Thu Oct 07 17:21:27 2004 +0000
+++ b/src/test/suurballe_test.cc	Fri Oct 08 13:07:51 2004 +0000
@@ -20,21 +20,19 @@
 //#include <path.h>
 #include "test_tools.h"
 
-using namespace std;
 using namespace lemon;
 
 
-
 bool passed = true;
 
 
 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
 
@@ -56,7 +54,7 @@
   Edge v5_t=graph.addEdge(v5, t);
   
 
-  ListGraph::EdgeMap<int> length(graph);
+  Graph::EdgeMap<int> length(graph);
 
   length.set(s_v1, 6);
   length.set(v1_v2, 4);
@@ -71,29 +69,29 @@
 
   
   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");
 
   check(  surb_test.checkComplementarySlackness(),
 	  "Complementary slackness conditions are not met.");
 
-  //  typedef DirPath<ListGraph> DPath;
+  //  typedef DirPath<Graph> DPath;
   //  DPath P(graph);
 
   /*
   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");
 
   check(  surb_test.checkComplementarySlackness(),
@@ -102,8 +100,8 @@
   //  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;
+  std::cout << (passed ? "All tests passed." : "Some of the tests failed!!!")
+	    << std::endl;
 
   return passed ? 0 : 1;