sg is moved sg is not...
5 #include <list_graph.h>
6 #include <smart_graph.h>
8 #include <edmonds_karp.h>
9 #include <time_measure.h>
10 #include <graph_wrapper.h>
14 // Use a DIMACS max flow file as stdin.
15 // read_dimacs_demo < dimacs_max_flow_file
17 int main(int, char **) {
19 typedef ListGraph MutableGraph;
20 //typedef SmartGraph Graph;
21 typedef ListGraph Graph;
22 typedef Graph::Node Node;
23 typedef Graph::EdgeIt EdgeIt;
27 Graph::EdgeMap<int> cap(G);
28 readDimacsMaxFlow(std::cin, G, s, t, cap);
31 typedef TrivGraphWrapper<const Graph> GW;
33 typedef GW::EdgeMapWrapper< Graph::EdgeMap<int>, int > EMW;
36 GW::EdgeMap<int> flow(gw);
37 MaxFlow<GW, int, GW::EdgeMap<int>, EMW > max_flow_test(gw, s, t, flow, cw);
41 std::cout << "edmonds karp demo (physical blocking flow augmentation)..." << std::endl;
42 for (GW::EdgeIt e(gw); gw.valid(e); gw.next(e)) flow.set(e, 0);
46 while (max_flow_test.augmentOnBlockingFlow<MutableGraph>()) { ++i; }
48 std::cout << "elapsed time: " << ts << std::endl;
49 std::cout << "number of augmentation phases: " << i << std::endl;
50 std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
54 std::cout << "edmonds karp demo (physical blocking flow 1 augmentation)..." << std::endl;
55 for (GW::EdgeIt e(gw); gw.valid(e); gw.next(e)) flow.set(e, 0);
59 while (max_flow_test.augmentOnBlockingFlow1<MutableGraph>()) { ++i; }
61 std::cout << "elapsed time: " << ts << std::endl;
62 std::cout << "number of augmentation phases: " << i << std::endl;
63 std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
67 std::cout << "edmonds karp demo (on-the-fly blocking flow augmentation)..." << std::endl;
68 for (GW::EdgeIt e(gw); gw.valid(e); gw.next(e)) flow.set(e, 0);
72 while (max_flow_test.augmentOnBlockingFlow2()) { ++i; }
74 std::cout << "elapsed time: " << ts << std::endl;
75 std::cout << "number of augmentation phases: " << i << std::endl;
76 std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
80 std::cout << "edmonds karp demo (on-the-fly shortest path augmentation)..." << std::endl;
81 for (GW::EdgeIt e(gw); gw.valid(e); gw.next(e)) flow.set(e, 0);
85 while (max_flow_test.augmentOnShortestPath()) { ++i; }
87 std::cout << "elapsed time: " << ts << std::endl;
88 std::cout << "number of augmentation phases: " << i << std::endl;
89 std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
97 typedef TrivGraphWrapper<const Graph> GW1;
99 typedef TrivGraphWrapper<const GW1> GW2;
101 typedef TrivGraphWrapper<const GW2> GW3;
103 typedef TrivGraphWrapper<const GW3> GW4;
105 typedef TrivGraphWrapper<const GW4> GW5;
107 typedef TrivGraphWrapper<const GW5> GW6;
109 typedef TrivGraphWrapper<const GW6> GW7;
111 typedef TrivGraphWrapper<const GW7> GW8;
113 typedef TrivGraphWrapper<const GW8> GW9;
115 typedef TrivGraphWrapper<const GW9> GW;
117 typedef GW::EdgeMapWrapper< Graph::EdgeMap<int>, int > EMW;
120 GW::EdgeMap<int> flow(gw);
121 MaxFlow<GW, int, GW::EdgeMap<int>, EMW > max_flow_test(gw, s, t, flow, cw);
125 std::cout << "edmonds karp demo (physical blocking flow augmentation)..." << std::endl;
126 for (GW::EdgeIt e(gw); gw.valid(e); gw.next(e)) flow.set(e, 0);
130 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 << "edmonds karp demo (physical blocking flow 1 augmentation)..." << std::endl;
139 for (GW::EdgeIt e(gw); gw.valid(e); gw.next(e)) flow.set(e, 0);
143 while (max_flow_test.augmentOnBlockingFlow1<MutableGraph>()) { ++i; }
145 std::cout << "elapsed time: " << ts << std::endl;
146 std::cout << "number of augmentation phases: " << i << std::endl;
147 std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
151 std::cout << "edmonds karp demo (on-the-fly blocking flow augmentation)..." << std::endl;
152 for (GW::EdgeIt e(gw); gw.valid(e); gw.next(e)) flow.set(e, 0);
156 while (max_flow_test.augmentOnBlockingFlow2()) { ++i; }
158 std::cout << "elapsed time: " << ts << std::endl;
159 std::cout << "number of augmentation phases: " << i << std::endl;
160 std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
164 std::cout << "edmonds karp demo (on-the-fly shortest path augmentation)..." << std::endl;
165 for (GW::EdgeIt e(gw); gw.valid(e); gw.next(e)) flow.set(e, 0);
169 while (max_flow_test.augmentOnShortestPath()) { ++i; }
171 std::cout << "elapsed time: " << ts << std::endl;
172 std::cout << "number of augmentation phases: " << i << std::endl;
173 std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;