Changeset 77:69b2d279c8f0 in lemon0.x for src/work/athos/preflow_push.hh
 Timestamp:
 02/16/04 16:57:59 (17 years ago)
 Branch:
 default
 Phase:
 public
 Convert:
 svn:c9d7d8f590d60310b91f818b3a526b0e/lemon/trunk@100
 File:

 1 edited
Legend:
 Unmodified
 Added
 Removed

src/work/athos/preflow_push.hh
r36 r77 7 7 //#include "pf_hiba.hh" 8 8 //#include <marci_list_graph.hh> 9 #include <marci_graph_traits.hh> 9 //#include <marci_graph_traits.hh> 10 10 11 #include "reverse_bfs.hh" 11 12 … … 18 19 19 20 //Hasznos typedefek 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 /* 20 32 typedef graph_traits<graph_type>::node_iterator node_iterator; 21 typedef graph_traits<graph_type>:: edge_iterator edge_iterator;33 typedef graph_traits<graph_type>::EdgeIt EdgeIt; 22 34 typedef graph_traits<graph_type>::each_node_iterator each_node_iterator; 23 typedef graph_traits<graph_type>::each_edge_iterator each_edge_iterator; 24 typedef graph_traits<graph_type>::out_edge_iterator out_edge_iterator; 25 typedef graph_traits<graph_type>::in_edge_iterator in_edge_iterator; 26 typedef graph_traits<graph_type>::sym_edge_iterator sym_edge_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 */ 27 40 28 41 // … … 44 57 //input 45 58 graph_type& G; 46 node_iterator s; 47 node_iterator t; 48 edge_property_vector<graph_type, T> &capacity; 59 NodeIt s; 60 NodeIt t; 61 typename graph_type::EdgeMap<T> &capacity; 62 //typename graph_type::EdgeMap<T> &capacity; 49 63 //output 50 edge_property_vector<graph_type, T> preflow; 64 //typename graph_type::EdgeMap<T> 65 typename graph_type::EdgeMap<T> preflow; 51 66 T maxflow_value; 52 67 53 68 //auxiliary variables for computation 54 69 int number_of_nodes; 55 node_property_vector<graph_type, int> level; 56 node_property_vector<graph_type, T> excess; 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; 57 76 58 77 //Number of nodes on each level … … 60 79 61 80 //For the FIFO implementation 62 list< node_iterator> fifo_nodes;81 list<NodeIt> fifo_nodes; 63 82 //For 'highest label' implementation 64 83 int highest_active; 65 84 //int second_highest_active; 66 vector< list< node_iterator> > active_nodes;85 vector< list<NodeIt> > active_nodes; 67 86 68 87 public: … … 71 90 preflow_push( 72 91 graph_type& _G, 73 node_iterator_s,74 node_iterator_t,75 edge_property_vector<graph_type, T>& _capacity)92 NodeIt _s, 93 NodeIt _t, 94 typename graph_type::EdgeMap<T> & _capacity) 76 95 : G(_G), s(_s), t(_t), 77 96 capacity(_capacity), 78 97 preflow(_G), 79 98 //Counting the number of nodes 80 number_of_nodes(number_of(G.first_node())), 99 //number_of_nodes(count(G.first<EachNodeIt>())), 100 number_of_nodes(G.nodeNum()), 101 81 102 level(_G), 82 103 excess(_G)//, … … 107 128 T run(); 108 129 109 edge_property_vector<graph_type, T>getmaxflow(){130 typename graph_type::EdgeMap<T> getmaxflow(){ 110 131 return preflow; 111 132 } … … 115 136 //For testing purposes only 116 137 //Lists the node_properties 117 void write_property_vector(node_property_vector<graph_type, T> a, 138 void write_property_vector(typename graph_type::NodeMap<T> a, 139 //node_property_vector<graph_type, T> a, 118 140 char* prop_name="property"){ 119 for( each_node_iterator i=G.first_node(); i.valid(); ++i) {141 for(EachNodeIt i=G.template first<EachNodeIt>(); i.valid(); ++i) { 120 142 cout<<"Node id.: "<<G.id(i)<<", "<<prop_name<<" value: "<<a.get(i)<<endl; 121 143 } … … 124 146 125 147 //Modifies the excess of the node and makes sufficient changes 126 void modify_excess(const node_iterator& a ,T v){148 void modify_excess(const NodeIt& a ,T v){ 127 149 T old_value=excess.get(a); 128 excess. put(a,old_value+v);150 excess.set(a,old_value+v); 129 151 } 130 152 … … 133 155 //and maintain the excess on the head and tail 134 156 //Here we do not check whether this is possible or not 135 void modify_preflow( edge_iteratorj, const T& v){157 void modify_preflow(EdgeIt j, const T& v){ 136 158 137 159 //Auxiliary variable … … 140 162 //Modifiyng the edge 141 163 old_value=preflow.get(j); 142 preflow. put(j,old_value+v);164 preflow.set(j,old_value+v); 143 165 144 166 … … 153 175 //Gives the active node to work with 154 176 //(depending on the implementation to be used) 155 node_iteratorget_active_node(){177 NodeIt get_active_node(){ 156 178 //cout<<highest_active<<endl; 157 179 … … 165 187 166 188 if( highest_active>=0) { 167 node_iteratora=active_nodes[highest_active].front();189 NodeIt a=active_nodes[highest_active].front(); 168 190 active_nodes[highest_active].pop_front(); 169 191 return a; 170 192 } 171 193 else { 172 return node_iterator();194 return NodeIt(); 173 195 } 174 196 … … 179 201 180 202 if( ! fifo_nodes.empty() ) { 181 node_iteratora=fifo_nodes.front();203 NodeIt a=fifo_nodes.front(); 182 204 fifo_nodes.pop_front(); 183 205 return a; 184 206 } 185 207 else { 186 return node_iterator();208 return NodeIt(); 187 209 } 188 210 break; … … 190 212 } 191 213 // 192 return node_iterator();214 return NodeIt(); 193 215 } 194 216 195 217 //Puts node 'a' among the active nodes 196 void make_active(const node_iterator& a){218 void make_active(const NodeIt& a){ 197 219 //s and t never become active 198 220 if (a!=s && a!= t){ … … 216 238 217 239 //Changes the level of node a and make sufficent changes 218 void change_level_to( node_iteratora, int new_value){240 void change_level_to(NodeIt a, int new_value){ 219 241 int seged = level.get(a); 220 level. put(a,new_value);242 level.set(a,new_value); 221 243 num_of_nodes_on_level[seged]; 222 244 ++num_of_nodes_on_level[new_value]; … … 224 246 225 247 //Collection of things useful (or necessary) to do before running 248 226 249 void preprocess(){ 227 250 … … 232 255 //Setting starting preflow, level and excess values to zero 233 256 //This can be important, if the algorithm is run more then once 234 for( each_node_iterator i=G.first_node(); i.valid(); ++i) {235 level. put(i,0);236 excess. put(i,0);237 for( out_edge_iterator j=G.first_out_edge(i); j.valid(); ++j)238 preflow. put(j, 0);257 for(EachNodeIt i=G.template first<EachNodeIt>(); i.valid(); ++i) { 258 level.set(i,0); 259 excess.set(i,0); 260 for(OutEdgeIt j=G.template first<OutEdgeIt>(i); j.valid(); ++j) 261 preflow.set(j, 0); 239 262 } 240 263 num_of_nodes_on_level[0]=number_of_nodes; … … 252 275 rev_bfs.run(); 253 276 //write_property_vector(rev_bfs.dist,"rev_bfs"); 254 for( each_node_iterator i=G.first_node(); i.valid(); ++i) {277 for(EachNodeIt i=G.template first<EachNodeIt>(); i.valid(); ++i) { 255 278 change_level_to(i,rev_bfs.dist(i)); 256 279 //level.put(i,rev_bfs.dist.get(i)); … … 267 290 268 291 //we push as much preflow from s as possible to start with 269 for( out_edge_iterator j=G.first_out_edge(s); j.valid(); ++j){292 for(OutEdgeIt j=G.template first<OutEdgeIt>(s); j.valid(); ++j){ 270 293 modify_preflow(j,capacity.get(j) ); 271 294 make_active(G.head(j)); … … 281 304 //If the preflow is less than the capacity on the given edge 282 305 //then it is an edge in the residual graph 283 bool is_admissible_forward_edge( out_edge_iteratorj, int& new_level){306 bool is_admissible_forward_edge(OutEdgeIt j, int& new_level){ 284 307 if (capacity.get(j)>preflow.get(j)){ 285 308 if(level.get(G.tail(j))==level.get(G.head(j))+1){ … … 296 319 //If the preflow is greater than 0 on the given edge 297 320 //then the edge reversd is an edge in the residual graph 298 bool is_admissible_backward_edge( in_edge_iteratorj, int& new_level){321 bool is_admissible_backward_edge(InEdgeIt j, int& new_level){ 299 322 if (0<preflow.get(j)){ 300 323 if(level.get(G.tail(j))==level.get(G.head(j))1){ … … 319 342 320 343 T e,v; 321 node_iteratora;344 NodeIt a; 322 345 while (a=get_active_node(), a.valid()){ 323 346 //cout<<G.id(a)<<endl; … … 325 348 //write_property_vector(level,"level"); 326 349 327 //Initial value for the new level for the active node we are dealing with328 int new_level=2*number_of_nodes;329 350 330 351 bool go_to_next_node=false; 331 352 e = excess.get(a); 332 353 while (!go_to_next_node){ 333 354 355 //Initial value for the new level for the active node we are dealing with 356 int new_level=2*number_of_nodes; 357 //write_property_vector(excess,"excess"); 358 //write_property_vector(level,"level"); 359 //cout<<G.id(a)<<endl; 334 360 //Out edges from node a 335 361 { 336 out_edge_iterator j=G.first_out_edge(a);362 OutEdgeIt j=G.template first<OutEdgeIt>(a); 337 363 while (j.valid() && e){ 338 364 … … 351 377 //In edges to node a 352 378 { 353 in_edge_iterator j=G.first_in_edge(a);379 InEdgeIt j=G.template first<InEdgeIt>(a); 354 380 while (j.valid() && e){ 355 381 if (is_admissible_backward_edge(j,new_level)){ … … 373 399 } 374 400 else{//If there is still excess in node a 375 401 402 //change_level_to(a,new_level+1); 403 376 404 //Level remains empty 377 405 if (num_of_nodes_on_level[level.get(a)]==1){ … … 383 411 //increase_level(a); 384 412 } 385 413 386 414 387 415
Note: See TracChangeset
for help on using the changeset viewer.