32 |
32 |
33 int main(int, char **) { |
33 int main(int, char **) { |
34 |
34 |
35 typedef ListGraph MutableGraph; |
35 typedef ListGraph MutableGraph; |
36 |
36 |
37 // typedef SmartGraph Graph; |
37 typedef SmartGraph Graph; |
38 typedef ListGraph Graph; |
38 //typedef ListGraph Graph; |
39 typedef Graph::Node Node; |
39 typedef Graph::Node Node; |
40 typedef Graph::EdgeIt EdgeIt; |
40 typedef Graph::EdgeIt EdgeIt; |
41 |
41 |
42 |
42 |
43 // Mize mize[10]; |
43 // Mize mize[10]; |
112 std::cout << "number of augmentation phases: " << i << std::endl; |
112 std::cout << "number of augmentation phases: " << i << std::endl; |
113 std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl; |
113 std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl; |
114 } |
114 } |
115 |
115 |
116 { |
116 { |
|
117 std::cout << "SmartGraph..." << std::endl; |
|
118 std::cout << "edmonds karp demo (physical blocking flow 1 augmentation)..." << std::endl; |
|
119 Graph::EdgeMap<int> flow(G); //0 flow |
|
120 |
|
121 Timer ts; |
|
122 ts.reset(); |
|
123 |
|
124 MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> > max_flow_test(G, s, t, flow, cap); |
|
125 //max_flow_test.augmentWithBlockingFlow<Graph>(); |
|
126 int i=0; |
|
127 while (max_flow_test.augmentOnBlockingFlow1<MutableGraph>()) { |
|
128 // for(EdgeIt e=G.template first<EdgeIt>(); e.valid(); ++e) { |
|
129 // std::cout<<"("<<G.tail(e)<< "-"<<flow.get(e)<<"->"<<G.head(e)<<") "; |
|
130 // } |
|
131 // std::cout<<std::endl; |
|
132 ++i; |
|
133 } |
|
134 |
|
135 // std::cout << "maximum flow: "<< std::endl; |
|
136 // for(EdgeIt e=G.first<EdgeIt>(); e.valid(); ++e) { |
|
137 // std::cout<<"("<<G.tail(e)<< "-"<<flow.get(e)<<"->"<<G.head(e)<<") "; |
|
138 // } |
|
139 // std::cout<<std::endl; |
|
140 std::cout << "elapsed time: " << ts << std::endl; |
|
141 std::cout << "number of augmentation phases: " << i << std::endl; |
|
142 std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl; |
|
143 } |
|
144 |
|
145 { |
117 std::cout << "edmonds karp demo (on-the-fly blocking flow augmentation)..." << std::endl; |
146 std::cout << "edmonds karp demo (on-the-fly blocking flow augmentation)..." << std::endl; |
118 Graph::EdgeMap<int> flow(G); //0 flow |
147 Graph::EdgeMap<int> flow(G); //0 flow |
119 |
148 |
120 Timer ts; |
149 Timer ts; |
121 ts.reset(); |
150 ts.reset(); |