Changeset 860:3577b3db6089 in lemon-0.x for src/hugo/minlengthpaths.h

Timestamp:

09/16/04 12:26:14 (20 years ago)

Author:

athos

Branch:

default

Phase:

public

Convert:

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

Message:

Completed documentation for mincostflows and minlengthpaths.

File:

• src/hugo/minlengthpaths.h (modified) (9 diffs)

src/hugo/minlengthpaths.h

@@ -8 +8 @@
 
 
-//#include <hugo/dijkstra.h>
-//#include <hugo/graph_wrapper.h>
 #include <hugo/maps.h>
 #include <vector>
@@ -19 +17 @@
 /// @{
 
-  ///\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
@@ -60 +60 @@
 
 
+    /// 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){}
@@ -68 +72 @@
     ///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
@@ -112 +120 @@
 
     
-    ///Total length of the paths
+    ///Returns the total length of the paths
     
     ///This function gives back the total length of the found paths.
@@ -121 +129 @@
     }
 
-    ///Return the found flow.
+    ///Returns the found flow.
 
     ///This function returns a const reference to the EdgeMap \c flow.
@@ -128 +136 @@
     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
@@ -137 +145 @@
     ///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();
@@ -155 +163 @@
     ///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){