Changeset 941:186aa53d2802 in lemon-0.x for src/lemon/suurballe.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/suurballe.h (modified) (8 diffs)

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