Changeset 633:305bd9c56f10 in lemon0.x for src/work/athos/mincostflow.h
 Timestamp:
 05/13/04 18:00:18 (17 years ago)
 Branch:
 default
 Phase:
 public
 Convert:
 svn:c9d7d8f590d60310b91f818b3a526b0e/lemon/trunk@824
 File:

 1 copied
Legend:
 Unmodified
 Added
 Removed

src/work/athos/mincostflow.h
r611 r633 1 1 // * c++ * 2 #ifndef HUGO_MINCOSTFLOW S_H3 #define HUGO_MINCOSTFLOW S_H2 #ifndef HUGO_MINCOSTFLOW_H 3 #define HUGO_MINCOSTFLOW_H 4 4 5 5 ///\ingroup galgs … … 23 23 /// 24 24 /// 25 /// The class \ref hugo::MinCostFlows "MinCostFlows" implements 26 /// an algorithm for finding a flow of value \c k 27 ///(for small values of \c k) having minimal total cost 28 /// from a given source node to a given target node in an 29 /// edgeweighted directed graph having nonnegative integer capacities. 25 /// The class \ref hugo::MinCostFlow "MinCostFlow" implements 26 /// an algorithm for solving the following general minimum cost flow problem> 27 /// 28 /// 29 /// 30 /// \warning It is assumed here that the problem has a feasible solution 31 /// 30 32 /// The range of the length (weight) function is nonnegative reals but 31 33 /// the range of capacity function is the set of nonnegative integers. … … 35 37 /// 36 38 ///\author Attila Bernath 37 template <typename Graph, typename LengthMap, typename CapacityMap>38 class MinCostFlow s{39 template <typename Graph, typename LengthMap, typename SupplyMap> 40 class MinCostFlow { 39 41 40 42 typedef typename LengthMap::ValueType Length; 41 43 42 //Warning: this should be integer type 43 typedef typename CapacityMap::ValueType Capacity;44 45 typedef typename SupplyMap::ValueType Supply; 44 46 45 47 typedef typename Graph::Node Node; … … 83 85 const Graph& G; 84 86 const LengthMap& length; 85 const CapacityMap& capacity;87 const SupplyMap& supply;//supply or demand of nodes 86 88 87 89 … … 92 94 //To store the potentila (dual variables) 93 95 typename Graph::template NodeMap<Length> potential; 94 95 //Container to store found paths 96 //std::vector< std::vector<Edge> > paths; 97 //typedef DirPath<Graph> DPath; 98 //DPath paths; 99 96 //To store excessdeficit values 97 SupplyMap excess; 98 100 99 101 100 Length total_length; … … 105 104 106 105 107 MinCostFlow s(Graph& _G, LengthMap& _length, CapacityMap& _cap) : G(_G),108 length(_length), capacity(_cap), flow(_G), potential(_G){ }106 MinCostFlow(Graph& _G, LengthMap& _length, SupplyMap& _supply) : G(_G), 107 length(_length), supply(_supply), flow(_G), potential(_G){ } 109 108 110 109 … … 116 115 ///\todo May be it does make sense to be able to start with a nonzero 117 116 /// feasible primaldual solution pair as well. 118 int run( Node s, Node t, int k) {117 int run() { 119 118 120 119 //Resetting variables from previous runs … … 124 123 flow.set(e,0); 125 124 } 125 126 //Initial value for delta 127 Supply delta = 0; 126 128 127 129 FOR_EACH_LOC(typename Graph::NodeIt, n, G){ 128 //cout << potential[n]<<endl; 130 if (delta < abs(supply[e])){ 131 delta = abs(supply[e]); 132 } 133 excess.set(n,supply[e]); 134 //Initialize the copy of the Dijkstra potential to zero 129 135 potential.set(n,0); 130 136 } … … 132 138 133 139 134 //We need a residual graph 135 ResGraphType res_graph(G, capacity, flow); 136 137 //Initialize the copy of the Dijkstra potential to zero 138 139 //typename ResGraphType::template NodeMap<Length> potential(res_graph); 140 141 140 //We need a residual graph which is uncapacitated 141 ResGraphType res_graph(G, flow); 142 143 144 142 145 ModLengthMap mod_length(res_graph, length, potential); 143 146 144 147 Dijkstra<ResGraphType, ModLengthMap> dijkstra(res_graph, mod_length); 148 145 149 146 150 int i; … … 152 156 }; 153 157 158 //We have to copy the potential 159 FOR_EACH_LOC(typename ResGraphType::NodeIt, n, res_graph){ 160 potential[n] += dijkstra.distMap()[n]; 161 } 162 163 /* 154 164 { 155 //We have to copy the potential 165 156 166 typename ResGraphType::NodeIt n; 157 167 for ( res_graph.first(n) ; res_graph.valid(n) ; res_graph.next(n) ) { … … 159 169 } 160 170 } 161 171 */ 162 172 163 173 //Augmenting on the sortest path … … 167 177 e = dijkstra.pred(n); 168 178 n = dijkstra.predNode(n); 169 res_graph.augment(e, 1);179 res_graph.augment(e,delta); 170 180 //Let's update the total length 171 181 if (res_graph.forward(e)) … … 226 236 } 227 237 228 /* 229 ///\todo To be implemented later 230 231 ///This function gives back the \c jth path in argument p. 232 ///Assumes that \c run() has been run and nothing changed since then. 233 /// \warning It is assumed that \c p is constructed to be a path of graph \c G. If \c j is greater than the result of previous \c run, then the result here will be an empty path. 234 template<typename DirPath> 235 void getPath(DirPath& p, int j){ 236 p.clear(); 237 typename DirPath::Builder B(p); 238 for(typename std::vector<Edge>::iterator i=paths[j].begin(); 239 i!=paths[j].end(); ++i ){ 240 B.pushBack(*i); 241 } 242 243 B.commit(); 244 } 245 246 */ 247 248 }; //class MinCostFlows 238 239 }; //class MinCostFlow 249 240 250 241 ///@}
Note: See TracChangeset
for help on using the changeset viewer.