Changeset 2581:054566ac0934 in lemon-0.x for lemon/min_cost_flow.h

Timestamp:

02/28/08 03:54:27 (16 years ago)

Author:

Peter Kovacs

Branch:

default

Phase:

public

Convert:

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

Message:

Query improvements in the min cost flow algorithms.

• External flow and potential maps can be used.
• New query functions: flow() and potential().
• CycleCanceling? also provides dual solution (node potentials).
• Doc improvements.

File:

• lemon/min_cost_flow.h (modified) (6 diffs)

lemon/min_cost_flow.h

@@ -44 +44 @@
   ///
   /// 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.
+  /// which can be used exactly the same way.
   /// - \ref CapacityScaling The capacity scaling algorithm.
   /// - \ref CostScaling The cost scaling algorithm.
@@ -61 +59 @@
   /// - 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.
+  /// - The value types of the maps should be convertible to each other.
+  /// - \c CostMap::Value must be signed type.
   ///
   /// \author Peter Kovacs
@@ -71 +66 @@
   template < typename Graph,
              typename LowerMap = typename Graph::template EdgeMap<int>,
-             typename CapacityMap = LowerMap,
+             typename CapacityMap = typename Graph::template EdgeMap<int>,
              typename CostMap = typename Graph::template EdgeMap<int>,
-             typename SupplyMap = typename Graph::template NodeMap
-                                  <typename CapacityMap::Value> >
+             typename SupplyMap = typename Graph::template NodeMap<int> >
   class MinCostFlow :
     public NetworkSimplex< Graph, LowerMap, CapacityMap,
@@ -86 +80 @@
   public:
 
-    /// General constructor of the class (with lower bounds).
+    /// General constructor (with lower bounds).
     MinCostFlow( const Graph &graph,
                  const LowerMap &lower,
@@ -101 +95 @@
       MinCostFlowImpl(graph, capacity, cost, supply) {}
 
-    /// Simple constructor of the class (with lower bounds).
+    /// Simple constructor (with lower bounds).
     MinCostFlow( const Graph &graph,
                  const LowerMap &lower,
@@ -111 +105 @@
                        s, t, flow_value ) {}
 
-    /// Simple constructor of the class (without lower bounds).
+    /// Simple constructor (without lower bounds).
     MinCostFlow( const Graph &graph,
                  const CapacityMap &capacity,