Changeset 2556:74c2c81055e1 in lemon-0.x for lemon/min_cost_max_flow.h
- Timestamp:
- 01/13/08 11:32:14 (16 years ago)
- Branch:
- default
- Phase:
- public
- Convert:
- svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@3437
- File:
-
- 1 edited
Legend:
- Unmodified
- Added
- Removed
-
lemon/min_cost_max_flow.h
r2553 r2556 23 23 /// 24 24 /// \file 25 /// \brief An efficient algorithm for finding a minimum cost maximum 26 /// flow. 25 /// \brief An efficient algorithm for finding a minimum cost maximum flow. 27 26 28 27 #include <lemon/preflow.h> … … 35 34 /// @{ 36 35 37 /// \brief An efficient algorithm for finding a minimum cost maximum38 /// flow.36 /// \brief An efficient algorithm for finding a minimum cost 37 /// maximum flow. 39 38 /// 40 /// \ref lemon::MinCostFlow "MinCostMaxFlow" implements an efficient 41 /// algorithm for finding a maximum flow having minimal total cost 42 /// from a given source node to a given target node in a directed 43 /// graph. 39 /// \ref MinCostMaxFlow implements an efficient algorithm for 40 /// finding a maximum flow having minimal total cost from a given 41 /// source node to a given target node in a directed graph. 44 42 /// 45 /// \note \ref lemon::MinCostMaxFlow "MinCostMaxFlow" uses 46 /// \ref lemon::Preflow "Preflow" algorithm for finding the maximum 47 /// flow value and \ref lemon::NetworkSimplex "NetworkSimplex" 48 /// algorithm for finding a minimum cost flow of that value. 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. 49 46 /// 50 47 /// \param Graph The directed graph type the algorithm runs on. … … 53 50 /// 54 51 /// \warning 55 /// - Edge capacities and costs should be non negative integers.56 /// 52 /// - Edge capacities and costs should be non-negative integers. 53 /// However \c CostMap::Value should be signed type. 57 54 /// 58 55 /// \author Peter Kovacs 59 56 60 57 template < typename Graph, 61 62 58 typename CapacityMap = typename Graph::template EdgeMap<int>, 59 typename CostMap = typename Graph::template EdgeMap<int> > 63 60 class MinCostMaxFlow 64 61 { … … 67 64 68 65 typedef typename CapacityMap::Value Capacity; 66 typedef typename CostMap::Value Cost; 69 67 typedef typename Graph::template NodeMap<Capacity> SupplyMap; 70 68 typedef NetworkSimplex< Graph, CapacityMap, CapacityMap, 71 69 CostMap, SupplyMap > 72 70 MinCostFlowImpl; 73 71 74 72 public: 75 73 76 /// \briefThe type of the flow map.74 /// The type of the flow map. 77 75 typedef typename Graph::template EdgeMap<Capacity> FlowMap; 78 typedef typename CostMap::Value Cost;79 76 80 77 private: 81 78 82 /// \briefThe directed graph the algorithm runs on.79 /// The directed graph the algorithm runs on. 83 80 const Graph &graph; 84 /// \briefThe modified capacity map.81 /// The modified capacity map. 85 82 const CapacityMap &capacity; 86 /// \briefThe cost map.83 /// The cost map. 87 84 const CostMap &cost; 88 /// \brief The source node. 85 /// The edge map of the found flow. 86 FlowMap flow; 87 /// The source node. 89 88 Node source; 90 /// \briefThe target node.89 /// The target node. 91 90 Node target; 92 /// \brief The edge map of the found flow.93 FlowMap flow;94 91 95 typedef Preflow<Graph, CapacityMap> PreflowImpl; 96 /// \brief \ref lemon::Preflow "Preflow" class for finding the 97 /// maximum flow value. 98 PreflowImpl preflow; 92 typedef Preflow<Graph, CapacityMap> MaxFlowImpl; 93 /// \brief \ref Preflow class for finding the maximum flow value. 94 MaxFlowImpl preflow; 99 95 100 96 public: … … 110 106 /// \param _t The target node. 111 107 MinCostMaxFlow( const Graph &_graph, 112 113 114 108 const CapacityMap &_capacity, 109 const CostMap &_cost, 110 Node _s, Node _t ) : 115 111 graph(_graph), capacity(_capacity), cost(_cost), 116 112 source(_s), target(_t), flow(_graph), … … 136 132 Cost c = 0; 137 133 for (typename Graph::EdgeIt e(graph); e != INVALID; ++e) 138 134 c += flow[e] * cost[e]; 139 135 return c; 140 136 } … … 145 141 preflow.runMinCut(); 146 142 MinCostFlowImpl mcf_impl( graph, capacity, cost, 147 143 source, target, preflow.flowValue() ); 148 144 mcf_impl.run(); 149 145 flow = mcf_impl.flowMap();
Note: See TracChangeset
for help on using the changeset viewer.