# HG changeset patch
# User athos
# Date 1095330374 0
# Node ID 3577b3db6089c75481bf69ec84dba060f05aea6a
# Parent  2570784896d86d6c42f00dfec6c5e7800f3e1bbc
Completed documentation for mincostflows and minlengthpaths.

diff -r 2570784896d8 -r 3577b3db6089 src/hugo/mincostflows.h
--- a/src/hugo/mincostflows.h	Wed Sep 15 14:38:13 2004 +0000
+++ b/src/hugo/mincostflows.h	Thu Sep 16 10:26:14 2004 +0000
@@ -23,19 +23,26 @@
   ///
   /// The class \ref hugo::MinCostFlows "MinCostFlows" implements
   /// an algorithm for finding a flow of value \c k 
-  ///(for small values of \c k) having minimal total cost  
+  /// having minimal total cost  
   /// from a given source node to a given target node in an
   /// edge-weighted directed graph having nonnegative integer capacities.
-  /// The range of the length (weight) function is nonnegative reals but 
-  /// the range of capacity function is the set of nonnegative integers. 
-  /// It is not a polinomial time algorithm for counting the minimum cost
-  /// maximal flow, since it counts the minimum cost flow for every value 0..M
-  /// where \c M is the value of the maximal flow.
+  /// The range of the length (weight or cost) function can be nonnegative reals but 
+  /// the range of the capacity function has to be the set of nonnegative integers.
+  /// This algorithm is intended to use only for for small values of \c k, since  /// it is not a polinomial time algorithm for finding the minimum cost
+  /// maximal flow (in order to find the minimum cost flow of value \c k it 
+  /// finds the minimum cost flow of value \c i for every 
+  /// \c i between 0 and \c k). 
+  ///
+  ///\param Graph The directed graph type the algorithm runs on.
+  ///\param LengthMap The type of the length map.
+  ///\param CapacityMap The capacity map type.
   ///
   ///\author Attila Bernath
   template <typename Graph, typename LengthMap, typename CapacityMap>
   class MinCostFlows {
 
+
+
     typedef typename LengthMap::ValueType Length;
 
     //Warning: this should be integer type
@@ -47,16 +54,13 @@
     typedef typename Graph::OutEdgeIt OutEdgeIt;
     typedef typename Graph::template EdgeMap<int> EdgeIntMap;
 
-    //    typedef ConstMap<Edge,int> ConstMap;
 
     typedef ResGraphWrapper<const Graph,int,CapacityMap,EdgeIntMap> ResGraphType;
     typedef typename ResGraphType::Edge ResGraphEdge;
 
     class ModLengthMap {   
-      //typedef typename ResGraphType::template NodeMap<Length> NodeMap;
       typedef typename Graph::template NodeMap<Length> NodeMap;
       const ResGraphType& G;
-      //      const EdgeIntMap& rev;
       const LengthMap &ol;
       const NodeMap &pot;
     public :
@@ -98,16 +102,26 @@
 
   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. 
     MinCostFlows(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 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.
+    ///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) {
@@ -133,7 +147,7 @@
       for (i=0; i<k; ++i){
 	dijkstra.run(s);
 	if (!dijkstra.reached(t)){
-	  //There are no k paths from s to t
+	  //There are no flow of value k from s to t
 	  break;
 	};
 	
@@ -165,26 +179,34 @@
 
 
 
+    /// Gives back the total weight of the found flow.
 
-    ///This function gives back the total length of the found paths.
+    ///This function gives back the total weight of the found flow.
     ///Assumes that \c run() has been run and nothing changed since then.
     Length totalLength(){
       return total_length;
     }
 
-    ///Returns a const reference to the EdgeMap \c flow. \pre \ref run() must
+    ///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).
+    ///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.
     const PotentialMap &getPotential() const { return potential;}
 
+    /// Checking the complementary slackness optimality criteria
+
     ///This function checks, whether the given solution is optimal
-    ///Running after a \c run() should return with true
-    ///In this "state of the art" this only check optimality, doesn't bother with feasibility
+    ///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.
     ///
-    ///\todo Is this OK here?
     bool checkComplementarySlackness(){
       Length mod_pot;
       Length fl_e;
diff -r 2570784896d8 -r 3577b3db6089 src/hugo/minlengthpaths.h
--- a/src/hugo/minlengthpaths.h	Wed Sep 15 14:38:13 2004 +0000
+++ b/src/hugo/minlengthpaths.h	Thu Sep 16 10:26:14 2004 +0000
@@ -7,8 +7,6 @@
 ///\brief An algorithm for finding k paths of minimal total length.
 
 
-//#include <hugo/dijkstra.h>
-//#include <hugo/graph_wrapper.h>
 #include <hugo/maps.h>
 #include <vector>
 #include <hugo/mincostflows.h>
@@ -18,16 +16,18 @@
 /// \addtogroup flowalgs
 /// @{
 
-  ///\brief Implementation of an algorithm for finding k paths between 2 nodes 
+  ///\brief Implementation of an algorithm for finding k edge-disjoint paths between 2 nodes 
   /// of minimal total length 
   ///
-  /// The class \ref hugo::MinLengthPaths "MinLengthPaths" implements
+  /// The class \ref hugo::MinLengthPaths implements
   /// an algorithm for finding k edge-disjoint paths
   /// from a given source node to a given target node in an
-  /// edge-weighted directed graph having minimal total weigth (length).
+  /// edge-weighted directed graph having minimal total weight (length).
   ///
-  ///\warning It is assumed that the lengths are positive, since the
-  /// general flow-decomposition is not implemented yet.
+  ///\warning Length values should be nonnegative.
+  /// 
+  ///\param Graph The directed graph type the algorithm runs on.
+  ///\param LengthMap The type of the length map (values should be nonnegative).
   ///
   ///\author Attila Bernath
   template <typename Graph, typename LengthMap>
@@ -59,6 +59,10 @@
   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. 
     MinLengthPaths(Graph& _G, LengthMap& _length) : G(_G),
       const1map(1), mincost_flow(_G, _length, const1map){}
 
@@ -67,11 +71,15 @@
     ///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.
+    ///
+    ///\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);
-      
-
+    
 
       //Let's find the paths
       //We put the paths into stl vectors (as an inner representation). 
@@ -111,7 +119,7 @@
     }
 
     
-    ///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
@@ -120,14 +128,14 @@
       return mincost_flow.totalLength();
     }
 
-    ///Return the found flow.
+    ///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;}
 
-    /// Return the optimal dual solution
+    /// Returns the optimal dual solution
     
     ///This function returns a const reference to the NodeMap
     ///\c potential (the dual solution).
@@ -136,12 +144,12 @@
 
     ///Checks whether the complementary slackness holds.
 
-    ///This function checks, whether the given solution is optimal
-    ///Running after a \c run() should return with true
+    ///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.
     ///
-    ///\todo Is this OK here?
     bool checkComplementarySlackness(){
       return mincost_flow.checkComplementarySlackness();
     }
@@ -154,9 +162,13 @@
     ///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 hugo 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){
-      
+
       p.clear();
       if (j>paths.size()-1){
 	return;