diff -r e866e288cba6 -r ae092c63d3ba lemon/min_cost_max_flow.h
--- a/lemon/min_cost_max_flow.h	Mon Feb 18 03:32:06 2008 +0000
+++ b/lemon/min_cost_max_flow.h	Mon Feb 18 03:32:56 2008 +0000
@@ -40,17 +40,22 @@
   /// finding a maximum flow having minimal total cost from a given
   /// source node to a given target node in a directed graph.
   ///
-  /// \note \ref MinCostMaxFlow uses \ref Preflow algorithm for finding
-  /// the maximum flow value and \ref NetworkSimplex algorithm for
-  /// finding a minimum cost flow of that value.
+  /// \ref MinCostMaxFlow uses \ref Preflow for finding the maximum
+  /// flow value and \ref NetworkSimplex for finding a minimum cost
+  /// flow of that value.
+  /// According to our benchmark tests \ref Preflow is generally the
+  /// most efficient algorithm for the maximum flow problem and
+  /// \ref NetworkSimplex is the most efficient for the minimum cost
+  /// flow problem in LEMON.
   ///
-  /// \param Graph The directed graph type the algorithm runs on.
-  /// \param CapacityMap The type of the capacity (upper bound) map.
-  /// \param CostMap The type of the cost (length) map.
+  /// \tparam Graph The directed graph type the algorithm runs on.
+  /// \tparam CapacityMap The type of the capacity (upper bound) map.
+  /// \tparam CostMap The type of the cost (length) map.
   ///
   /// \warning
-  /// - Edge capacities and costs should be non-negative integers.
-  ///   However \c CostMap::Value should be signed type.
+  /// - Edge capacities and costs should be \e non-negative \e integers.
+  ///   However \c CostMap::Value must be signed type.
+  /// - \c CapacityMap::Value must be convertible to \c CostMap::Value.
   ///
   /// \author Peter Kovacs
 
@@ -64,34 +69,37 @@
 
     typedef typename CapacityMap::Value Capacity;
     typedef typename CostMap::Value Cost;
-    typedef typename Graph::template NodeMap<Capacity> SupplyMap;
+    typedef typename Graph::template NodeMap<Cost> SupplyMap;
+
+    typedef Preflow<Graph, CapacityMap> MaxFlowImpl;
     typedef NetworkSimplex< Graph, CapacityMap, CapacityMap,
-                            CostMap, SupplyMap >
-      MinCostFlowImpl;
+                            CostMap, SupplyMap > MinCostFlowImpl;
 
   public:
 
     /// The type of the flow map.
     typedef typename Graph::template EdgeMap<Capacity> FlowMap;
+    /// The type of the potential map.
+    typedef typename Graph::template NodeMap<Cost> PotentialMap;
 
   private:
 
-    /// The directed graph the algorithm runs on.
-    const Graph &graph;
-    /// The modified capacity map.
-    const CapacityMap &capacity;
-    /// The cost map.
-    const CostMap &cost;
-    /// The edge map of the found flow.
-    FlowMap flow;
-    /// The source node.
-    Node source;
-    /// The target node.
-    Node target;
+    // The directed graph the algorithm runs on
+    const Graph &_graph;
+    // The modified capacity map
+    const CapacityMap &_capacity;
+    // The cost map
+    const CostMap &_cost;
 
-    typedef Preflow<Graph, CapacityMap> MaxFlowImpl;
-    /// \brief \ref Preflow class for finding the maximum flow value.
-    MaxFlowImpl preflow;
+    // Edge map of the found flow
+    FlowMap _flow;
+    // Node map of the found potentials
+    PotentialMap _potential;
+
+    // The source node
+    Node _source;
+    // The target node
+    Node _target;
 
   public:
 
@@ -104,22 +112,46 @@
     /// \param _cost The cost (length) values of the edges.
     /// \param _s The source node.
     /// \param _t The target node.
-    MinCostMaxFlow( const Graph &_graph,
-                    const CapacityMap &_capacity,
-                    const CostMap &_cost,
-                    Node _s, Node _t ) :
-      graph(_graph), capacity(_capacity), cost(_cost),
-      source(_s), target(_t), flow(_graph),
-      preflow(_graph, _capacity, _s, _t)
+    MinCostMaxFlow( const Graph &graph,
+                    const CapacityMap &capacity,
+                    const CostMap &cost,
+                    Node s, Node t ) :
+      _graph(graph), _capacity(capacity), _cost(cost), _flow(graph),
+      _potential(graph), _source(s), _target(t)
     {}
 
-    /// \brief Returns a const reference to the flow map.
+    /// \brief Runs the algorithm.
     ///
-    /// Returns a const reference to the flow map.
+    /// Runs the algorithm.
+    void run() {
+      MaxFlowImpl preflow(_graph, _capacity, _source, _target);
+      preflow.flowMap(_flow).runMinCut();
+      MinCostFlowImpl mcf( _graph, _capacity, _cost,
+                           _source, _target, preflow.flowValue() );
+      mcf.run();
+      _flow = mcf.flowMap();
+      _potential = mcf.potentialMap();
+    }
+
+    /// \brief Returns a const reference to the edge map storing the
+    /// found flow.
+    ///
+    /// Returns a const reference to the edge map storing the found flow.
     ///
     /// \pre \ref run() must be called before using this function.
     const FlowMap& flowMap() const {
-      return flow;
+      return _flow_result;
+    }
+
+    /// \brief Returns a const reference to the node map storing the
+    /// found potentials (the dual solution).
+    ///
+    /// Returns a const reference to the node map storing the found
+    /// potentials (the dual solution).
+    ///
+    /// \pre \ref run() must be called before using this function.
+    const PotentialMap& potentialMap() const {
+      return _potential_result;
     }
 
     /// \brief Returns the total cost of the found flow.
@@ -131,20 +163,10 @@
     Cost totalCost() const {
       Cost c = 0;
       for (typename Graph::EdgeIt e(graph); e != INVALID; ++e)
-        c += flow[e] * cost[e];
+        c += _flow[e] * _cost[e];
       return c;
     }
 
-    /// \brief Runs the algorithm.
-    void run() {
-      preflow.flowMap(flow);
-      preflow.runMinCut();
-      MinCostFlowImpl mcf_impl( graph, capacity, cost,
-                                source, target, preflow.flowValue() );
-      mcf_impl.run();
-      flow = mcf_impl.flowMap();
-    }
-
   }; //class MinCostMaxFlow
 
   ///@}