Changeset 523:4da6fb104664 in lemon-0.x for src

Timestamp:

05/04/04 14:00:13 (19 years ago)

Author:

athos

Branch:

default

Phase:

public

Convert:

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

Message:

Started.

File:

• src/work/athos/mincostflows.h (copied) (copied from src/work/athos/minlengthpaths.h) (2 diffs)

src/work/athos/mincostflows.h

@@ -1 +1 @@
 // -*- c++ -*-
-#ifndef HUGO_MINLENGTHPATHS_H
-#define HUGO_MINLENGTHPATHS_H
+#ifndef HUGO_MINCOSTFLOWS_H
+#define HUGO_MINCOSTFLOWS_H
 
 ///\ingroup galgs
 ///\file
-///\brief An algorithm for finding k paths of minimal total length.
+///\brief An algorithm for finding a flow of value \c k (for small values of \c k) having minimal total cost 
 
 #include <iostream>
@@ -19 +19 @@
 /// @{
 
-  ///\brief Implementation of an algorithm for finding k paths between 2 nodes 
-  /// of minimal total length 
+  ///\brief Implementation of an algorithm for finding a flow of value \c k 
+  ///(for small values of \c k) having minimal total cost between 2 nodes 
+  /// 
   ///
-  /// The class \ref hugo::MinLengthPaths "MinLengthPaths" implements
-  /// an algorithm for finding k edge-disjoint paths
+  /// 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  
   /// 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 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.
   ///
   ///\author Attila Bernath
   template <typename Graph, typename LengthMap>
-  class MinLengthPaths {
+  class MinCostFlows {
 
     typedef typename LengthMap::ValueType Length;