3 #include <fstream> |
3 #include <fstream> |
4 |
4 |
5 #include <list_graph.h> |
5 #include <list_graph.h> |
6 #include <smart_graph.h> |
6 #include <smart_graph.h> |
7 #include <dimacs.h> |
7 #include <dimacs.h> |
8 #include <edmonds_karp.h> |
8 //#include <edmonds_karp.h> |
9 #include <time_measure.h> |
9 #include <time_measure.h> |
10 //#include <graph_wrapper.h> |
10 //#include <graph_wrapper.h> |
11 #include <preflow.h> |
11 #include <preflow.h> |
12 #include <preflow_res.h> |
12 //#include <preflow_res.h> |
13 #include <for_each_macros.h> |
13 #include <for_each_macros.h> |
14 |
14 |
15 using namespace hugo; |
15 using namespace hugo; |
16 |
16 |
17 // Use a DIMACS max flow file as stdin. |
17 // Use a DIMACS max flow file as stdin. |
70 readDimacsMaxFlow(std::cin, G, s, t, cap); |
70 readDimacsMaxFlow(std::cin, G, s, t, cap); |
71 Timer ts; |
71 Timer ts; |
72 Graph::EdgeMap<int> flow(G); //0 flow |
72 Graph::EdgeMap<int> flow(G); //0 flow |
73 Preflow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> > |
73 Preflow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> > |
74 pre_flow_test(G, s, t, cap, flow/*, true*/); |
74 pre_flow_test(G, s, t, cap, flow/*, true*/); |
75 Preflow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> > |
75 // Preflow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> > |
76 pre_flow_ize(G, s, t, cap, flow/*, false*/); |
76 // pre_flow_ize(G, s, t, cap, flow/*, false*/); |
77 // PreflowRes<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> > |
77 // PreflowRes<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> > |
78 // pre_flow_res(G, s, t, cap, flow/*, true*/); |
78 // pre_flow_res(G, s, t, cap, flow/*, true*/); |
79 MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> > |
79 //MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> > |
80 max_flow_test(G, s, t, cap, flow); |
80 // max_flow_test(G, s, t, cap, flow); |
81 |
81 |
82 { |
82 { |
83 std::cout << "preflow ..." << std::endl; |
83 std::cout << "preflow ..." << std::endl; |
84 ts.reset(); |
84 ts.reset(); |
85 pre_flow_test.run(); |
85 pre_flow_test.run(); |
89 |
89 |
90 { |
90 { |
91 std::cout << "preflow ..." << std::endl; |
91 std::cout << "preflow ..." << std::endl; |
92 FOR_EACH_LOC(Graph::EdgeIt, e, G) flow.set(e, 0); |
92 FOR_EACH_LOC(Graph::EdgeIt, e, G) flow.set(e, 0); |
93 ts.reset(); |
93 ts.reset(); |
94 pre_flow_ize.preflow(Preflow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> >::GEN_FLOW); |
94 pre_flow_test.preflow(Preflow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> >::GEN_FLOW); |
95 std::cout << "elapsed time: " << ts << std::endl; |
95 std::cout << "elapsed time: " << ts << std::endl; |
96 std::cout << "flow value: "<< pre_flow_ize.flowValue() << std::endl; |
96 std::cout << "flow value: "<< pre_flow_test.flowValue() << std::endl; |
97 } |
97 } |
98 |
98 |
99 // { |
99 // { |
100 // std::cout << "wrapped preflow ..." << std::endl; |
100 // std::cout << "wrapped preflow ..." << std::endl; |
101 // FOR_EACH_LOC(Graph::EdgeIt, e, G) flow.set(e, 0); |
101 // FOR_EACH_LOC(Graph::EdgeIt, e, G) flow.set(e, 0); |
108 { |
108 { |
109 std::cout << "physical blocking flow augmentation ..." << std::endl; |
109 std::cout << "physical blocking flow augmentation ..." << std::endl; |
110 FOR_EACH_LOC(Graph::EdgeIt, e, G) flow.set(e, 0); |
110 FOR_EACH_LOC(Graph::EdgeIt, e, G) flow.set(e, 0); |
111 ts.reset(); |
111 ts.reset(); |
112 int i=0; |
112 int i=0; |
113 while (max_flow_test.augmentOnBlockingFlow<MutableGraph>()) { ++i; } |
113 while (pre_flow_test.augmentOnBlockingFlow<MutableGraph>()) { ++i; } |
114 std::cout << "elapsed time: " << ts << std::endl; |
114 std::cout << "elapsed time: " << ts << std::endl; |
115 std::cout << "number of augmentation phases: " << i << std::endl; |
115 std::cout << "number of augmentation phases: " << i << std::endl; |
116 std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl; |
116 std::cout << "flow value: "<< pre_flow_test.flowValue() << std::endl; |
117 } |
117 } |
118 |
118 |
119 { |
119 // { |
120 std::cout << "faster physical blocking flow augmentation ..." << std::endl; |
120 // std::cout << "faster physical blocking flow augmentation ..." << std::endl; |
121 FOR_EACH_LOC(Graph::EdgeIt, e, G) flow.set(e, 0); |
121 // FOR_EACH_LOC(Graph::EdgeIt, e, G) flow.set(e, 0); |
122 ts.reset(); |
122 // ts.reset(); |
123 int i=0; |
123 // int i=0; |
124 while (max_flow_test.augmentOnBlockingFlow1<MutableGraph>()) { ++i; } |
124 // while (max_flow_test.augmentOnBlockingFlow1<MutableGraph>()) { ++i; } |
125 std::cout << "elapsed time: " << ts << std::endl; |
125 // std::cout << "elapsed time: " << ts << std::endl; |
126 std::cout << "number of augmentation phases: " << i << std::endl; |
126 // std::cout << "number of augmentation phases: " << i << std::endl; |
127 std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl; |
127 // std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl; |
128 } |
128 // } |
129 |
129 |
130 { |
130 { |
131 std::cout << "on-the-fly blocking flow augmentation ..." << std::endl; |
131 std::cout << "on-the-fly blocking flow augmentation ..." << std::endl; |
132 FOR_EACH_LOC(Graph::EdgeIt, e, G) flow.set(e, 0); |
132 FOR_EACH_LOC(Graph::EdgeIt, e, G) flow.set(e, 0); |
133 ts.reset(); |
133 ts.reset(); |
134 int i=0; |
134 int i=0; |
135 while (max_flow_test.augmentOnBlockingFlow2()) { ++i; } |
135 while (pre_flow_test.augmentOnBlockingFlow2()) { ++i; } |
136 std::cout << "elapsed time: " << ts << std::endl; |
136 std::cout << "elapsed time: " << ts << std::endl; |
137 std::cout << "number of augmentation phases: " << i << std::endl; |
137 std::cout << "number of augmentation phases: " << i << std::endl; |
138 std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl; |
138 std::cout << "flow value: "<< pre_flow_test.flowValue() << std::endl; |
139 } |
139 } |
140 |
140 |
141 { |
141 { |
142 std::cout << "on-the-fly shortest path augmentation ..." << std::endl; |
142 std::cout << "on-the-fly shortest path augmentation ..." << std::endl; |
143 FOR_EACH_LOC(Graph::EdgeIt, e, G) flow.set(e, 0); |
143 FOR_EACH_LOC(Graph::EdgeIt, e, G) flow.set(e, 0); |
144 ts.reset(); |
144 ts.reset(); |
145 int i=0; |
145 int i=0; |
146 while (max_flow_test.augmentOnShortestPath()) { ++i; } |
146 while (pre_flow_test.augmentOnShortestPath()) { ++i; } |
147 std::cout << "elapsed time: " << ts << std::endl; |
147 std::cout << "elapsed time: " << ts << std::endl; |
148 std::cout << "number of augmentation phases: " << i << std::endl; |
148 std::cout << "number of augmentation phases: " << i << std::endl; |
149 std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl; |
149 std::cout << "flow value: "<< pre_flow_test.flowValue() << std::endl; |
150 } |
150 } |
151 |
151 |
152 |
152 |
153 return 0; |
153 return 0; |
154 } |
154 } |