Sorry, the other half of the move comes here.
6 #include <list_graph.h>
7 #include <hugo/smart_graph.h>
8 #include <hugo/dimacs.h>
10 #include <hugo/time_measure.h>
11 #include <for_each_macros.h>
15 // Use a DIMACS max flow file as stdin.
16 // read_dimacs_demo dimacs_max_flow_file
18 int main(int, char** argv) {
20 std::string in=argv[1];
21 typedef ListGraph MutableGraph;
24 typedef ListGraph Graph;
25 typedef Graph::Node Node;
26 typedef Graph::EdgeIt EdgeIt;
30 Graph::EdgeMap<int> cap(g);
31 std::ifstream ins(in.c_str());
32 //readDimacsMaxFlow(ins, g, s, t, cap);
33 readDimacs(ins, g, cap, s, t);
36 Graph::EdgeMap<int> flow(g); //0 flow
37 MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> >
38 max_flow_test(g, s, t, cap, flow/*, true*/);
40 std::cout << "ListGraph ..." << std::endl;
43 std::cout << "preflow ..." << std::endl;
46 std::cout << "elapsed time: " << ts << std::endl;
47 std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
51 std::cout << "physical blocking flow augmentation ..." << std::endl;
52 FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0);
55 while (max_flow_test.augmentOnBlockingFlow<MutableGraph>()) { ++i; }
56 std::cout << "elapsed time: " << ts << std::endl;
57 std::cout << "number of augmentation phases: " << i << std::endl;
58 std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
62 // std::cout << "faster physical blocking flow augmentation ..." << std::endl;
63 // FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0);
66 // while (max_flow_test.augmentOnBlockingFlow1<MutableGraph>()) { ++i; }
67 // std::cout << "elapsed time: " << ts << std::endl;
68 // std::cout << "number of augmentation phases: " << i << std::endl;
69 // std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
73 std::cout << "on-the-fly blocking flow augmentation ..." << std::endl;
74 FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0);
77 while (max_flow_test.augmentOnBlockingFlow2()) { ++i; }
78 std::cout << "elapsed time: " << ts << std::endl;
79 std::cout << "number of augmentation phases: " << i << std::endl;
80 std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
84 std::cout << "on-the-fly shortest path augmentation ..." << std::endl;
85 FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0);
88 while (max_flow_test.augmentOnShortestPath()) { ++i; }
89 std::cout << "elapsed time: " << ts << std::endl;
90 std::cout << "number of augmentation phases: " << i << std::endl;
91 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 << "SmatrGraph ..." << 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;