1.1 --- a/lemon/min_cost_max_flow.h Sun Jan 13 10:26:55 2008 +0000
1.2 +++ b/lemon/min_cost_max_flow.h Sun Jan 13 10:32:14 2008 +0000
1.3 @@ -22,8 +22,7 @@
1.4 /// \ingroup min_cost_flow
1.5 ///
1.6 /// \file
1.7 -/// \brief An efficient algorithm for finding a minimum cost maximum
1.8 -/// flow.
1.9 +/// \brief An efficient algorithm for finding a minimum cost maximum flow.
1.10
1.11 #include <lemon/preflow.h>
1.12 #include <lemon/network_simplex.h>
1.13 @@ -34,68 +33,65 @@
1.14 /// \addtogroup min_cost_flow
1.15 /// @{
1.16
1.17 - /// \brief An efficient algorithm for finding a minimum cost maximum
1.18 - /// flow.
1.19 + /// \brief An efficient algorithm for finding a minimum cost
1.20 + /// maximum flow.
1.21 ///
1.22 - /// \ref lemon::MinCostFlow "MinCostMaxFlow" implements an efficient
1.23 - /// algorithm for finding a maximum flow having minimal total cost
1.24 - /// from a given source node to a given target node in a directed
1.25 - /// graph.
1.26 + /// \ref MinCostMaxFlow implements an efficient algorithm for
1.27 + /// finding a maximum flow having minimal total cost from a given
1.28 + /// source node to a given target node in a directed graph.
1.29 ///
1.30 - /// \note \ref lemon::MinCostMaxFlow "MinCostMaxFlow" uses
1.31 - /// \ref lemon::Preflow "Preflow" algorithm for finding the maximum
1.32 - /// flow value and \ref lemon::NetworkSimplex "NetworkSimplex"
1.33 - /// algorithm for finding a minimum cost flow of that value.
1.34 + /// \note \ref MinCostMaxFlow uses \ref Preflow algorithm for finding
1.35 + /// the maximum flow value and \ref NetworkSimplex algorithm for
1.36 + /// finding a minimum cost flow of that value.
1.37 ///
1.38 /// \param Graph The directed graph type the algorithm runs on.
1.39 /// \param CapacityMap The type of the capacity (upper bound) map.
1.40 /// \param CostMap The type of the cost (length) map.
1.41 ///
1.42 /// \warning
1.43 - /// - Edge capacities and costs should be nonnegative integers.
1.44 - /// However \c CostMap::Value should be signed type.
1.45 + /// - Edge capacities and costs should be non-negative integers.
1.46 + /// However \c CostMap::Value should be signed type.
1.47 ///
1.48 /// \author Peter Kovacs
1.49
1.50 template < typename Graph,
1.51 - typename CapacityMap = typename Graph::template EdgeMap<int>,
1.52 - typename CostMap = typename Graph::template EdgeMap<int> >
1.53 + typename CapacityMap = typename Graph::template EdgeMap<int>,
1.54 + typename CostMap = typename Graph::template EdgeMap<int> >
1.55 class MinCostMaxFlow
1.56 {
1.57 typedef typename Graph::Node Node;
1.58 typedef typename Graph::Edge Edge;
1.59
1.60 typedef typename CapacityMap::Value Capacity;
1.61 + typedef typename CostMap::Value Cost;
1.62 typedef typename Graph::template NodeMap<Capacity> SupplyMap;
1.63 typedef NetworkSimplex< Graph, CapacityMap, CapacityMap,
1.64 - CostMap, SupplyMap >
1.65 + CostMap, SupplyMap >
1.66 MinCostFlowImpl;
1.67
1.68 public:
1.69
1.70 - /// \brief The type of the flow map.
1.71 + /// The type of the flow map.
1.72 typedef typename Graph::template EdgeMap<Capacity> FlowMap;
1.73 - typedef typename CostMap::Value Cost;
1.74
1.75 private:
1.76
1.77 - /// \brief The directed graph the algorithm runs on.
1.78 + /// The directed graph the algorithm runs on.
1.79 const Graph &graph;
1.80 - /// \brief The modified capacity map.
1.81 + /// The modified capacity map.
1.82 const CapacityMap &capacity;
1.83 - /// \brief The cost map.
1.84 + /// The cost map.
1.85 const CostMap &cost;
1.86 - /// \brief The source node.
1.87 + /// The edge map of the found flow.
1.88 + FlowMap flow;
1.89 + /// The source node.
1.90 Node source;
1.91 - /// \brief The target node.
1.92 + /// The target node.
1.93 Node target;
1.94 - /// \brief The edge map of the found flow.
1.95 - FlowMap flow;
1.96
1.97 - typedef Preflow<Graph, CapacityMap> PreflowImpl;
1.98 - /// \brief \ref lemon::Preflow "Preflow" class for finding the
1.99 - /// maximum flow value.
1.100 - PreflowImpl preflow;
1.101 + typedef Preflow<Graph, CapacityMap> MaxFlowImpl;
1.102 + /// \brief \ref Preflow class for finding the maximum flow value.
1.103 + MaxFlowImpl preflow;
1.104
1.105 public:
1.106
1.107 @@ -109,9 +105,9 @@
1.108 /// \param _s The source node.
1.109 /// \param _t The target node.
1.110 MinCostMaxFlow( const Graph &_graph,
1.111 - const CapacityMap &_capacity,
1.112 - const CostMap &_cost,
1.113 - Node _s, Node _t ) :
1.114 + const CapacityMap &_capacity,
1.115 + const CostMap &_cost,
1.116 + Node _s, Node _t ) :
1.117 graph(_graph), capacity(_capacity), cost(_cost),
1.118 source(_s), target(_t), flow(_graph),
1.119 preflow(_graph, _capacity, _s, _t)
1.120 @@ -135,7 +131,7 @@
1.121 Cost totalCost() const {
1.122 Cost c = 0;
1.123 for (typename Graph::EdgeIt e(graph); e != INVALID; ++e)
1.124 - c += flow[e] * cost[e];
1.125 + c += flow[e] * cost[e];
1.126 return c;
1.127 }
1.128
1.129 @@ -144,7 +140,7 @@
1.130 preflow.flowMap(flow);
1.131 preflow.runMinCut();
1.132 MinCostFlowImpl mcf_impl( graph, capacity, cost,
1.133 - source, target, preflow.flowValue() );
1.134 + source, target, preflow.flowValue() );
1.135 mcf_impl.run();
1.136 flow = mcf_impl.flowMap();
1.137 }