92 std::cout << "node and edge property values on the tails and heads of edges..." << std::endl; |
92 std::cout << "node and edge property values on the tails and heads of edges..." << std::endl; |
93 for(EachEdgeIt j=G.first<EachEdgeIt>(); j.valid(); ++j) { |
93 for(EachEdgeIt j=G.first<EachEdgeIt>(); j.valid(); ++j) { |
94 std::cout << my_property_vector.get(G.tail(j)) << "--" << my_edge_property.get(j) << "-->" << my_property_vector.get(G.head(j)) << " "; |
94 std::cout << my_property_vector.get(G.tail(j)) << "--" << my_edge_property.get(j) << "-->" << my_property_vector.get(G.head(j)) << " "; |
95 } |
95 } |
96 std::cout << std::endl; |
96 std::cout << std::endl; |
97 |
97 /* |
98 std::cout << "bfs from the first node" << std::endl; |
98 std::cout << "bfs from the first node" << std::endl; |
99 bfs<ListGraph> bfs_test(G, G.first<EachNodeIt>()); |
99 bfs<ListGraph> bfs_test(G, G.first<EachNodeIt>()); |
100 bfs_test.run(); |
100 bfs_test.run(); |
101 std::cout << "reached: "; |
101 std::cout << "reached: "; |
102 for(EachNodeIt i=G.first<EachNodeIt>(); i.valid(); ++i) { |
102 for(EachNodeIt i=G.first<EachNodeIt>(); i.valid(); ++i) { |
106 std::cout << "dist: "; |
106 std::cout << "dist: "; |
107 for(EachNodeIt i=G.first<EachNodeIt>(); i.valid(); ++i) { |
107 for(EachNodeIt i=G.first<EachNodeIt>(); i.valid(); ++i) { |
108 std::cout << bfs_test.dist.get(i) << " "; |
108 std::cout << bfs_test.dist.get(i) << " "; |
109 } |
109 } |
110 std::cout<<std::endl; |
110 std::cout<<std::endl; |
111 |
111 */ |
112 |
112 |
113 std::cout << "augmenting path flow algorithm test..." << std::endl; |
113 std::cout << "augmenting path flow algorithm test..." << std::endl; |
114 ListGraph flowG; |
114 ListGraph flowG; |
115 |
115 |
116 NodeIt s=flowG.addNode(); |
116 NodeIt s=flowG.addNode(); |
171 //flowG.deleteEdge(v1_v3); |
171 //flowG.deleteEdge(v1_v3); |
172 |
172 |
173 |
173 |
174 //flowG.setTail(v3_t, v2); |
174 //flowG.setTail(v3_t, v2); |
175 //flowG.setHead(v3_t, s); |
175 //flowG.setHead(v3_t, s); |
176 |
176 /* |
177 for(EachNodeIt i=flowG.first<EachNodeIt>(); i.valid(); ++i) { |
177 for(EachNodeIt i=flowG.first<EachNodeIt>(); i.valid(); ++i) { |
178 std::cout << node_name.get(i) << ": "; |
178 std::cout << node_name.get(i) << ": "; |
179 std::cout << "out edges: "; |
179 std::cout << "out edges: "; |
180 for(OutEdgeIt j=flowG.first<OutEdgeIt>(i); j.valid(); ++j) |
180 for(OutEdgeIt j=flowG.first<OutEdgeIt>(i); j.valid(); ++j) |
181 std::cout << node_name.get(flowG.tail(j)) << "-"<< cap.get(j) << "->" << node_name.get(flowG.head(j)) << " "; |
181 std::cout << node_name.get(flowG.tail(j)) << "-"<< cap.get(j) << "->" << node_name.get(flowG.head(j)) << " "; |
186 } |
186 } |
187 |
187 |
188 for(EachEdgeIt e=flowG.first<EachEdgeIt>(); e.valid(); ++e) { |
188 for(EachEdgeIt e=flowG.first<EachEdgeIt>(); e.valid(); ++e) { |
189 std::cout << node_name.get(flowG.tail(e)) << "-"<< cap.get(e) << "->" << node_name.get(flowG.head(e)) << " "; |
189 std::cout << node_name.get(flowG.tail(e)) << "-"<< cap.get(e) << "->" << node_name.get(flowG.head(e)) << " "; |
190 } |
190 } |
191 |
191 */ |
192 /* |
192 /* |
193 while (flowG.first<EachEdgeIt>().valid()) { |
193 while (flowG.first<EachEdgeIt>().valid()) { |
194 flowG.deleteEdge(flowG.first<EachEdgeIt>()); |
194 flowG.deleteEdge(flowG.first<EachEdgeIt>()); |
195 for(EachNodeIt i=flowG.first<EachNodeIt>(); i.valid(); ++i) { |
195 for(EachNodeIt i=flowG.first<EachNodeIt>(); i.valid(); ++i) { |
196 std::cout << node_name.get(i) << ": "; |
196 std::cout << node_name.get(i) << ": "; |
217 std::cout << std::endl; |
217 std::cout << std::endl; |
218 } |
218 } |
219 } |
219 } |
220 */ |
220 */ |
221 |
221 |
222 std::cout << std::endl; |
222 //std::cout << std::endl; |
223 //std::cout << "meg jo" << std::flush; |
223 |
224 |
224 |
225 ListGraph::EdgeMap<int> flow(flowG, 0); |
225 { |
226 MaxFlow<ListGraph, int, ListGraph::EdgeMap<int>, ListGraph::EdgeMap<int> > max_flow_test(flowG, s, t, flow, cap); |
226 ListGraph::EdgeMap<int> flow(flowG, 0); |
227 max_flow_test.run(); |
227 MaxFlow<ListGraph, int, ListGraph::EdgeMap<int>, ListGraph::EdgeMap<int> > max_flow_test(flowG, s, t, flow, cap); |
228 |
228 max_flow_test.run(); |
229 std::cout << "maximum flow: "<< std::endl; |
229 |
230 for(EachEdgeIt e=flowG.template first<EachEdgeIt>(); e.valid(); ++e) { |
230 std::cout << "maximum flow: "<< std::endl; |
231 std::cout<<"("<<flowG.tail(e)<< "-"<<flow.get(e)<<"->"<<flowG.head(e)<<") "; |
231 for(EachEdgeIt e=flowG.template first<EachEdgeIt>(); e.valid(); ++e) { |
232 } |
232 std::cout<<"("<<flowG.tail(e)<< "-"<<flow.get(e)<<"->"<<flowG.head(e)<<") "; |
233 std::cout<<std::endl; |
233 } |
234 std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl; |
234 std::cout<<std::endl; |
|
235 std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl; |
|
236 } |
|
237 |
|
238 { |
|
239 std::list<NodeIt> S; |
|
240 S.push_back(s); S.push_back(v3); |
|
241 std::list<NodeIt> T; |
|
242 T.push_back(t); |
|
243 |
|
244 ListGraph::EdgeMap<int> flow(flowG, 0); |
|
245 MaxFlow2<ListGraph, int, ListGraph::EdgeMap<int>, ListGraph::EdgeMap<int> > max_flow_test(flowG, S, T, flow, cap); |
|
246 max_flow_test.run(); |
|
247 |
|
248 std::cout << "maximum flow: "<< std::endl; |
|
249 for(EachEdgeIt e=flowG.template first<EachEdgeIt>(); e.valid(); ++e) { |
|
250 std::cout<<"("<<flowG.tail(e)<< "-"<<flow.get(e)<<"->"<<flowG.head(e)<<") "; |
|
251 } |
|
252 std::cout<<std::endl; |
|
253 std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl; |
|
254 } |
235 |
255 |
236 return 0; |
256 return 0; |
237 } |
257 } |