Changeset 2556:74c2c81055e1 in lemon-0.x for lemon/min_cost_max_flow.h

Timestamp:

01/13/08 11:32:14 (16 years ago)

Author:

Peter Kovacs

Branch:

default

Phase:

public

Convert:

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

Message:

Cleanup in the minimum cost flow files.
The changes only affects the documentation and the look of the source codes.

File:

• lemon/min_cost_max_flow.h (modified) (7 diffs)

lemon/min_cost_max_flow.h

@@ -23 +23 @@
 ///
 /// \file
-/// \brief An efficient algorithm for finding a minimum cost maximum
-/// flow.
+/// \brief An efficient algorithm for finding a minimum cost maximum flow.
 
 #include <lemon/preflow.h>
@@ -35 +34 @@
   /// @{
 
-  /// \brief An efficient algorithm for finding a minimum cost maximum
-  /// flow.
+  /// \brief An efficient algorithm for finding a minimum cost
+  /// maximum flow.
   ///
-  /// \ref lemon::MinCostFlow "MinCostMaxFlow" implements an efficient
-  /// algorithm for finding a maximum flow having minimal total cost
-  /// from a given source node to a given target node in a directed
-  /// graph.
+  /// \ref MinCostMaxFlow implements an efficient algorithm for
+  /// finding a maximum flow having minimal total cost from a given
+  /// source node to a given target node in a directed graph.
   ///
-  /// \note \ref lemon::MinCostMaxFlow "MinCostMaxFlow" uses
-  /// \ref lemon::Preflow "Preflow" algorithm for finding the maximum
-  /// flow value and \ref lemon::NetworkSimplex "NetworkSimplex" 
-  /// algorithm for finding a minimum cost flow of that value.
+  /// \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.
   ///
   /// \param Graph The directed graph type the algorithm runs on.
@@ -53 +50 @@
   ///
   /// \warning
-  /// - Edge capacities and costs should be nonnegative integers.
-  ///   However \c CostMap::Value should be signed type.
+  /// - Edge capacities and costs should be non-negative integers.
+  ///   However \c CostMap::Value should be signed type.
   ///
   /// \author Peter Kovacs
 
   template < typename Graph,
-             typename CapacityMap = typename Graph::template EdgeMap<int>,
-             typename CostMap = typename Graph::template EdgeMap<int> >
+             typename CapacityMap = typename Graph::template EdgeMap<int>,
+             typename CostMap = typename Graph::template EdgeMap<int> >
   class MinCostMaxFlow
   {
@@ -67 +64 @@
 
     typedef typename CapacityMap::Value Capacity;
+    typedef typename CostMap::Value Cost;
     typedef typename Graph::template NodeMap<Capacity> SupplyMap;
     typedef NetworkSimplex< Graph, CapacityMap, CapacityMap,
-                            CostMap, SupplyMap >
+                            CostMap, SupplyMap >
       MinCostFlowImpl;
 
   public:
 
-    /// \brief The type of the flow map.
+    /// The type of the flow map.
     typedef typename Graph::template EdgeMap<Capacity> FlowMap;
-    typedef typename CostMap::Value Cost;
 
   private:
 
-    /// \brief The directed graph the algorithm runs on.
+    /// The directed graph the algorithm runs on.
     const Graph &graph;
-    /// \brief The modified capacity map.
+    /// The modified capacity map.
     const CapacityMap &capacity;
-    /// \brief The cost map.
+    /// The cost map.
     const CostMap &cost;
-    /// \brief The source node.
+    /// The edge map of the found flow.
+    FlowMap flow;
+    /// The source node.
     Node source;
-    /// \brief The target node.
+    /// The target node.
     Node target;
-    /// \brief The edge map of the found flow.
-    FlowMap flow;
 
-    typedef Preflow<Graph, CapacityMap> PreflowImpl;
-    /// \brief \ref lemon::Preflow "Preflow" class for finding the
-    /// maximum flow value.
-    PreflowImpl preflow;
+    typedef Preflow<Graph, CapacityMap> MaxFlowImpl;
+    /// \brief \ref Preflow class for finding the maximum flow value.
+    MaxFlowImpl preflow;
 
   public:
@@ -110 +106 @@
     /// \param _t The target node.
     MinCostMaxFlow( const Graph &_graph,
-                    const CapacityMap &_capacity,
-                    const CostMap &_cost,
-                    Node _s, Node _t ) :
+                    const CapacityMap &_capacity,
+                    const CostMap &_cost,
+                    Node _s, Node _t ) :
       graph(_graph), capacity(_capacity), cost(_cost),
       source(_s), target(_t), flow(_graph),
@@ -136 +132 @@
       Cost c = 0;
       for (typename Graph::EdgeIt e(graph); e != INVALID; ++e)
-        c += flow[e] * cost[e];
+        c += flow[e] * cost[e];
       return c;
     }
@@ -145 +141 @@
       preflow.runMinCut();
       MinCostFlowImpl mcf_impl( graph, capacity, cost,
-                                source, target, preflow.flowValue() );
+                                source, target, preflow.flowValue() );
       mcf_impl.run();
       flow = mcf_impl.flowMap();