as you see...
6 #include <list_graph.h>
7 #include <smart_graph.h>
9 #include <edmonds_karp.h>
11 #include <time_measure.h>
12 #include <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 ListGraph MutableGraph;
25 typedef ListGraph 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);
36 Graph::EdgeMap<int> flow(G); //0 flow
37 Preflow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> >
38 pre_flow_test(G, s, t, cap, flow, true);
39 MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> >
40 max_flow_test(G, s, t, cap, flow);
42 std::cout << "ListGraph ..." << std::endl;
45 std::cout << "preflow ..." << std::endl;
48 std::cout << "elapsed time: " << ts << std::endl;
49 std::cout << "flow value: "<< pre_flow_test.flowValue() << std::endl;
53 std::cout << "physical blocking flow augmentation ..." << std::endl;
54 FOR_EACH_LOC(Graph::EdgeIt, e, G) flow.set(e, 0);
57 while (max_flow_test.augmentOnBlockingFlow<MutableGraph>()) { ++i; }
58 std::cout << "elapsed time: " << ts << std::endl;
59 std::cout << "number of augmentation phases: " << i << std::endl;
60 std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
64 std::cout << "faster physical blocking flow augmentation ..." << std::endl;
65 FOR_EACH_LOC(Graph::EdgeIt, e, G) flow.set(e, 0);
68 while (max_flow_test.augmentOnBlockingFlow1<MutableGraph>()) { ++i; }
69 std::cout << "elapsed time: " << ts << std::endl;
70 std::cout << "number of augmentation phases: " << i << std::endl;
71 std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
75 std::cout << "on-the-fly blocking flow augmentation ..." << std::endl;
76 FOR_EACH_LOC(Graph::EdgeIt, e, G) flow.set(e, 0);
79 while (max_flow_test.augmentOnBlockingFlow2()) { ++i; }
80 std::cout << "elapsed time: " << ts << std::endl;
81 std::cout << "number of augmentation phases: " << i << std::endl;
82 std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
86 std::cout << "on-the-fly shortest path augmentation ..." << std::endl;
87 FOR_EACH_LOC(Graph::EdgeIt, e, G) flow.set(e, 0);
90 while (max_flow_test.augmentOnShortestPath()) { ++i; }
91 std::cout << "elapsed time: " << ts << std::endl;
92 std::cout << "number of augmentation phases: " << i << std::endl;
93 std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
99 typedef SmartGraph Graph;
100 typedef Graph::Node Node;
101 typedef Graph::EdgeIt EdgeIt;
105 Graph::EdgeMap<int> cap(G);
106 std::ifstream ins(in.c_str());
107 readDimacsMaxFlow(ins, G, s, t, cap);
110 Graph::EdgeMap<int> flow(G); //0 flow
111 Preflow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> >
112 pre_flow_test(G, s, t, cap, flow, true);
113 MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> >
114 max_flow_test(G, s, t, cap, flow);
116 std::cout << "SmatrGraph ..." << std::endl;
119 std::cout << "preflow ..." << std::endl;
120 FOR_EACH_LOC(Graph::EdgeIt, e, G) flow.set(e, 0);
123 std::cout << "elapsed time: " << ts << std::endl;
124 std::cout << "flow value: "<< pre_flow_test.flowValue() << std::endl;
128 std::cout << "physical blocking flow augmentation ..." << std::endl;
129 FOR_EACH_LOC(Graph::EdgeIt, e, G) flow.set(e, 0);
132 while (max_flow_test.augmentOnBlockingFlow<MutableGraph>()) { ++i; }
133 std::cout << "elapsed time: " << ts << std::endl;
134 std::cout << "number of augmentation phases: " << i << std::endl;
135 std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
139 std::cout << "faster physical blocking flow augmentation ..." << std::endl;
140 FOR_EACH_LOC(Graph::EdgeIt, e, G) flow.set(e, 0);
143 while (max_flow_test.augmentOnBlockingFlow1<MutableGraph>()) { ++i; }
144 std::cout << "elapsed time: " << ts << std::endl;
145 std::cout << "number of augmentation phases: " << i << std::endl;
146 std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
150 std::cout << "on-the-fly blocking flow augmentation ..." << std::endl;
151 FOR_EACH_LOC(Graph::EdgeIt, e, G) flow.set(e, 0);
154 while (max_flow_test.augmentOnBlockingFlow2()) { ++i; }
155 std::cout << "elapsed time: " << ts << std::endl;
156 std::cout << "number of augmentation phases: " << i << std::endl;
157 std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
161 std::cout << "on-the-fly shortest path augmentation ..." << std::endl;
162 FOR_EACH_LOC(Graph::EdgeIt, e, G) flow.set(e, 0);
165 while (max_flow_test.augmentOnShortestPath()) { ++i; }
166 std::cout << "elapsed time: " << ts << std::endl;
167 std::cout << "number of augmentation phases: " << i << std::endl;
168 std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;