36 // cout << "bfs and dfs iterator demo on the directed graph" << endl; |
36 // cout << "bfs and dfs iterator demo on the directed graph" << endl; |
37 // for(NodeIt n=G.first<NodeIt>(); G.valid(n); G.next(n)) { |
37 // for(NodeIt n=G.first<NodeIt>(); G.valid(n); G.next(n)) { |
38 // cout << G.id(n) << ": "; |
38 // cout << G.id(n) << ": "; |
39 // cout << "out edges: "; |
39 // cout << "out edges: "; |
40 // for(OutEdgeIt e=G.first<OutEdgeIt>(n); G.valid(e); G.next(e)) |
40 // for(OutEdgeIt e=G.first<OutEdgeIt>(n); G.valid(e); G.next(e)) |
41 // cout << G.id(G.tail(e)) << "-" << cap.get(e) << "->" << G.id(G.head(e)) << " "; |
41 // cout << G.id(G.source(e)) << "-" << cap.get(e) << "->" << G.id(G.target(e)) << " "; |
42 // cout << "in edges: "; |
42 // cout << "in edges: "; |
43 // for(InEdgeIt e=G.first<InEdgeIt>(n); G.valid(e); G.next(e)) |
43 // for(InEdgeIt e=G.first<InEdgeIt>(n); G.valid(e); G.next(e)) |
44 // cout << G.id(G.tail(e)) << "-" << cap.get(e) << "->" << G.id(G.head(e)) << " "; |
44 // cout << G.id(G.source(e)) << "-" << cap.get(e) << "->" << G.id(G.target(e)) << " "; |
45 // cout << endl; |
45 // cout << endl; |
46 // } |
46 // } |
47 |
47 |
48 // int i=0; |
48 // int i=0; |
49 // for(EdgeIt e=G.first<EdgeIt>(); G.valid(e); G.next(e)) { cap.set(e, i); i+=3; } |
49 // for(EdgeIt e=G.first<EdgeIt>(); G.valid(e); G.next(e)) { cap.set(e, i); i+=3; } |
62 MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> > max_flow_test(G, s, t, flow, cap); |
62 MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> > max_flow_test(G, s, t, flow, cap); |
63 //max_flow_test.augmentWithBlockingFlow<Graph>(); |
63 //max_flow_test.augmentWithBlockingFlow<Graph>(); |
64 int i=0; |
64 int i=0; |
65 while (max_flow_test.augmentOnShortestPath()) { |
65 while (max_flow_test.augmentOnShortestPath()) { |
66 // for(EdgeIt e=G.template first<EdgeIt>(); e.valid(); ++e) { |
66 // for(EdgeIt e=G.template first<EdgeIt>(); e.valid(); ++e) { |
67 // std::cout<<"("<<G.tail(e)<< "-"<<flow.get(e)<<"->"<<G.head(e)<<") "; |
67 // std::cout<<"("<<G.source(e)<< "-"<<flow.get(e)<<"->"<<G.target(e)<<") "; |
68 // } |
68 // } |
69 // std::cout<<std::endl; |
69 // std::cout<<std::endl; |
70 ++i; |
70 ++i; |
71 } |
71 } |
72 |
72 |
73 // std::cout << "maximum flow: "<< std::endl; |
73 // std::cout << "maximum flow: "<< std::endl; |
74 // for(EdgeIt e=G.first<EdgeIt>(); e.valid(); ++e) { |
74 // for(EdgeIt e=G.first<EdgeIt>(); e.valid(); ++e) { |
75 // std::cout<<"("<<G.tail(e)<< "-"<<flow.get(e)<<"->"<<G.head(e)<<") "; |
75 // std::cout<<"("<<G.source(e)<< "-"<<flow.get(e)<<"->"<<G.target(e)<<") "; |
76 // } |
76 // } |
77 // std::cout<<std::endl; |
77 // std::cout<<std::endl; |
78 std::cout << "elapsed time: " << ts << std::endl; |
78 std::cout << "elapsed time: " << ts << std::endl; |
79 std::cout << "number of augmentation phases: " << i << std::endl; |
79 std::cout << "number of augmentation phases: " << i << std::endl; |
80 std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl; |
80 std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl; |