Changeset 2576:ae092c63d3ba in lemon-0.x for lemon/min_cost_max_flow.h
- Timestamp:
- 02/18/08 04:32:56 (16 years ago)
- Branch:
- default
- Phase:
- public
- Convert:
- svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@3458
- File:
-
- 1 edited
Legend:
- Unmodified
- Added
- Removed
-
lemon/min_cost_max_flow.h
r2556 r2576 41 41 /// source node to a given target node in a directed graph. 42 42 /// 43 /// \note \ref MinCostMaxFlow uses \ref Preflow algorithm for finding 44 /// the maximum flow value and \ref NetworkSimplex algorithm for 45 /// finding a minimum cost flow of that value. 43 /// \ref MinCostMaxFlow uses \ref Preflow for finding the maximum 44 /// flow value and \ref NetworkSimplex for finding a minimum cost 45 /// flow of that value. 46 /// According to our benchmark tests \ref Preflow is generally the 47 /// most efficient algorithm for the maximum flow problem and 48 /// \ref NetworkSimplex is the most efficient for the minimum cost 49 /// flow problem in LEMON. 46 50 /// 47 /// \ param Graph The directed graph type the algorithm runs on.48 /// \ param CapacityMap The type of the capacity (upper bound) map.49 /// \ param CostMap The type of the cost (length) map.51 /// \tparam Graph The directed graph type the algorithm runs on. 52 /// \tparam CapacityMap The type of the capacity (upper bound) map. 53 /// \tparam CostMap The type of the cost (length) map. 50 54 /// 51 55 /// \warning 52 /// - Edge capacities and costs should be non-negative integers. 53 /// However \c CostMap::Value should be signed type. 56 /// - Edge capacities and costs should be \e non-negative \e integers. 57 /// However \c CostMap::Value must be signed type. 58 /// - \c CapacityMap::Value must be convertible to \c CostMap::Value. 54 59 /// 55 60 /// \author Peter Kovacs … … 65 70 typedef typename CapacityMap::Value Capacity; 66 71 typedef typename CostMap::Value Cost; 67 typedef typename Graph::template NodeMap<Capacity> SupplyMap; 72 typedef typename Graph::template NodeMap<Cost> SupplyMap; 73 74 typedef Preflow<Graph, CapacityMap> MaxFlowImpl; 68 75 typedef NetworkSimplex< Graph, CapacityMap, CapacityMap, 69 CostMap, SupplyMap > 70 MinCostFlowImpl; 76 CostMap, SupplyMap > MinCostFlowImpl; 71 77 72 78 public: … … 74 80 /// The type of the flow map. 75 81 typedef typename Graph::template EdgeMap<Capacity> FlowMap; 82 /// The type of the potential map. 83 typedef typename Graph::template NodeMap<Cost> PotentialMap; 76 84 77 85 private: 78 86 79 /// The directed graph the algorithm runs on. 80 const Graph &graph; 81 /// The modified capacity map. 82 const CapacityMap &capacity; 83 /// The cost map. 84 const CostMap &cost; 85 /// The edge map of the found flow. 86 FlowMap flow; 87 /// The source node. 88 Node source; 89 /// The target node. 90 Node target; 87 // The directed graph the algorithm runs on 88 const Graph &_graph; 89 // The modified capacity map 90 const CapacityMap &_capacity; 91 // The cost map 92 const CostMap &_cost; 91 93 92 typedef Preflow<Graph, CapacityMap> MaxFlowImpl; 93 /// \brief \ref Preflow class for finding the maximum flow value. 94 MaxFlowImpl preflow; 94 // Edge map of the found flow 95 FlowMap _flow; 96 // Node map of the found potentials 97 PotentialMap _potential; 98 99 // The source node 100 Node _source; 101 // The target node 102 Node _target; 95 103 96 104 public: … … 105 113 /// \param _s The source node. 106 114 /// \param _t The target node. 107 MinCostMaxFlow( const Graph &_graph, 108 const CapacityMap &_capacity, 109 const CostMap &_cost, 110 Node _s, Node _t ) : 111 graph(_graph), capacity(_capacity), cost(_cost), 112 source(_s), target(_t), flow(_graph), 113 preflow(_graph, _capacity, _s, _t) 115 MinCostMaxFlow( const Graph &graph, 116 const CapacityMap &capacity, 117 const CostMap &cost, 118 Node s, Node t ) : 119 _graph(graph), _capacity(capacity), _cost(cost), _flow(graph), 120 _potential(graph), _source(s), _target(t) 114 121 {} 115 122 116 /// \brief R eturns a const reference to the flow map.123 /// \brief Runs the algorithm. 117 124 /// 118 /// Returns a const reference to the flow map. 125 /// Runs the algorithm. 126 void run() { 127 MaxFlowImpl preflow(_graph, _capacity, _source, _target); 128 preflow.flowMap(_flow).runMinCut(); 129 MinCostFlowImpl mcf( _graph, _capacity, _cost, 130 _source, _target, preflow.flowValue() ); 131 mcf.run(); 132 _flow = mcf.flowMap(); 133 _potential = mcf.potentialMap(); 134 } 135 136 /// \brief Returns a const reference to the edge map storing the 137 /// found flow. 138 /// 139 /// Returns a const reference to the edge map storing the found flow. 119 140 /// 120 141 /// \pre \ref run() must be called before using this function. 121 142 const FlowMap& flowMap() const { 122 return flow; 143 return _flow_result; 144 } 145 146 /// \brief Returns a const reference to the node map storing the 147 /// found potentials (the dual solution). 148 /// 149 /// Returns a const reference to the node map storing the found 150 /// potentials (the dual solution). 151 /// 152 /// \pre \ref run() must be called before using this function. 153 const PotentialMap& potentialMap() const { 154 return _potential_result; 123 155 } 124 156 … … 132 164 Cost c = 0; 133 165 for (typename Graph::EdgeIt e(graph); e != INVALID; ++e) 134 c += flow[e] *cost[e];166 c += _flow[e] * _cost[e]; 135 167 return c; 136 }137 138 /// \brief Runs the algorithm.139 void run() {140 preflow.flowMap(flow);141 preflow.runMinCut();142 MinCostFlowImpl mcf_impl( graph, capacity, cost,143 source, target, preflow.flowValue() );144 mcf_impl.run();145 flow = mcf_impl.flowMap();146 168 } 147 169
Note: See TracChangeset
for help on using the changeset viewer.