Example in the doc is corrected.
6 #include <sage_graph.h>
7 #include <hugo/list_graph.h>
8 #include <hugo/smart_graph.h>
9 #include <hugo/dimacs.h>
11 #include <hugo/time_measure.h>
12 #include <hugo/for_each_macros.h>
16 // Use a DIMACS max flow file as stdin.
17 // read_dimacs_demo dimacs_max_flow_file
19 int main(int, char** argv) {
21 std::string in=argv[1];
22 typedef SageGraph MutableGraph;
25 typedef SageGraph Graph;
26 typedef Graph::Node Node;
27 typedef Graph::EdgeIt EdgeIt;
31 Graph::EdgeMap<int> cap(g);
32 std::ifstream ins(in.c_str());
33 //readDimacsMaxFlow(ins, g, s, t, cap);
34 readDimacs(ins, g, cap, s, t);
37 Graph::EdgeMap<int> flow(g); //0 flow
38 MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> >
39 max_flow_test(g, s, t, cap, flow/*, true*/);
41 std::cout << "SageGraph ..." << std::endl;
44 std::cout << "preflow ..." << std::endl;
47 std::cout << "elapsed time: " << ts << std::endl;
48 std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
52 std::cout << "physical blocking flow augmentation ..." << std::endl;
53 FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0);
56 while (max_flow_test.augmentOnBlockingFlow<MutableGraph>()) { ++i; }
57 std::cout << "elapsed time: " << ts << std::endl;
58 std::cout << "number of augmentation phases: " << i << std::endl;
59 std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
63 // std::cout << "faster physical blocking flow augmentation ..." << std::endl;
64 // FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0);
67 // while (max_flow_test.augmentOnBlockingFlow1<MutableGraph>()) { ++i; }
68 // std::cout << "elapsed time: " << ts << std::endl;
69 // std::cout << "number of augmentation phases: " << i << std::endl;
70 // std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
74 std::cout << "on-the-fly blocking flow augmentation ..." << std::endl;
75 FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0);
78 while (max_flow_test.augmentOnBlockingFlow2()) { ++i; }
79 std::cout << "elapsed time: " << ts << std::endl;
80 std::cout << "number of augmentation phases: " << i << std::endl;
81 std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
85 std::cout << "on-the-fly shortest path augmentation ..." << std::endl;
86 FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0);
89 while (max_flow_test.augmentOnShortestPath()) { ++i; }
90 std::cout << "elapsed time: " << ts << std::endl;
91 std::cout << "number of augmentation phases: " << i << std::endl;
92 std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
97 typedef SmartGraph Graph;
98 typedef Graph::Node Node;
99 typedef Graph::EdgeIt EdgeIt;
103 Graph::EdgeMap<int> cap(g);
104 std::ifstream ins(in.c_str());
105 //readDimacsMaxFlow(ins, g, s, t, cap);
106 readDimacs(ins, g, cap, s, t);
109 Graph::EdgeMap<int> flow(g); //0 flow
110 MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> >
111 max_flow_test(g, s, t, cap, flow/*, true*/);
112 // MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> >
113 // max_flow_test(g, s, t, cap, flow);
115 std::cout << "SmartGraph ..." << std::endl;
118 std::cout << "preflow ..." << std::endl;
119 FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0);
122 std::cout << "elapsed time: " << ts << std::endl;
123 std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
127 std::cout << "physical blocking flow augmentation ..." << std::endl;
128 FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0);
131 while (max_flow_test.augmentOnBlockingFlow<MutableGraph>()) { ++i; }
132 std::cout << "elapsed time: " << ts << std::endl;
133 std::cout << "number of augmentation phases: " << i << std::endl;
134 std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
138 // std::cout << "faster physical blocking flow augmentation ..." << std::endl;
139 // FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0);
142 // while (max_flow_test.augmentOnBlockingFlow1<MutableGraph>()) { ++i; }
143 // std::cout << "elapsed time: " << ts << std::endl;
144 // std::cout << "number of augmentation phases: " << i << std::endl;
145 // std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
149 std::cout << "on-the-fly blocking flow augmentation ..." << std::endl;
150 FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0);
153 while (max_flow_test.augmentOnBlockingFlow2()) { ++i; }
154 std::cout << "elapsed time: " << ts << std::endl;
155 std::cout << "number of augmentation phases: " << i << std::endl;
156 std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
160 std::cout << "on-the-fly shortest path augmentation ..." << std::endl;
161 FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0);
164 while (max_flow_test.augmentOnShortestPath()) { ++i; }
165 std::cout << "elapsed time: " << ts << std::endl;
166 std::cout << "number of augmentation phases: " << i << std::endl;
167 std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
172 typedef ListGraph Graph;
173 typedef Graph::Node Node;
174 typedef Graph::EdgeIt EdgeIt;
178 Graph::EdgeMap<int> cap(g);
179 std::ifstream ins(in.c_str());
180 //readDimacsMaxFlow(ins, g, s, t, cap);
181 readDimacs(ins, g, cap, s, t);
184 Graph::EdgeMap<int> flow(g); //0 flow
185 MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> >
186 max_flow_test(g, s, t, cap, flow/*, true*/);
187 // MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> >
188 // max_flow_test(g, s, t, cap, flow);
190 std::cout << "ListGraph ..." << std::endl;
193 std::cout << "preflow ..." << std::endl;
194 FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0);
197 std::cout << "elapsed time: " << ts << std::endl;
198 std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
202 std::cout << "physical blocking flow augmentation ..." << std::endl;
203 FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0);
206 while (max_flow_test.augmentOnBlockingFlow<MutableGraph>()) { ++i; }
207 std::cout << "elapsed time: " << ts << std::endl;
208 std::cout << "number of augmentation phases: " << i << std::endl;
209 std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
213 // std::cout << "faster physical blocking flow augmentation ..." << std::endl;
214 // FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0);
217 // while (max_flow_test.augmentOnBlockingFlow1<MutableGraph>()) { ++i; }
218 // std::cout << "elapsed time: " << ts << std::endl;
219 // std::cout << "number of augmentation phases: " << i << std::endl;
220 // std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
224 std::cout << "on-the-fly blocking flow augmentation ..." << std::endl;
225 FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0);
228 while (max_flow_test.augmentOnBlockingFlow2()) { ++i; }
229 std::cout << "elapsed time: " << ts << std::endl;
230 std::cout << "number of augmentation phases: " << i << std::endl;
231 std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
235 std::cout << "on-the-fly shortest path augmentation ..." << std::endl;
236 FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0);
239 while (max_flow_test.augmentOnShortestPath()) { ++i; }
240 std::cout << "elapsed time: " << ts << std::endl;
241 std::cout << "number of augmentation phases: " << i << std::endl;
242 std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;