Heap concept moved to namespace concept.
6 #include <sage_graph.h>
7 #include <lemon/list_graph.h>
8 #include <lemon/smart_graph.h>
9 #include <lemon/dimacs.h>
10 #include <lemon/max_flow.h>
11 #include <augmenting_flow.h>
12 #include <lemon/time_measure.h>
13 #include <for_each_macros.h>
15 using namespace lemon;
17 // Use a DIMACS max flow file as stdin.
18 // read_dimacs_demo dimacs_max_flow_file
20 int main(int, char** argv) {
22 std::string in=argv[1];
23 typedef SageGraph MutableGraph;
26 typedef SageGraph Graph;
27 typedef Graph::Node Node;
28 typedef Graph::EdgeIt EdgeIt;
32 Graph::EdgeMap<int> cap(g);
33 std::ifstream ins(in.c_str());
34 //readDimacsMaxFlow(ins, g, s, t, cap);
35 readDimacs(ins, g, cap, s, t);
38 Graph::EdgeMap<int> flow(g); //0 flow
39 MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> >
40 max_flow_test(g, s, t, cap, flow/*, true*/);
41 AugmentingFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> >
42 augmenting_flow_test(g, s, t, cap, flow/*, true*/);
44 std::cout << "SageGraph ..." << std::endl;
47 std::cout << "preflow ..." << std::endl;
50 std::cout << "elapsed time: " << ts << std::endl;
51 std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
55 std::cout << "physical blocking flow augmentation ..." << std::endl;
56 for (Graph::EdgeIt e(g); e!=INVALID; ++e) flow.set(e, 0);
59 while (augmenting_flow_test.augmentOnBlockingFlow<MutableGraph>()) { ++i; }
60 std::cout << "elapsed time: " << ts << std::endl;
61 std::cout << "number of augmentation phases: " << i << std::endl;
62 std::cout << "flow value: "<< augmenting_flow_test.flowValue() << std::endl;
66 // std::cout << "faster physical blocking flow augmentation ..." << std::endl;
67 // FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0);
70 // while (max_flow_test.augmentOnBlockingFlow1<MutableGraph>()) { ++i; }
71 // std::cout << "elapsed time: " << ts << std::endl;
72 // std::cout << "number of augmentation phases: " << i << std::endl;
73 // std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
77 std::cout << "on-the-fly blocking flow augmentation ..." << std::endl;
78 for (Graph::EdgeIt e(g); e!=INVALID; ++e) flow.set(e, 0);
81 while (augmenting_flow_test.augmentOnBlockingFlow2()) { ++i; }
82 std::cout << "elapsed time: " << ts << std::endl;
83 std::cout << "number of augmentation phases: " << i << std::endl;
84 std::cout << "flow value: "<< augmenting_flow_test.flowValue() << std::endl;
88 std::cout << "on-the-fly shortest path augmentation ..." << std::endl;
89 for (Graph::EdgeIt e(g); e!=INVALID; ++e) flow.set(e, 0);
92 while (augmenting_flow_test.augmentOnShortestPath()) { ++i; }
93 std::cout << "elapsed time: " << ts << std::endl;
94 std::cout << "number of augmentation phases: " << i << std::endl;
95 std::cout << "flow value: "<< augmenting_flow_test.flowValue() << std::endl;
100 typedef SmartGraph Graph;
101 typedef Graph::Node Node;
102 typedef Graph::EdgeIt EdgeIt;
106 Graph::EdgeMap<int> cap(g);
107 std::ifstream ins(in.c_str());
108 //readDimacsMaxFlow(ins, g, s, t, cap);
109 readDimacs(ins, g, cap, s, t);
112 Graph::EdgeMap<int> flow(g); //0 flow
113 MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> >
114 max_flow_test(g, s, t, cap, flow/*, true*/);
115 AugmentingFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> >
116 augmenting_flow_test(g, s, t, cap, flow/*, true*/);
117 // MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> >
118 // max_flow_test(g, s, t, cap, flow);
120 std::cout << "SmartGraph ..." << std::endl;
123 std::cout << "preflow ..." << std::endl;
124 for (Graph::EdgeIt e(g); e!=INVALID; ++e) flow.set(e, 0);
127 std::cout << "elapsed time: " << ts << std::endl;
128 std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
132 std::cout << "physical blocking flow augmentation ..." << std::endl;
133 for (Graph::EdgeIt e(g); e!=INVALID; ++e) flow.set(e, 0);
136 while (augmenting_flow_test.augmentOnBlockingFlow<MutableGraph>()) { ++i; }
137 std::cout << "elapsed time: " << ts << std::endl;
138 std::cout << "number of augmentation phases: " << i << std::endl;
139 std::cout << "flow value: "<< augmenting_flow_test.flowValue() << std::endl;
143 // std::cout << "faster physical blocking flow augmentation ..." << std::endl;
144 // FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0);
147 // while (max_flow_test.augmentOnBlockingFlow1<MutableGraph>()) { ++i; }
148 // std::cout << "elapsed time: " << ts << std::endl;
149 // std::cout << "number of augmentation phases: " << i << std::endl;
150 // std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
154 std::cout << "on-the-fly blocking flow augmentation ..." << std::endl;
155 for (Graph::EdgeIt e(g); e!=INVALID; ++e) flow.set(e, 0);
158 while (augmenting_flow_test.augmentOnBlockingFlow2()) { ++i; }
159 std::cout << "elapsed time: " << ts << std::endl;
160 std::cout << "number of augmentation phases: " << i << std::endl;
161 std::cout << "flow value: "<< augmenting_flow_test.flowValue() << std::endl;
165 std::cout << "on-the-fly shortest path augmentation ..." << std::endl;
166 for (Graph::EdgeIt e(g); e!=INVALID; ++e) flow.set(e, 0);
169 while (augmenting_flow_test.augmentOnShortestPath()) { ++i; }
170 std::cout << "elapsed time: " << ts << std::endl;
171 std::cout << "number of augmentation phases: " << i << std::endl;
172 std::cout << "flow value: "<< augmenting_flow_test.flowValue() << std::endl;
177 typedef ListGraph Graph;
178 typedef Graph::Node Node;
179 typedef Graph::EdgeIt EdgeIt;
183 Graph::EdgeMap<int> cap(g);
184 std::ifstream ins(in.c_str());
185 //readDimacsMaxFlow(ins, g, s, t, cap);
186 readDimacs(ins, g, cap, s, t);
189 Graph::EdgeMap<int> flow(g); //0 flow
190 MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> >
191 max_flow_test(g, s, t, cap, flow/*, true*/);
192 AugmentingFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> >
193 augmenting_flow_test(g, s, t, cap, flow/*, true*/);
194 // MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> >
195 // max_flow_test(g, s, t, cap, flow);
197 std::cout << "ListGraph ..." << std::endl;
200 std::cout << "preflow ..." << std::endl;
201 for (Graph::EdgeIt e(g); e!=INVALID; ++e) flow.set(e, 0);
204 std::cout << "elapsed time: " << ts << std::endl;
205 std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
209 std::cout << "physical blocking flow augmentation ..." << std::endl;
210 for (Graph::EdgeIt e(g); e!=INVALID; ++e) flow.set(e, 0);
213 while (augmenting_flow_test.augmentOnBlockingFlow<MutableGraph>()) { ++i; }
214 std::cout << "elapsed time: " << ts << std::endl;
215 std::cout << "number of augmentation phases: " << i << std::endl;
216 std::cout << "flow value: "<< augmenting_flow_test.flowValue() << std::endl;
220 // std::cout << "faster physical blocking flow augmentation ..." << std::endl;
221 // FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0);
224 // while (max_flow_test.augmentOnBlockingFlow1<MutableGraph>()) { ++i; }
225 // std::cout << "elapsed time: " << ts << std::endl;
226 // std::cout << "number of augmentation phases: " << i << std::endl;
227 // std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
231 std::cout << "on-the-fly blocking flow augmentation ..." << std::endl;
232 for (Graph::EdgeIt e(g); e!=INVALID; ++e) flow.set(e, 0);
235 while (augmenting_flow_test.augmentOnBlockingFlow2()) { ++i; }
236 std::cout << "elapsed time: " << ts << std::endl;
237 std::cout << "number of augmentation phases: " << i << std::endl;
238 std::cout << "flow value: "<< augmenting_flow_test.flowValue() << std::endl;
242 std::cout << "on-the-fly shortest path augmentation ..." << std::endl;
243 for (Graph::EdgeIt e(g); e!=INVALID; ++e) flow.set(e, 0);
246 while (augmenting_flow_test.augmentOnShortestPath()) { ++i; }
247 std::cout << "elapsed time: " << ts << std::endl;
248 std::cout << "number of augmentation phases: " << i << std::endl;
249 std::cout << "flow value: "<< augmenting_flow_test.flowValue() << std::endl;