Changeset 14:99014d576aed in lemon0.x for src/work
 Timestamp:
 01/12/04 12:50:52 (20 years ago)
 Branch:
 default
 Phase:
 public
 Convert:
 svn:c9d7d8f590d60310b91f818b3a526b0e/lemon/trunk@27
 File:

 1 edited
Legend:
 Unmodified
 Added
 Removed

src/work/marci_max_flow.hh
r9 r14 95 95 }; 96 96 97 template <typename graph_type, typename pred_type, typename free_type>98 struct flow_visitor {99 typedef typename graph_traits<graph_type>::node_iterator node_iterator;100 typedef typename graph_traits<graph_type>::edge_iterator edge_iterator;101 typedef typename graph_traits<graph_type>::each_node_iterator each_node_iterator;102 typedef typename graph_traits<graph_type>::out_edge_iterator out_edge_iterator;103 graph_type& G;104 pred_type& pred;105 free_type& free;106 flow_visitor(graph_type& _G, pred_type& _pred, free_type& _free) : G(_G), pred(_pred), free(_free) { }107 void at_previously_reached(out_edge_iterator& e) {108 //node_iterator v=G.tail(e);109 //node_iterator w=G.head(e);110 //std::cout<<G.id(v)<<">"<<G.id(w)<<", "<<G.id(w)<<" is already reached";111 //std::cout<<std::endl;112 }113 void at_newly_reached(out_edge_iterator& e) {114 node_iterator v=G.tail(e);115 node_iterator w=G.head(e);116 //std::cout<<G.id(v)<<">"<<G.id(w)<<", "<<G.id(w)<<" is newly reached";117 pred.put(w, e);118 if (pred.get(v).is_valid()) {119 free.put(w, std::min(free.get(v), e.free()));120 //std::cout <<" nem elso csucs: ";121 //std::cout <<"szabad kap eddig: "<< free.get(w) << " ";122 } else {123 free.put(w, e.free());124 //std::cout <<" elso csucs: ";125 //std::cout <<"szabad kap eddig: "<< free.get(w) << " ";126 }127 //std::cout<<std::endl;128 }129 };130 131 97 template <typename graph_type, typename T> 132 98 struct max_flow_type { … … 153 119 aug_graph_type res_graph(G, flow, capacity); 154 120 155 typedef std::queue<graph_traits<aug_graph_type>::out_edge_iterator> bfs_queue_type;156 bfs_queue_type bfs_queue;157 //bfs_queue.push(res_graph.first_out_edge(s));158 159 typedef node_property_vector<aug_graph_type, bool> reached_type;160 //reached_type reached(res_graph, false);161 reached_type reached(res_graph);162 //reached.put(s, true);163 164 typedef node_property_vector<aug_graph_type, graph_traits<aug_graph_type>::edge_iterator> pred_type;165 pred_type pred(res_graph);166 pred.put(s, res_graph.invalid_edge());167 168 typedef node_property_vector<aug_graph_type, int> free_type;169 free_type free(res_graph);170 171 typedef flow_visitor<aug_graph_type, pred_type, free_type> visitor_type;172 visitor_type vis(res_graph, pred, free);173 174 bfs_iterator< aug_graph_type, reached_type, visitor_type >175 res_bfs(res_graph, bfs_queue, reached, vis);176 177 //for(graph_traits<aug_graph_type>::each_node_iterator i=res_graph.first_node(); i.is_valid(); ++i) {178 //for(graph_traits<aug_graph_type>::out_edge_iterator j=res_graph.first_out_edge(i); j.is_valid(); ++j) {179 // std::cout<<"("<<res_graph.tail(j)<< ">"<<res_graph.head(j)<<") ";180 //}181 //}182 //std::cout<<std::endl;183 184 //char c;185 121 bool augment; 186 122 do { 187 123 augment=false; 188 189 while (!bfs_queue.empty()) { bfs_queue.pop(); } 124 125 typedef std::queue<graph_traits<aug_graph_type>::out_edge_iterator> bfs_queue_type; 126 bfs_queue_type bfs_queue; 190 127 bfs_queue.push(res_graph.first_out_edge(s)); 191 192 for(graph_traits<aug_graph_type>::each_node_iterator i=res_graph.first_node(); i.is_valid(); ++i) { reached.put(i, false); } 128 129 typedef node_property_vector<aug_graph_type, bool> reached_type; 130 //reached_type reached(res_graph); 131 //for(graph_traits<aug_graph_type>::each_node_iterator i=res_graph.first_node(); i.is_valid(); ++i) { reached.put(i, false); } 132 reached_type reached(res_graph, false); 193 133 reached.put(s, true); 194 134 135 bfs_iterator1< aug_graph_type, reached_type > 136 res_bfs(res_graph, bfs_queue, reached); 137 138 typedef node_property_vector<aug_graph_type, graph_traits<aug_graph_type>::edge_iterator> pred_type; 139 pred_type pred(res_graph); 140 pred.put(s, res_graph.invalid_edge()); 141 142 typedef node_property_vector<aug_graph_type, int> free_type; 143 free_type free(res_graph); 144 195 145 //searching for augmenting path 196 while ( /*std::cin>>c &&*/ res_bfs.is_valid() ) { 197 res_bfs.process(); 198 //if (res_graph.head(graph_traits<aug_graph_type>::out_edge_iterator(res_bfs))==t) break; 146 while ( res_bfs.is_valid() ) { 147 //std::cout<<"KULSO ciklus itt jar: "<<G.id(res_graph.tail(res_bfs))<<">"<<G.id(res_graph.head(res_bfs))<<std::endl; 148 if (res_bfs.is_newly_reached()) { 149 graph_traits<aug_graph_type>::edge_iterator e; 150 e=res_bfs; 151 node_iterator v=res_graph.tail(e); 152 node_iterator w=res_graph.head(e); 153 //std::cout<<G.id(v)<<">"<<G.id(w)<<", "<<G.id(w)<<" is newly reached"; 154 pred.put(w, e); 155 if (pred.get(v).is_valid()) { 156 free.put(w, std::min(free.get(v), e.free())); 157 //std::cout <<" nem elso csucs: "; 158 //std::cout <<"szabad kap eddig: "<< free.get(w) << " "; 159 } else { 160 free.put(w, e.free()); 161 //std::cout <<" elso csucs: "; 162 //std::cout <<"szabad kap eddig: "<< free.get(w) << " "; 163 } 164 //std::cout<<std::endl; 165 } 166 199 167 if (res_graph.head(res_bfs)==t) break; 200 //res_bfs.next();201 168 ++res_bfs; 202 169 } 203 //for (; std::cin>>c && !res_bfs.finished() && res_graph.head(res_bfs.current())!=t; res_bfs.next()) { res_bfs.process(); }204 170 if (reached.get(t)) { 205 171 augment=true; … … 216 182 } 217 183 218 std::cout << " max flow:"<< std::endl;184 std::cout << "actual flow: "<< std::endl; 219 185 for(graph_traits<graph_type>::each_edge_iterator e=G.first_edge(); e.is_valid(); ++e) { 220 186 std::cout<<"("<<G.tail(e)<< ""<<flow.get(e)<<">"<<G.head(e)<<") ";
Note: See TracChangeset
for help on using the changeset viewer.