Index: lemon/min_cost_flow.h
===================================================================
--- lemon/min_cost_flow.h	(revision 2556)
+++ lemon/min_cost_flow.h	(revision 2576)
@@ -37,31 +37,33 @@
   /// a minimum cost flow.
   ///
-  /// \note \ref MinCostFlow is just an alias for \ref NetworkSimplex,
-  /// which is the most efficient implementation for the minimum cost
-  /// flow problem in the LEMON library according to our benchmark
-  /// tests.
-  ///
-  /// \note There are three implementations for the minimum cost flow
-  /// problem, that can be used exactly the same way.
-  /// - \ref CapacityScaling
-  /// - \ref CycleCanceling
-  /// - \ref NetworkSimplex
-  ///
-  /// \note For the detailed documentation of this class see
+  /// This class is just an alias for \ref NetworkSimplex,
+  /// which is the most efficient algorithm for the minimum cost
+  /// flow problem in LEMON according to our benchmark tests.
+  /// For the detailed documentation of this class see
   /// \ref NetworkSimplex.
   ///
-  /// \param Graph The directed graph type the algorithm runs on.
-  /// \param LowerMap The type of the lower bound map.
-  /// \param CapacityMap The type of the capacity (upper bound) map.
-  /// \param CostMap The type of the cost (length) map.
-  /// \param SupplyMap The type of the supply map.
+  /// There are four implementations for the minimum cost flow problem,
+  /// which can be used exactly the same way except for the fact that
+  /// \ref CycleCanceling does not provide dual solution (node
+  /// potentials) since it is a pure primal method.
+  /// - \ref CapacityScaling The capacity scaling algorithm.
+  /// - \ref CostScaling The cost scaling algorithm.
+  /// - \ref CycleCanceling A cycle-canceling algorithm.
+  /// - \ref NetworkSimplex The network simplex algorithm.
+  ///
+  /// \tparam Graph The directed graph type the algorithm runs on.
+  /// \tparam LowerMap The type of the lower bound map.
+  /// \tparam CapacityMap The type of the capacity (upper bound) map.
+  /// \tparam CostMap The type of the cost (length) map.
+  /// \tparam SupplyMap The type of the supply map.
   ///
   /// \warning
-  /// - Edge capacities and costs should be non-negative integers.
-  ///   However \c CostMap::Value should be signed type.
-  /// - Supply values should be signed integers.
-  /// - \c LowerMap::Value must be convertible to
-  ///   \c CapacityMap::Value and \c CapacityMap::Value must be
-  ///   convertible to \c SupplyMap::Value.
+  /// - Edge capacities and costs should be \e non-negative \e integers.
+  /// - Supply values should be \e signed \e integers.
+  /// - \c LowerMap::Value must be convertible to \c CapacityMap::Value.
+  /// - \c CapacityMap::Value and \c SupplyMap::Value must be
+  ///   convertible to each other.
+  /// - All value types must be convertible to \c CostMap::Value, which
+  ///   must be signed type.
   ///
   /// \author Peter Kovacs
Index: lemon/min_cost_max_flow.h
===================================================================
--- lemon/min_cost_max_flow.h	(revision 2556)
+++ lemon/min_cost_max_flow.h	(revision 2576)
@@ -41,15 +41,20 @@
   /// 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
@@ -65,8 +70,9 @@
     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:
@@ -74,23 +80,25 @@
     /// 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:
@@ -105,20 +113,44 @@
     /// \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;
     }
 
@@ -132,16 +164,6 @@
       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();
     }
 
