Changeset 331:f5461f8bc59b in lemon-0.x for src/work/athos/preflow_push.hh
- Timestamp:
- 04/15/04 19:03:44 (20 years ago)
- Branch:
- default
- Phase:
- public
- Convert:
- svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@449
- File:
-
- 1 edited
Legend:
- Unmodified
- Added
- Removed
-
src/work/athos/preflow_push.hh
r119 r331 1 #ifndef PREFLOW_PUSH_HH2 #define PREFLOW_PUSH_HH3 4 #include <algorithm>1 #ifndef HUGO_PREFLOW_PUSH_HH 2 #define HUGO_PREFLOW_PUSH_HH 3 4 //#include <algorithm> 5 5 #include <list> 6 6 #include <vector> 7 #include <queue> 7 8 //#include "pf_hiba.hh" 8 9 //#include <marci_list_graph.hh> 9 10 //#include <marci_graph_traits.hh> 10 11 #include <reverse_bfs.hh> 11 #include <invalid.h> 12 #include <graph_wrapper.h> 13 //#include <reverse_bfs.hh> 12 14 13 15 using namespace std; … … 15 17 namespace hugo { 16 18 17 template <typename graph_type, typename T>19 template <typename Graph, typename T> 18 20 class preflow_push { 19 21 20 //Hasznos typedef-ek 21 typedef typename graph_type::NodeIt NodeIt; 22 typedef typename graph_type::EdgeIt EdgeIt; 23 typedef typename graph_type::EachNodeIt EachNodeIt; 24 typedef typename graph_type::EachEdgeIt EachEdgeIt; 25 typedef typename graph_type::OutEdgeIt OutEdgeIt; 26 typedef typename graph_type::InEdgeIt InEdgeIt; 27 typedef typename graph_type::SymEdgeIt SymEdgeIt; 28 29 30 31 /* 32 typedef graph_traits<graph_type>::node_iterator node_iterator; 33 typedef graph_traits<graph_type>::EdgeIt EdgeIt; 34 typedef graph_traits<graph_type>::each_node_iterator each_node_iterator; 35 typedef graph_traits<graph_type>::each_EdgeIt each_EdgeIt; 36 typedef graph_traits<graph_type>::out_EdgeIt out_EdgeIt; 37 typedef graph_traits<graph_type>::InEdgeIt InEdgeIt; 38 typedef graph_traits<graph_type>::sym_EdgeIt sym_EdgeIt; 39 */ 22 //Useful typedefs 23 typedef typename Graph::Node Node; 24 typedef typename Graph::NodeIt NodeIt; 25 typedef typename Graph::Edge Edge; 26 typedef typename Graph::OutEdgeIt OutEdgeIt; 27 typedef typename Graph::InEdgeIt InEdgeIt; 28 40 29 41 30 //--------------------------------------------- … … 56 45 private: 57 46 //input 58 graph_type& G;59 Node Its;60 Node Itt;61 typename graph_type::EdgeMap<T> &capacity;62 //typename graph_type::EdgeMap<T> &capacity; 47 Graph& G; 48 Node s; 49 Node t; 50 typename Graph::EdgeMap<T> &capacity; 51 63 52 //output 64 //typename graph_type::EdgeMap<T> 65 typename graph_type::EdgeMap<T> preflow; 53 typename Graph::EdgeMap<T> preflow; 66 54 T maxflow_value; 67 55 68 56 //auxiliary variables for computation 57 //The number of the nodes 69 58 int number_of_nodes; 70 71 72 typename graph_type::NodeMap<int> level; 73 typename graph_type::NodeMap<T> excess; 74 //node_property_vector<graph_type, int> level; 75 //node_property_vector<graph_type, T> excess; 59 //A nodemap for the level 60 typename Graph::NodeMap<int> level; 61 //A nodemap for the excess 62 typename Graph::NodeMap<T> excess; 76 63 77 64 //Number of nodes on each level … … 79 66 80 67 //For the FIFO implementation 81 list<Node It> fifo_nodes;68 list<Node> fifo_nodes; 82 69 //For 'highest label' implementation 83 70 int highest_active; 84 71 //int second_highest_active; 85 vector< list<Node It> > active_nodes;72 vector< list<Node> > active_nodes; 86 73 87 74 public: … … 89 76 //Constructing the object using the graph, source, sink and capacity vector 90 77 preflow_push( 91 graph_type& _G,92 Node It_s,93 Node It_t,94 typename graph_type::EdgeMap<T> & _capacity)78 Graph& _G, 79 Node _s, 80 Node _t, 81 typename Graph::EdgeMap<T> & _capacity) 95 82 : G(_G), s(_s), t(_t), 96 83 capacity(_capacity), … … 115 102 switch(implementation){ 116 103 case impl_highest_label :{ 104 active_nodes.clear(); 117 105 active_nodes.resize(2*number_of_nodes-1); 118 active_nodes.clear();106 119 107 break; 120 108 } … … 128 116 T run(); 129 117 130 typename graph_type::EdgeMap<T> getmaxflow(){118 typename Graph::EdgeMap<T> getmaxflow(){ 131 119 return preflow; 132 120 } … … 136 124 //For testing purposes only 137 125 //Lists the node_properties 138 void write_property_vector(typename graph_type::NodeMap<T> a,139 //node_property_vector< graph_type, T> a,126 void write_property_vector(typename Graph::NodeMap<T> a, 127 //node_property_vector<Graph, T> a, 140 128 char* prop_name="property"){ 141 for( EachNodeIt i=G.template first<EachNodeIt>(); i.valid(); ++i) {142 cout<<"Node id.: "<<G.id(i)<<", "<<prop_name<<" value: "<<a .get(i)<<endl;129 for(NodeIt i=G.template first<NodeIt>(); G.valid(i); G.next(i)) { 130 cout<<"Node id.: "<<G.id(i)<<", "<<prop_name<<" value: "<<a[i]<<endl; 143 131 } 144 132 cout<<endl; … … 146 134 147 135 //Modifies the excess of the node and makes sufficient changes 148 void modify_excess(const Node It& a ,T v){149 T old_value=excess.get(a);150 excess.set(a,old_value+v);136 void modify_excess(const Node& a ,T v){ 137 //T old_value=excess[a]; 138 excess[a] += v; 151 139 } 152 140 … … 155 143 //and maintain the excess on the head and tail 156 144 //Here we do not check whether this is possible or not 157 void modify_preflow(EdgeIt j, const T& v){ 158 159 //Auxiliary variable 160 T old_value; 161 145 void modify_preflow(Edge j, const T& v){ 146 162 147 //Modifiyng the edge 163 old_value=preflow.get(j); 164 preflow.set(j,old_value+v); 148 preflow[j] += v; 165 149 166 150 … … 175 159 //Gives the active node to work with 176 160 //(depending on the implementation to be used) 177 Node Itget_active_node(){161 Node get_active_node(){ 178 162 179 163 … … 181 165 case impl_highest_label : { 182 166 183 //First need to find the highest label for which there "s an active node167 //First need to find the highest label for which there's an active node 184 168 while( highest_active>=0 && active_nodes[highest_active].empty() ){ 185 169 --highest_active; … … 189 173 190 174 191 Node Ita=active_nodes[highest_active].front();175 Node a=active_nodes[highest_active].front(); 192 176 active_nodes[highest_active].pop_front(); 193 177 … … 195 179 } 196 180 else { 197 return NodeIt();181 return INVALID; 198 182 } 199 183 … … 204 188 205 189 if( ! fifo_nodes.empty() ) { 206 Node Ita=fifo_nodes.front();190 Node a=fifo_nodes.front(); 207 191 fifo_nodes.pop_front(); 208 192 return a; 209 193 } 210 194 else { 211 return NodeIt();195 return INVALID; 212 196 } 213 197 break; … … 215 199 } 216 200 // 217 return NodeIt();201 return INVALID; 218 202 } 219 203 220 204 //Puts node 'a' among the active nodes 221 void make_active(const Node It& a){205 void make_active(const Node& a){ 222 206 //s and t never become active 223 207 if (a!=s && a!= t){ 224 208 switch(implementation){ 225 209 case impl_highest_label : 226 active_nodes[level .get(a)].push_back(a);210 active_nodes[level[a]].push_back(a); 227 211 break; 228 212 case impl_fifo : … … 234 218 235 219 //Update highest_active label 236 if (highest_active<level .get(a)){237 highest_active=level .get(a);220 if (highest_active<level[a]){ 221 highest_active=level[a]; 238 222 } 239 223 … … 241 225 242 226 //Changes the level of node a and make sufficent changes 243 void change_level_to(Node Ita, int new_value){244 int seged = level .get(a);227 void change_level_to(Node a, int new_value){ 228 int seged = level[a]; 245 229 level.set(a,new_value); 246 230 --num_of_nodes_on_level[seged]; … … 258 242 //Setting starting preflow, level and excess values to zero 259 243 //This can be important, if the algorithm is run more then once 260 for( EachNodeIt i=G.template first<EachNodeIt>(); i.valid(); ++i) {244 for(NodeIt i=G.template first<NodeIt>(); G.valid(i); G.next(i)) { 261 245 level.set(i,0); 262 246 excess.set(i,0); 263 for(OutEdgeIt j=G.template first<OutEdgeIt>(i); j.valid(); ++j)247 for(OutEdgeIt j=G.template first<OutEdgeIt>(i); G.valid(j); G.next(j)) 264 248 preflow.set(j, 0); 265 249 } … … 274 258 //This is the only part that uses BFS 275 259 //------------------------------------ 260 261 /*Reverse_bfs from t, to find the starting level.*/ 262 //Copyright: Jacint 263 change_level_to(t,0); 264 265 std::queue<Node> bfs_queue; 266 bfs_queue.push(t); 267 268 while (!bfs_queue.empty()) { 269 270 Node v=bfs_queue.front(); 271 bfs_queue.pop(); 272 int l=level[v]+1; 273 274 InEdgeIt e; 275 for(G.first(e,v); G.valid(e); G.next(e)) { 276 Node w=G.tail(e); 277 if ( level[w] == number_of_nodes && w != s ) { 278 bfs_queue.push(w); 279 //Node first=level_list[l]; 280 //if ( G.valid(first) ) left.set(first,w); 281 //right.set(w,first); 282 //level_list[l]=w; 283 change_level_to(w, l); 284 //level.set(w, l); 285 } 286 } 287 } 288 change_level_to(s,number_of_nodes); 289 //level.set(s,number_of_nodes); 290 291 /* 276 292 //Setting starting level values using reverse bfs 277 reverse_bfs< graph_type> rev_bfs(G,t);293 reverse_bfs<Graph> rev_bfs(G,t); 278 294 rev_bfs.run(); 279 295 //write_property_vector(rev_bfs.dist,"rev_bfs"); 280 for( EachNodeIt i=G.template first<EachNodeIt>(); i.valid(); ++i) {296 for(NodeIt i=G.template first<NodeIt>(); G.valid(i); G.next(i)) { 281 297 change_level_to(i,rev_bfs.dist(i)); 282 298 //level.put(i,rev_bfs.dist.get(i)); 283 299 } 300 */ 284 301 //------------------------------------ 285 302 //This is the only part that uses BFS … … 293 310 294 311 //we push as much preflow from s as possible to start with 295 for(OutEdgeIt j=G.template first<OutEdgeIt>(s); j.valid(); ++j){296 modify_preflow(j,capacity .get(j));312 for(OutEdgeIt j=G.template first<OutEdgeIt>(s); G.valid(j); G.next(j)){ 313 modify_preflow(j,capacity[j] ); 297 314 make_active(G.head(j)); 298 int lev=level .get(G.head(j));315 int lev=level[G.head(j)]; 299 316 if(highest_active<lev){ 300 317 highest_active=lev; … … 307 324 //If the preflow is less than the capacity on the given edge 308 325 //then it is an edge in the residual graph 309 bool is_admissible_forward_edge( OutEdgeItj, int& new_level){310 311 if (capacity .get(j)>preflow.get(j)){312 if(level .get(G.tail(j))==level.get(G.head(j))+1){326 bool is_admissible_forward_edge(Edge j, int& new_level){ 327 328 if (capacity[j]>preflow[j]){ 329 if(level[G.tail(j)]==level[G.head(j)]+1){ 313 330 return true; 314 331 } 315 332 else{ 316 if (level .get(G.head(j))< new_level)317 new_level=level .get(G.head(j));333 if (level[G.head(j)] < new_level) 334 new_level=level[G.head(j)]; 318 335 } 319 336 } … … 323 340 //If the preflow is greater than 0 on the given edge 324 341 //then the edge reversd is an edge in the residual graph 325 bool is_admissible_backward_edge( InEdgeItj, int& new_level){326 327 if (0<preflow .get(j)){328 if(level .get(G.tail(j))==level.get(G.head(j))-1){342 bool is_admissible_backward_edge(Edge j, int& new_level){ 343 344 if (0<preflow[j]){ 345 if(level[G.tail(j)]==level[G.head(j)]-1){ 329 346 330 347 return true; 331 348 } 332 349 else{ 333 if (level .get(G.tail(j))< new_level)334 new_level=level .get(G.tail(j));350 if (level[G.tail(j)] < new_level) 351 new_level=level[G.tail(j)]; 335 352 } 336 353 … … 342 359 }; //class preflow_push 343 360 344 template<typename graph_type, typename T> 345 T preflow_push<graph_type, T>::run() { 361 template<typename Graph, typename T> 362 T preflow_push<Graph, T>::run() { 363 364 //We need a residual graph 365 ResGraphType res_graph(G, preflow, capacity); 346 366 347 367 preprocess(); 348 368 //write_property_vector(level,"level"); 349 369 T e,v; 350 NodeIt a; 351 while (a=get_active_node(), a.valid()){ 352 353 //cout<<G.id(a)<<endl; 354 //write_property_vector(excess,"excess"); 355 //write_property_vector(level,"level"); 356 357 370 Node a; 371 while (a=get_active_node(), G.valid(a)){ 372 358 373 bool go_to_next_node=false; 359 e = excess .get(a);374 e = excess[a]; 360 375 while (!go_to_next_node){ 376 361 377 //Initial value for the new level for the active node we are dealing with 362 378 int new_level=2*number_of_nodes; 363 //write_property_vector(excess,"excess"); 364 //write_property_vector(level,"level"); 365 //cout<<G.id(a)<<endl; 379 380 366 381 //Out edges from node a 367 382 { 368 383 OutEdgeIt j=G.template first<OutEdgeIt>(a); 369 while ( j.valid() && e){384 while (G.valid(j) && e){ 370 385 371 386 if (is_admissible_forward_edge(j,new_level)){ 372 v=min(e,capacity .get(j) - preflow.get(j));387 v=min(e,capacity[j] - preflow[j]); 373 388 e -= v; 374 389 //New node might become active 375 if (excess .get(G.head(j))==0){390 if (excess[G.head(j)]==0){ 376 391 make_active(G.head(j)); 377 392 } 378 393 modify_preflow(j,v); 379 394 } 380 ++j;395 G.next(j); 381 396 } 382 397 } … … 384 399 { 385 400 InEdgeIt j=G.template first<InEdgeIt>(a); 386 while ( j.valid() && e){401 while (G.valid(j) && e){ 387 402 if (is_admissible_backward_edge(j,new_level)){ 388 v=min(e,preflow .get(j));403 v=min(e,preflow[j]); 389 404 e -= v; 390 405 //New node might become active 391 if (excess .get(G.tail(j))==0){406 if (excess[G.tail(j)]==0){ 392 407 make_active(G.tail(j)); 393 408 } 394 409 modify_preflow(j,-v); 395 410 } 396 ++j;411 G.next(j); 397 412 } 398 413 } … … 411 426 412 427 //Level remains empty 413 if (num_of_nodes_on_level[level .get(a)]==1){428 if (num_of_nodes_on_level[level[a]]==1){ 414 429 change_level_to(a,number_of_nodes); 415 430 //go_to_next_node=True; … … 438 453 } 439 454 } 440 maxflow_value = excess .get(t);455 maxflow_value = excess[t]; 441 456 return maxflow_value; 442 457 }//run
Note: See TracChangeset
for help on using the changeset viewer.