Changeset 661:d306e777117e in lemon0.x for src/work/athos/mincostflow.h
 Timestamp:
 05/25/04 17:11:11 (20 years ago)
 Branch:
 default
 Phase:
 public
 Convert:
 svn:c9d7d8f590d60310b91f818b3a526b0e/lemon/trunk@864
 File:

 1 edited
Legend:
 Unmodified
 Added
 Removed

src/work/athos/mincostflow.h
r659 r661 12 12 #include <vector> 13 13 #include <list> 14 #include < for_each_macros.h>15 #include <hugo/union _find.h>14 #include <hugo/for_each_macros.h> 15 #include <hugo/unionfind.h> 16 16 17 17 namespace hugo { … … 20 20 /// @{ 21 21 22 ///\brief Implementation of an algorithm for finding the minimum cost flow23 /// of given valuein an uncapacitated network22 ///\brief Implementation of an algorithm for solving the minimum cost general 23 /// flow problem in an uncapacitated network 24 24 /// 25 25 /// … … 31 31 /// \warning It is assumed here that the problem has a feasible solution 32 32 /// 33 /// The range of the length(weight) function is nonnegative reals but33 /// The range of the cost (weight) function is nonnegative reals but 34 34 /// the range of capacity function is the set of nonnegative integers. 35 35 /// It is not a polinomial time algorithm for counting the minimum cost … … 38 38 /// 39 39 ///\author Attila Bernath 40 template <typename Graph, typename LengthMap, typename SupplyDemandMap>40 template <typename Graph, typename CostMap, typename SupplyDemandMap> 41 41 class MinCostFlow { 42 42 43 typedef typename LengthMap::ValueType Length;43 typedef typename CostMap::ValueType Cost; 44 44 45 45 … … 50 50 typedef typename Graph::Edge Edge; 51 51 typedef typename Graph::OutEdgeIt OutEdgeIt; 52 typedef typename Graph::template EdgeMap<int> EdgeIntMap; 52 typedef typename Graph::template EdgeMap<SupplyDemand> FlowMap; 53 typedef ConstMap<Edge,SupplyDemand> ConstEdgeMap; 53 54 54 55 // typedef ConstMap<Edge,int> ConstMap; 55 56 56 typedef ResGraphWrapper<const Graph,int,C apacityMap,EdgeIntMap> ResGraphType;57 typedef typename ResGraph Type::Edge ResGraphEdge;58 59 class Mod LengthMap {60 //typedef typename ResGraph Type::template NodeMap<Length> NodeMap;61 typedef typename Graph::template NodeMap< Length> NodeMap;62 const ResGraph Type& res_graph;57 typedef ResGraphWrapper<const Graph,int,ConstEdgeMap,FlowMap> ResGraph; 58 typedef typename ResGraph::Edge ResGraphEdge; 59 60 class ModCostMap { 61 //typedef typename ResGraph::template NodeMap<Cost> NodeMap; 62 typedef typename Graph::template NodeMap<Cost> NodeMap; 63 const ResGraph& res_graph; 63 64 // const EdgeIntMap& rev; 64 const LengthMap &ol;65 const CostMap &ol; 65 66 const NodeMap &pot; 66 67 public : 67 typedef typename LengthMap::KeyType KeyType;68 typedef typename LengthMap::ValueType ValueType;68 typedef typename CostMap::KeyType KeyType; 69 typedef typename CostMap::ValueType ValueType; 69 70 70 ValueType operator[](typename ResGraph Type::Edge e) const {71 ValueType operator[](typename ResGraph::Edge e) const { 71 72 if (res_graph.forward(e)) 72 73 return ol[e](pot[res_graph.head(e)]pot[res_graph.tail(e)]); … … 75 76 } 76 77 77 Mod LengthMap(const ResGraphType& _res_graph,78 const LengthMap &o, const NodeMap &p) :78 ModCostMap(const ResGraph& _res_graph, 79 const CostMap &o, const NodeMap &p) : 79 80 res_graph(_res_graph), /*rev(_rev),*/ ol(o), pot(p){}; 80 };//Mod LengthMap81 };//ModCostMap 81 82 82 83 … … 85 86 //Input 86 87 const Graph& graph; 87 const LengthMap& length;88 const CostMap& cost; 88 89 const SupplyDemandMap& supply_demand;//supply or demand of nodes 89 90 … … 92 93 93 94 //To store the flow 94 EdgeIntMap flow;95 FlowMap flow; 95 96 //To store the potentila (dual variables) 96 typename Graph::template NodeMap< Length> potential;97 typename Graph::template NodeMap<Cost> potential; 97 98 //To store excessdeficit values 98 99 SupplyDemandMap excess_deficit; 99 100 100 101 101 Length total_length;102 Cost total_cost; 102 103 103 104 … … 105 106 106 107 107 MinCostFlow(Graph& _graph, LengthMap& _length, SupplyDemandMap& _supply_demand) : graph(_graph),108 length(_length), supply_demand(_supply_demand), flow(_graph), potential(_graph){ }108 MinCostFlow(Graph& _graph, CostMap& _cost, SupplyDemandMap& _supply_demand) : graph(_graph), 109 cost(_cost), supply_demand(_supply_demand), flow(_graph), potential(_graph){ } 109 110 110 111 … … 118 119 119 120 //Resetting variables from previous runs 120 //total_ length= 0;121 //total_cost = 0; 121 122 122 123 typedef typename Graph::template NodeMap<int> HeapMap; … … 176 177 SupplyDemand max_excess = delta; 177 178 178 //ConstMap<Edge,SupplyDemand> ConstEdgeMap; 179 179 ///\bug This is a serious cheat here, before we have an uncapacitated ResGraph 180 ConstEdgeMap const_inf_map(MAX_INT); 181 180 182 //We need a residual graph which is uncapacitated 181 ResGraph Type res_graph(graph, flow);183 ResGraph res_graph(graph, const_inf_map, flow); 182 184 183 185 //An EdgeMap to tell which arcs are abundant … … 196 198 ResAbGraph; 197 199 //Again uncapacitated 198 ResAbGraph res_ab_graph(abundant_graph, flow);200 ResAbGraph res_ab_graph(abundant_graph, const_inf_map, flow); 199 201 200 202 //We need things for the bfs … … 210 212 bfs(res_ab_graph, bfs_reached, bfs_pred, bfs_dist_dummy); 211 213 212 Mod LengthMap mod_length(res_graph, length, potential);213 214 Dijkstra<ResGraph Type, ModLengthMap> dijkstra(res_graph, mod_length);214 ModCostMap mod_cost(res_graph, cost, potential); 215 216 Dijkstra<ResGraph, ModCostMap> dijkstra(res_graph, mod_cost); 215 217 216 218 … … 316 318 317 319 //We have to change the potential 318 FOR_EACH_LOC(typename ResGraph Type::NodeIt, n, res_graph){320 FOR_EACH_LOC(typename ResGraph::NodeIt, n, res_graph){ 319 321 potential[n] += dijkstra.distMap()[n]; 320 322 } … … 329 331 res_graph.augment(e,delta); 330 332 /* 331 //Let's update the total length333 //Let's update the total cost 332 334 if (res_graph.forward(e)) 333 total_ length += length[e];335 total_cost += cost[e]; 334 336 else 335 total_ length = length[e];337 total_cost = cost[e]; 336 338 */ 337 339 } … … 401 403 402 404 403 ///This function gives back the total lengthof the found paths.405 ///This function gives back the total cost of the found paths. 404 406 ///Assumes that \c run() has been run and nothing changed since then. 405 Length totalLength(){406 return total_ length;407 Cost totalCost(){ 408 return total_cost; 407 409 } 408 410 … … 421 423 ///\todo Is this OK here? 422 424 bool checkComplementarySlackness(){ 423 Lengthmod_pot;424 Lengthfl_e;425 Cost mod_pot; 426 Cost fl_e; 425 427 FOR_EACH_LOC(typename Graph::EdgeIt, e, graph){ 426 428 //C^{\Pi}_{i,j} 427 mod_pot = length[e]potential[graph.head(e)]+potential[graph.tail(e)];429 mod_pot = cost[e]potential[graph.head(e)]+potential[graph.tail(e)]; 428 430 fl_e = flow[e]; 429 431 // std::cout << fl_e << std::endl;
Note: See TracChangeset
for help on using the changeset viewer.