Changeset 2276:1a8a66b6c6ce in lemon-0.x

Timestamp:

10/30/06 18:22:14 (18 years ago)

Author:

Balazs Dezso

Branch:

default

Phase:

public

Convert:

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

Message:

Min cost flow is renamed to SspMinCostFlow?

Files:

• lemon/Makefile.am (modified) (2 diffs)
• lemon/min_cost_flow.h (deleted)
• lemon/ssp_min_cost_flow.h (added)
• lemon/suurballe.h (modified) (6 diffs)
• test/min_cost_flow_test.cc (modified) (2 diffs)

lemon/Makefile.am

@@ -77 +77 @@
         lemon/max_matching.h \
         lemon/min_cost_arborescence.h \
-        lemon/min_cost_flow.h \
         lemon/min_cut.h \
         lemon/mip_glpk.h \
@@ -91 +90 @@
         lemon/simann.h \
         lemon/smart_graph.h \
+        lemon/ssp_min_cost_flow.h \
         lemon/sub_graph.h \
         lemon/suurballe.h \

lemon/suurballe.h

@@ -27 +27 @@
 #include <lemon/maps.h>
 #include <vector>
-#include <lemon/min_cost_flow.h>
+#include <lemon/ssp_min_cost_flow.h>
 
 namespace lemon {
@@ -34 +34 @@
 /// @{
 
-  ///\brief Implementation of an algorithm for finding k edge-disjoint paths between 2 nodes 
-  /// of minimal total length 
+  ///\brief Implementation of an algorithm for finding k edge-disjoint
+  /// paths between 2 nodes of minimal total length
   ///
   /// The class \ref lemon::Suurballe implements
@@ -50 +50 @@
   ///%Suurballe for it is just a special case of Edmonds' and Karp's algorithm
   ///for finding minimum cost flows. In fact, this implementation just
-  ///wraps the MinCostFlow algorithms. The paper of both %Suurballe and
+  ///wraps the SspMinCostFlow algorithms. The paper of both %Suurballe and
   ///Edmonds-Karp published in 1972, therefore it is possibly right to
   ///state that they are
@@ -80 +80 @@
     ConstMap const1map;
     //This MinCostFlow instance will actually solve the problem
-    MinCostFlow<Graph, LengthMap, ConstMap> min_cost_flow;
+    SspMinCostFlow<Graph, LengthMap, ConstMap> min_cost_flow;
 
     //Container to store found paths
@@ -88 +88 @@
 
 
-    /*! \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.
-    */
+    /// \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.
-
-    ///Runs the algorithm.
-    ///Returns k if there are at least k edge-disjoint paths from s to t.
-    ///Otherwise it returns the number of edge-disjoint paths found 
-    ///from s to t.
-    ///
-    ///\param k How many paths are we looking for?
+    /// \brief 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 edge-disjoint paths found 
+    /// from s to t.
+    ///
+    /// \param k How many paths are we looking for?
     ///
     int run(int k) {
@@ -145 +144 @@
 
     
-    ///Returns the total length of the paths.
-    
-    ///This function gives back the total length of the found paths.
+    /// \brief Returns the total length of the paths.
+    ///
+    /// This function gives back the total length of the found paths.
     Length totalLength(){
       return min_cost_flow.totalLength();
     }
 
-    ///Returns the found flow.
-
-    ///This function returns a const reference to the EdgeMap \c flow.
+    /// \brief Returns the found flow.
+    ///
+    /// This function returns a const reference to the EdgeMap \c 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).
+    /// \brief Returns the optimal dual solution
+    ///
+    /// This function returns a const reference to the NodeMap \c
+    /// potential (the dual solution).
     const EdgeIntMap &getPotential() const { return min_cost_flow.potential;}
 
-    ///Checks whether the complementary slackness holds.
-
-    ///This function checks, whether the given solution is optimal.
-    ///Currently this function only checks optimality,
-    ///doesn't bother with feasibility.
-    ///It is meant for testing purposes.
+    /// \brief Checks whether the complementary slackness holds.
+    ///
+    /// This function checks, whether the given solution is optimal.
+    /// Currently this function only checks optimality, doesn't bother
+    /// with feasibility.  It is meant for testing purposes.
     bool checkComplementarySlackness(){
       return min_cost_flow.checkComplementarySlackness();
     }
 
-    ///Read the found paths.
-    
-    ///This function gives back the \c j-th path in argument p.
-    ///Assumes that \c run() has been run and nothing has changed since then.
-    /// \warning It is assumed that \c p is constructed to
-    ///be a path of graph \c G.
-    ///If \c j is not less than the result of previous \c run,
-    ///then the result here will be an empty path (\c j can be 0 as well).
-    ///
-    ///\param Path The type of the path structure to put the result to (must meet lemon path concept).
-    ///\param p The path to put the result to.
-    ///\param j Which path you want to get from the found paths (in a real application you would get the found paths iteratively).
+    /// \brief Read the found paths.
+    ///
+    /// This function gives back the \c j-th path in argument p.
+    /// Assumes that \c run() has been run and nothing has changed
+    /// since then.
+    ///
+    /// \warning It is assumed that \c p is constructed to be a path
+    /// of graph \c G.  If \c j is not less than the result of
+    /// previous \c run, then the result here will be an empty path
+    /// (\c j can be 0 as well).
+    ///
+    /// \param Path The type of the path structure to put the result
+    /// to (must meet lemon path concept).
+    /// \param p The path to put the result to.
+    /// \param j Which path you want to get from the found paths (in a
+    /// real application you would get the found paths iteratively).
     template<typename Path>
     void getPath(Path& p, size_t j){

test/min_cost_flow_test.cc

@@ -20 +20 @@
 #include "test_tools.h"
 #include <lemon/list_graph.h>
-#include <lemon/min_cost_flow.h>
+#include <lemon/ssp_min_cost_flow.h>
 //#include <path.h>
 //#include <maps.h>
@@ -93 +93 @@
   std::cout << "Mincostflows algorithm test..." << std::endl;
 
-  MinCostFlow< Graph, Graph::EdgeMap<int>, Graph::EdgeMap<int> >
+  SspMinCostFlow< Graph, Graph::EdgeMap<int>, Graph::EdgeMap<int> >
     surb_test(graph, length, capacity, s, t);