92 typedef typename res_graph_type<graph_type, T>::res_edge_it edge_iterator; |
92 typedef typename res_graph_type<graph_type, T>::res_edge_it edge_iterator; |
93 typedef typename graph_traits<graph_type>::each_node_iterator each_node_iterator; |
93 typedef typename graph_traits<graph_type>::each_node_iterator each_node_iterator; |
94 typedef typename res_graph_type<graph_type, T>::res_out_edge_it out_edge_iterator; |
94 typedef typename res_graph_type<graph_type, T>::res_out_edge_it out_edge_iterator; |
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 template <typename graph_type, typename T> |
97 template <typename graph_type, typename T> |
132 struct max_flow_type { |
98 struct max_flow_type { |
133 |
99 |
134 typedef typename graph_traits<graph_type>::node_iterator node_iterator; |
100 typedef typename graph_traits<graph_type>::node_iterator node_iterator; |
135 typedef typename graph_traits<graph_type>::edge_iterator edge_iterator; |
101 typedef typename graph_traits<graph_type>::edge_iterator edge_iterator; |
150 } |
116 } |
151 void run() { |
117 void run() { |
152 typedef res_graph_type<graph_type, T> aug_graph_type; |
118 typedef res_graph_type<graph_type, T> aug_graph_type; |
153 aug_graph_type res_graph(G, flow, capacity); |
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 bool augment; |
121 bool augment; |
186 do { |
122 do { |
187 augment=false; |
123 augment=false; |
188 |
124 |
189 while (!bfs_queue.empty()) { bfs_queue.pop(); } |
125 typedef std::queue<graph_traits<aug_graph_type>::out_edge_iterator> bfs_queue_type; |
|
126 bfs_queue_type bfs_queue; |
190 bfs_queue.push(res_graph.first_out_edge(s)); |
127 bfs_queue.push(res_graph.first_out_edge(s)); |
191 |
128 |
192 for(graph_traits<aug_graph_type>::each_node_iterator i=res_graph.first_node(); i.is_valid(); ++i) { reached.put(i, false); } |
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 reached.put(s, true); |
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 //searching for augmenting path |
145 //searching for augmenting path |
196 while ( /*std::cin>>c &&*/ res_bfs.is_valid() ) { |
146 while ( res_bfs.is_valid() ) { |
197 res_bfs.process(); |
147 //std::cout<<"KULSO ciklus itt jar: "<<G.id(res_graph.tail(res_bfs))<<"->"<<G.id(res_graph.head(res_bfs))<<std::endl; |
198 //if (res_graph.head(graph_traits<aug_graph_type>::out_edge_iterator(res_bfs))==t) break; |
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 if (res_graph.head(res_bfs)==t) break; |
167 if (res_graph.head(res_bfs)==t) break; |
200 //res_bfs.next(); |
|
201 ++res_bfs; |
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 if (reached.get(t)) { |
170 if (reached.get(t)) { |
205 augment=true; |
171 augment=true; |
206 node_iterator n=t; |
172 node_iterator n=t; |
207 T augment_value=free.get(t); |
173 T augment_value=free.get(t); |
208 std::cout<<"augmentation: "; |
174 std::cout<<"augmentation: "; |