85 ts.reset(); |
85 ts.reset(); |
86 //double pre_time=currTime(); |
86 //double pre_time=currTime(); |
87 MaxFlow<ListGraph, int, ListGraph::EdgeMap<int>, ListGraph::EdgeMap<int> > max_flow_test(G, s, t, flow, cap); |
87 MaxFlow<ListGraph, int, ListGraph::EdgeMap<int>, ListGraph::EdgeMap<int> > max_flow_test(G, s, t, flow, cap); |
88 //max_flow_test.augmentWithBlockingFlow<ListGraph>(); |
88 //max_flow_test.augmentWithBlockingFlow<ListGraph>(); |
89 int i=0; |
89 int i=0; |
90 while (max_flow_test.augmentOnBlockingFlow<ListGraph>()) { ++i; } |
90 while (max_flow_test.augmentOnBlockingFlow<ListGraph>()) { |
|
91 // for(EachEdgeIt e=G.template first<EachEdgeIt>(); e.valid(); ++e) { |
|
92 // std::cout<<"("<<G.tail(e)<< "-"<<flow.get(e)<<"->"<<G.head(e)<<") "; |
|
93 // } |
|
94 // std::cout<<std::endl; |
|
95 ++i; |
|
96 } |
|
97 //double post_time=currTime(); |
|
98 |
|
99 //std::cout << "maximum flow: "<< std::endl; |
|
100 //for(EachEdgeIt e=G.first<EachEdgeIt>(); e.valid(); ++e) { |
|
101 // std::cout<<"("<<G.tail(e)<< "-"<<flow.get(e)<<"->"<<G.head(e)<<") "; |
|
102 //} |
|
103 //std::cout<<std::endl; |
|
104 std::cout << "elapsed time: " << ts << std::endl; |
|
105 std::cout << "number of augmentation phases: " << i << std::endl; |
|
106 std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl; |
|
107 } |
|
108 |
|
109 { |
|
110 std::cout << "edmonds karp demo (blocking flow augmentation)..." << std::endl; |
|
111 ListGraph::EdgeMap<int> flow(G); //0 flow |
|
112 |
|
113 Timer ts; |
|
114 ts.reset(); |
|
115 //double pre_time=currTime(); |
|
116 MaxFlow<ListGraph, int, ListGraph::EdgeMap<int>, ListGraph::EdgeMap<int> > max_flow_test(G, s, t, flow, cap); |
|
117 //max_flow_test.augmentWithBlockingFlow<ListGraph>(); |
|
118 int i=0; |
|
119 while (max_flow_test.augmentOnBlockingFlow2()) { |
|
120 // for(EachEdgeIt e=G.template first<EachEdgeIt>(); e.valid(); ++e) { |
|
121 // std::cout<<"("<<G.tail(e)<< "-"<<flow.get(e)<<"->"<<G.head(e)<<") "; |
|
122 // } |
|
123 // std::cout<<std::endl; |
|
124 ++i; |
|
125 } |
91 //double post_time=currTime(); |
126 //double post_time=currTime(); |
92 |
127 |
93 //std::cout << "maximum flow: "<< std::endl; |
128 //std::cout << "maximum flow: "<< std::endl; |
94 //for(EachEdgeIt e=G.first<EachEdgeIt>(); e.valid(); ++e) { |
129 //for(EachEdgeIt e=G.first<EachEdgeIt>(); e.valid(); ++e) { |
95 // std::cout<<"("<<G.tail(e)<< "-"<<flow.get(e)<<"->"<<G.head(e)<<") "; |
130 // std::cout<<"("<<G.tail(e)<< "-"<<flow.get(e)<<"->"<<G.head(e)<<") "; |
108 ts.reset(); |
143 ts.reset(); |
109 //double pre_time=currTime(); |
144 //double pre_time=currTime(); |
110 MaxFlow<ListGraph, int, ListGraph::EdgeMap<int>, ListGraph::EdgeMap<int> > max_flow_test(G, s, t, flow, cap); |
145 MaxFlow<ListGraph, int, ListGraph::EdgeMap<int>, ListGraph::EdgeMap<int> > max_flow_test(G, s, t, flow, cap); |
111 //max_flow_test.augmentWithBlockingFlow<ListGraph>(); |
146 //max_flow_test.augmentWithBlockingFlow<ListGraph>(); |
112 int i=0; |
147 int i=0; |
113 while (max_flow_test.augmentOnShortestPath()) { ++i; } |
148 while (max_flow_test.augmentOnShortestPath()) { |
|
149 // for(EachEdgeIt e=G.template first<EachEdgeIt>(); e.valid(); ++e) { |
|
150 // std::cout<<"("<<G.tail(e)<< "-"<<flow.get(e)<<"->"<<G.head(e)<<") "; |
|
151 // } |
|
152 // std::cout<<std::endl; |
|
153 ++i; |
|
154 } |
114 //double post_time=currTime(); |
155 //double post_time=currTime(); |
115 |
156 |
116 //std::cout << "maximum flow: "<< std::endl; |
157 //std::cout << "maximum flow: "<< std::endl; |
117 //for(EachEdgeIt e=G.first<EachEdgeIt>(); e.valid(); ++e) { |
158 //for(EachEdgeIt e=G.first<EachEdgeIt>(); e.valid(); ++e) { |
118 // std::cout<<"("<<G.tail(e)<< "-"<<flow.get(e)<<"->"<<G.head(e)<<") "; |
159 // std::cout<<"("<<G.tail(e)<< "-"<<flow.get(e)<<"->"<<G.head(e)<<") "; |