1.1 --- a/lemon/min_cost_max_flow.h Mon Feb 18 03:32:06 2008 +0000
1.2 +++ b/lemon/min_cost_max_flow.h Mon Feb 18 03:32:56 2008 +0000
1.3 @@ -40,17 +40,22 @@
1.4 /// finding a maximum flow having minimal total cost from a given
1.5 /// source node to a given target node in a directed graph.
1.6 ///
1.7 - /// \note \ref MinCostMaxFlow uses \ref Preflow algorithm for finding
1.8 - /// the maximum flow value and \ref NetworkSimplex algorithm for
1.9 - /// finding a minimum cost flow of that value.
1.10 + /// \ref MinCostMaxFlow uses \ref Preflow for finding the maximum
1.11 + /// flow value and \ref NetworkSimplex for finding a minimum cost
1.12 + /// flow of that value.
1.13 + /// According to our benchmark tests \ref Preflow is generally the
1.14 + /// most efficient algorithm for the maximum flow problem and
1.15 + /// \ref NetworkSimplex is the most efficient for the minimum cost
1.16 + /// flow problem in LEMON.
1.17 ///
1.18 - /// \param Graph The directed graph type the algorithm runs on.
1.19 - /// \param CapacityMap The type of the capacity (upper bound) map.
1.20 - /// \param CostMap The type of the cost (length) map.
1.21 + /// \tparam Graph The directed graph type the algorithm runs on.
1.22 + /// \tparam CapacityMap The type of the capacity (upper bound) map.
1.23 + /// \tparam CostMap The type of the cost (length) map.
1.24 ///
1.25 /// \warning
1.26 - /// - Edge capacities and costs should be non-negative integers.
1.27 - /// However \c CostMap::Value should be signed type.
1.28 + /// - Edge capacities and costs should be \e non-negative \e integers.
1.29 + /// However \c CostMap::Value must be signed type.
1.30 + /// - \c CapacityMap::Value must be convertible to \c CostMap::Value.
1.31 ///
1.32 /// \author Peter Kovacs
1.33
1.34 @@ -64,34 +69,37 @@
1.35
1.36 typedef typename CapacityMap::Value Capacity;
1.37 typedef typename CostMap::Value Cost;
1.38 - typedef typename Graph::template NodeMap<Capacity> SupplyMap;
1.39 + typedef typename Graph::template NodeMap<Cost> SupplyMap;
1.40 +
1.41 + typedef Preflow<Graph, CapacityMap> MaxFlowImpl;
1.42 typedef NetworkSimplex< Graph, CapacityMap, CapacityMap,
1.43 - CostMap, SupplyMap >
1.44 - MinCostFlowImpl;
1.45 + CostMap, SupplyMap > MinCostFlowImpl;
1.46
1.47 public:
1.48
1.49 /// The type of the flow map.
1.50 typedef typename Graph::template EdgeMap<Capacity> FlowMap;
1.51 + /// The type of the potential map.
1.52 + typedef typename Graph::template NodeMap<Cost> PotentialMap;
1.53
1.54 private:
1.55
1.56 - /// The directed graph the algorithm runs on.
1.57 - const Graph &graph;
1.58 - /// The modified capacity map.
1.59 - const CapacityMap &capacity;
1.60 - /// The cost map.
1.61 - const CostMap &cost;
1.62 - /// The edge map of the found flow.
1.63 - FlowMap flow;
1.64 - /// The source node.
1.65 - Node source;
1.66 - /// The target node.
1.67 - Node target;
1.68 + // The directed graph the algorithm runs on
1.69 + const Graph &_graph;
1.70 + // The modified capacity map
1.71 + const CapacityMap &_capacity;
1.72 + // The cost map
1.73 + const CostMap &_cost;
1.74
1.75 - typedef Preflow<Graph, CapacityMap> MaxFlowImpl;
1.76 - /// \brief \ref Preflow class for finding the maximum flow value.
1.77 - MaxFlowImpl preflow;
1.78 + // Edge map of the found flow
1.79 + FlowMap _flow;
1.80 + // Node map of the found potentials
1.81 + PotentialMap _potential;
1.82 +
1.83 + // The source node
1.84 + Node _source;
1.85 + // The target node
1.86 + Node _target;
1.87
1.88 public:
1.89
1.90 @@ -104,22 +112,46 @@
1.91 /// \param _cost The cost (length) values of the edges.
1.92 /// \param _s The source node.
1.93 /// \param _t The target node.
1.94 - MinCostMaxFlow( const Graph &_graph,
1.95 - const CapacityMap &_capacity,
1.96 - const CostMap &_cost,
1.97 - Node _s, Node _t ) :
1.98 - graph(_graph), capacity(_capacity), cost(_cost),
1.99 - source(_s), target(_t), flow(_graph),
1.100 - preflow(_graph, _capacity, _s, _t)
1.101 + MinCostMaxFlow( const Graph &graph,
1.102 + const CapacityMap &capacity,
1.103 + const CostMap &cost,
1.104 + Node s, Node t ) :
1.105 + _graph(graph), _capacity(capacity), _cost(cost), _flow(graph),
1.106 + _potential(graph), _source(s), _target(t)
1.107 {}
1.108
1.109 - /// \brief Returns a const reference to the flow map.
1.110 + /// \brief Runs the algorithm.
1.111 ///
1.112 - /// Returns a const reference to the flow map.
1.113 + /// Runs the algorithm.
1.114 + void run() {
1.115 + MaxFlowImpl preflow(_graph, _capacity, _source, _target);
1.116 + preflow.flowMap(_flow).runMinCut();
1.117 + MinCostFlowImpl mcf( _graph, _capacity, _cost,
1.118 + _source, _target, preflow.flowValue() );
1.119 + mcf.run();
1.120 + _flow = mcf.flowMap();
1.121 + _potential = mcf.potentialMap();
1.122 + }
1.123 +
1.124 + /// \brief Returns a const reference to the edge map storing the
1.125 + /// found flow.
1.126 + ///
1.127 + /// Returns a const reference to the edge map storing the found flow.
1.128 ///
1.129 /// \pre \ref run() must be called before using this function.
1.130 const FlowMap& flowMap() const {
1.131 - return flow;
1.132 + return _flow_result;
1.133 + }
1.134 +
1.135 + /// \brief Returns a const reference to the node map storing the
1.136 + /// found potentials (the dual solution).
1.137 + ///
1.138 + /// Returns a const reference to the node map storing the found
1.139 + /// potentials (the dual solution).
1.140 + ///
1.141 + /// \pre \ref run() must be called before using this function.
1.142 + const PotentialMap& potentialMap() const {
1.143 + return _potential_result;
1.144 }
1.145
1.146 /// \brief Returns the total cost of the found flow.
1.147 @@ -131,20 +163,10 @@
1.148 Cost totalCost() const {
1.149 Cost c = 0;
1.150 for (typename Graph::EdgeIt e(graph); e != INVALID; ++e)
1.151 - c += flow[e] * cost[e];
1.152 + c += _flow[e] * _cost[e];
1.153 return c;
1.154 }
1.155
1.156 - /// \brief Runs the algorithm.
1.157 - void run() {
1.158 - preflow.flowMap(flow);
1.159 - preflow.runMinCut();
1.160 - MinCostFlowImpl mcf_impl( graph, capacity, cost,
1.161 - source, target, preflow.flowValue() );
1.162 - mcf_impl.run();
1.163 - flow = mcf_impl.flowMap();
1.164 - }
1.165 -
1.166 }; //class MinCostMaxFlow
1.167
1.168 ///@}