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

 1 added
 2 edited
Legend:
 Unmodified
 Added
 Removed

src/work/athos/pf_demo.cc
r36 r77 3 3 #include <string> 4 4 5 #include " marci_list_graph.hh"5 #include "list_graph.hh" 6 6 #include "marci_graph_traits.hh" 7 #include "marci_property_vector.hh"7 //#include "marci_property_vector.hh" 8 8 #include "preflow_push.hh" 9 9 … … 13 13 int main (int, char*[]) 14 14 { 15 typedef graph_traits<list_graph>::node_iterator node_iterator;16 typedef graph_traits<list_graph>::edge_iterator edge_iterator;17 typedef graph_traits<list_graph>::each_node_iterator each_node_iterator;18 typedef graph_traits<list_graph>::each_edge_iterator each_edge_iterator;19 typedef graph_traits<list_graph>::out_edge_iterator out_edge_iterator;20 typedef graph_traits<list_graph>::in_edge_iterator in_edge_iterator;21 typedef graph_traits<list_graph>::sym_edge_iterator sym_edge_iterator;22 15 23 list_graph flow_test;24 25 16 17 typedef ListGraph::NodeIt NodeIt; 18 typedef ListGraph::EdgeIt EdgeIt; 19 /* 20 typedef ListGraph::EachNodeIt EachNodeIt; 21 typedef ListGraph::EachEdgeIt EachEdgeIt; 22 typedef ListGraph::OutEdgeIt OutEdgeIt; 23 typedef ListGraph::InEdgeIt InEdgeIt; 24 typedef ListGraph::SymEdgeIt SymEdgeIt; 25 */ 26 27 //Marci példája 28 ListGraph flowG; 29 30 NodeIt s=flowG.addNode(); 31 NodeIt v1=flowG.addNode(); 32 NodeIt v2=flowG.addNode(); 33 NodeIt v3=flowG.addNode(); 34 NodeIt v4=flowG.addNode(); 35 NodeIt t=flowG.addNode(); 36 37 38 EdgeIt s_v1=flowG.addEdge(s, v1); 39 EdgeIt s_v2=flowG.addEdge(s, v2); 40 EdgeIt v1_v2=flowG.addEdge(v1, v2); 41 EdgeIt v2_v1=flowG.addEdge(v2, v1); 42 EdgeIt v1_v3=flowG.addEdge(v1, v3); 43 EdgeIt v3_v2=flowG.addEdge(v3, v2); 44 EdgeIt v2_v4=flowG.addEdge(v2, v4); 45 EdgeIt v4_v3=flowG.addEdge(v4, v3); 46 EdgeIt v3_t=flowG.addEdge(v3, t); 47 EdgeIt v4_t=flowG.addEdge(v4, t); 48 49 ListGraph::EdgeMap<int> cap(flowG); 50 51 cap.set(s_v1, 16); 52 cap.set(s_v2, 13); 53 cap.set(v1_v2, 10); 54 cap.set(v2_v1, 4); 55 cap.set(v1_v3, 12); 56 cap.set(v3_v2, 9); 57 cap.set(v2_v4, 14); 58 cap.set(v4_v3, 7); 59 cap.set(v3_t, 20); 60 cap.set(v4_t, 4); 61 62 63 64 65 66 67 68 /* 26 69 //Ahuja könyv példája 27 70 node_iterator s=flow_test.add_node(); 28 node_iteratorv2=flow_test.add_node();29 node_iteratorv3=flow_test.add_node();30 node_iteratorv4=flow_test.add_node();31 node_iteratorv5=flow_test.add_node();32 node_iteratort=flow_test.add_node();71 NodeIt v2=flow_test.add_node(); 72 NodeIt v3=flow_test.add_node(); 73 NodeIt v4=flow_test.add_node(); 74 NodeIt v5=flow_test.add_node(); 75 NodeIt t=flow_test.add_node(); 33 76 34 77 node_property_vector<list_graph, std::string> node_name(flow_test); … … 71 114 //cap.put(t_s, 20); 72 115 73 74 /* 75 //Marci példája 76 node_iterator s=flow_test.add_node(); 77 node_iterator v1=flow_test.add_node(); 78 node_iterator v2=flow_test.add_node(); 79 node_iterator v3=flow_test.add_node(); 80 node_iterator v4=flow_test.add_node(); 81 node_iterator t=flow_test.add_node(); 82 83 node_property_vector<list_graph, std::string> node_name(flow_test); 84 node_name.put(s, "s"); 85 node_name.put(v1, "v1"); 86 node_name.put(v2, "v2"); 87 node_name.put(v3, "v3"); 88 node_name.put(v4, "v4"); 89 node_name.put(t, "t"); 116 */ 90 117 91 edge_iterator s_v1=flow_test.add_edge(s, v1); 92 edge_iterator s_v2=flow_test.add_edge(s, v2); 93 edge_iterator v1_v2=flow_test.add_edge(v1, v2); 94 edge_iterator v2_v1=flow_test.add_edge(v2, v1); 95 edge_iterator v1_v3=flow_test.add_edge(v1, v3); 96 edge_iterator v3_v2=flow_test.add_edge(v3, v2); 97 edge_iterator v2_v4=flow_test.add_edge(v2, v4); 98 edge_iterator v4_v3=flow_test.add_edge(v4, v3); 99 edge_iterator v3_t=flow_test.add_edge(v3, t); 100 edge_iterator v4_t=flow_test.add_edge(v4, t); 101 102 edge_property_vector<list_graph, int> cap(flow_test); 103 cap.put(s_v1, 16); 104 cap.put(s_v2, 13); 105 cap.put(v1_v2, 10); 106 cap.put(v2_v1, 4); 107 cap.put(v1_v3, 12); 108 cap.put(v3_v2, 9); 109 cap.put(v2_v4, 14); 110 cap.put(v4_v3, 7); 111 cap.put(v3_t, 20); 112 cap.put(v4_t, 4); 113 */ 118 119 114 120 /*Egyszerû példa 115 node_iterators=flow_test.add_node();116 node_iteratorv1=flow_test.add_node();117 node_iteratorv2=flow_test.add_node();118 node_iteratort=flow_test.add_node();121 NodeIt s=flow_test.add_node(); 122 NodeIt v1=flow_test.add_node(); 123 NodeIt v2=flow_test.add_node(); 124 NodeIt t=flow_test.add_node(); 119 125 120 126 node_property_vector<list_graph, std::string> node_name(flow_test); … … 136 142 137 143 std::cout << "preflowpush algorithm test..." << std::endl; 144 145 /* 138 146 std::cout << "on directed graph graph" << std::endl; //<< flow_test; 139 147 std::cout << "names and capacity values" << std::endl; 140 for( each_node_iteratori=flow_test.first_node(); i.valid(); ++i) {148 for(EachNodeIt i=flow_test.first_node(); i.valid(); ++i) { 141 149 std::cout << node_name.get(i) << ": "; 142 150 std::cout << "out edges: "; … … 148 156 std::cout << std::endl; 149 157 } 150 158 */ 151 159 152 //for(each_ node_iteratori=flow_test.first_node(); i.valid(); ++i) {160 //for(each_NodeIt i=flow_test.first_node(); i.valid(); ++i) { 153 161 // std::cout << i << " "; 154 162 //} 155 163 156 preflow_push< list_graph, int> preflow_push_test(flow_test, s, t, cap);164 preflow_push<ListGraph, int> preflow_push_test(flowG, s, t, cap); 157 165 cout << preflow_push_test.run()<<endl; 158 166 
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.