1 // -*- c++ -*- |
|
2 #include <iostream> |
|
3 #include <fstream> |
|
4 |
|
5 #include <list_graph.h> |
|
6 //#include <smart_graph.h> |
|
7 #include <dimacs.h> |
|
8 #include <edmonds_karp_1.h> |
|
9 #include <time_measure.h> |
|
10 #include <graph_wrapper_1.h> |
|
11 |
|
12 class CM { |
|
13 public: |
|
14 template<typename T> int get(T) const {return 1;} |
|
15 }; |
|
16 |
|
17 using namespace lemon; |
|
18 |
|
19 // Use a DIMACS max flow file as stdin. |
|
20 // read_dimacs_demo < dimacs_max_flow_file |
|
21 |
|
22 |
|
23 // struct Ize { |
|
24 // }; |
|
25 |
|
26 // struct Mize { |
|
27 // Ize bumm; |
|
28 // }; |
|
29 |
|
30 // template <typename B> |
|
31 // class Huha { |
|
32 // public: |
|
33 // int u; |
|
34 // B brr; |
|
35 // }; |
|
36 |
|
37 |
|
38 int main(int, char **) { |
|
39 |
|
40 typedef ListGraph MutableGraph; |
|
41 |
|
42 //typedef SmartGraph Graph; |
|
43 typedef ListGraph Graph; |
|
44 typedef Graph::Node Node; |
|
45 typedef Graph::EdgeIt EdgeIt; |
|
46 |
|
47 |
|
48 // Mize mize[10]; |
|
49 // Mize bize[0]; |
|
50 // Mize zize; |
|
51 // typedef Mize Tize[0]; |
|
52 |
|
53 // std::cout << &zize << " " << sizeof(mize) << sizeof(Tize) << std::endl; |
|
54 // std::cout << sizeof(bize) << std::endl; |
|
55 |
|
56 |
|
57 // Huha<Tize> k; |
|
58 // std::cout << sizeof(k) << std::endl; |
|
59 |
|
60 |
|
61 // struct Bumm { |
|
62 // //int a; |
|
63 // bool b; |
|
64 // }; |
|
65 |
|
66 // std::cout << sizeof(Bumm) << std::endl; |
|
67 |
|
68 |
|
69 Graph G; |
|
70 Node s, t; |
|
71 Graph::EdgeMap<int> cap(G); |
|
72 readDimacsMaxFlow(std::cin, G, s, t, cap); |
|
73 |
|
74 // typedef TrivGraphWrapper<Graph> TGW; |
|
75 // TGW gw(G); |
|
76 // TGW::NodeIt sw; |
|
77 // gw./*getF*/first(sw); |
|
78 // std::cout << "p1:" << gw.nodeNum() << std::endl; |
|
79 // gw.erase(sw); |
|
80 // std::cout << "p2:" << gw.nodeNum() << std::endl; |
|
81 |
|
82 // typedef const Graph cLG; |
|
83 // typedef TrivGraphWrapper<const cLG> CTGW; |
|
84 // CTGW cgw(G); |
|
85 // CTGW::NodeIt csw; |
|
86 // cgw./*getF*/first(csw); |
|
87 // std::cout << "p1:" << cgw.nodeNum() << std::endl; |
|
88 // //cgw.erase(csw); |
|
89 // std::cout << "p2:" << cgw.nodeNum() << std::endl; |
|
90 |
|
91 |
|
92 { |
|
93 typedef TrivGraphWrapper<const Graph> GW; |
|
94 GW gw(G); |
|
95 std::cout << "edmonds karp demo (physical blocking flow augmentation)..." << std::endl; |
|
96 GW::EdgeMap<int> flow(gw); //0 flow |
|
97 |
|
98 Timer ts; |
|
99 ts.reset(); |
|
100 |
|
101 typedef GW::EdgeMapWrapper< Graph::EdgeMap<int>, int > EMW; |
|
102 EMW cw(cap); |
|
103 MaxFlow<GW, int, GW::EdgeMap<int>, EMW > max_flow_test(gw, s, t, flow, cw); |
|
104 int i=0; |
|
105 while (max_flow_test.augmentOnBlockingFlow<MutableGraph>()) { |
|
106 // for(EdgeIt e=G.template first<EdgeIt>(); e.valid(); ++e) { |
|
107 // std::cout<<"("<<G.source(e)<< "-"<<flow.get(e)<<"->"<<G.target(e)<<") "; |
|
108 // } |
|
109 // std::cout<<std::endl; |
|
110 ++i; |
|
111 } |
|
112 |
|
113 // std::cout << "maximum flow: "<< std::endl; |
|
114 // for(EdgeIt e=G.first<EdgeIt>(); e.valid(); ++e) { |
|
115 // std::cout<<"("<<G.source(e)<< "-"<<flow.get(e)<<"->"<<G.target(e)<<") "; |
|
116 // } |
|
117 // std::cout<<std::endl; |
|
118 std::cout << "elapsed time: " << ts << std::endl; |
|
119 std::cout << "number of augmentation phases: " << i << std::endl; |
|
120 std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl; |
|
121 } |
|
122 |
|
123 { |
|
124 typedef TrivGraphWrapper<const Graph> GW; |
|
125 GW gw(G); |
|
126 std::cout << "edmonds karp demo (physical blocking flow 1 augmentation)..." << std::endl; |
|
127 GW::EdgeMap<int> flow(gw); //0 flow |
|
128 |
|
129 Timer ts; |
|
130 ts.reset(); |
|
131 |
|
132 typedef GW::EdgeMapWrapper< Graph::EdgeMap<int>, int > EMW; |
|
133 EMW cw(cap); |
|
134 MaxFlow<GW, int, GW::EdgeMap<int>, EMW > max_flow_test(gw, s, t, flow, cw); |
|
135 int i=0; |
|
136 while (max_flow_test.augmentOnBlockingFlow1<MutableGraph>()) { |
|
137 // for(EdgeIt e=G.template first<EdgeIt>(); e.valid(); ++e) { |
|
138 // std::cout<<"("<<G.source(e)<< "-"<<flow.get(e)<<"->"<<G.target(e)<<") "; |
|
139 // } |
|
140 // std::cout<<std::endl; |
|
141 ++i; |
|
142 } |
|
143 |
|
144 // std::cout << "maximum flow: "<< std::endl; |
|
145 // for(EdgeIt e=G.first<EdgeIt>(); e.valid(); ++e) { |
|
146 // std::cout<<"("<<G.source(e)<< "-"<<flow.get(e)<<"->"<<G.target(e)<<") "; |
|
147 // } |
|
148 // std::cout<<std::endl; |
|
149 std::cout << "elapsed time: " << ts << std::endl; |
|
150 std::cout << "number of augmentation phases: " << i << std::endl; |
|
151 std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl; |
|
152 } |
|
153 |
|
154 { |
|
155 typedef TrivGraphWrapper<const Graph> GW; |
|
156 GW gw(G); |
|
157 std::cout << "edmonds karp demo (on-the-fly blocking flow augmentation)..." << std::endl; |
|
158 GW::EdgeMap<int> flow(gw); //0 flow |
|
159 |
|
160 Timer ts; |
|
161 ts.reset(); |
|
162 |
|
163 typedef GW::EdgeMapWrapper< Graph::EdgeMap<int>, int > EMW; |
|
164 EMW cw(cap); |
|
165 MaxFlow<GW, int, GW::EdgeMap<int>, EMW > max_flow_test(gw, s, t, flow, cw); |
|
166 int i=0; |
|
167 while (max_flow_test.augmentOnBlockingFlow2()) { |
|
168 // for(EdgeIt e=G.template first<EdgeIt>(); e.valid(); ++e) { |
|
169 // std::cout<<"("<<G.source(e)<< "-"<<flow.get(e)<<"->"<<G.target(e)<<") "; |
|
170 // } |
|
171 // std::cout<<std::endl; |
|
172 ++i; |
|
173 } |
|
174 |
|
175 // std::cout << "maximum flow: "<< std::endl; |
|
176 // for(EdgeIt e=G.first<EdgeIt>(); e.valid(); ++e) { |
|
177 // std::cout<<"("<<G.source(e)<< "-"<<flow.get(e)<<"->"<<G.target(e)<<") "; |
|
178 // } |
|
179 // std::cout<<std::endl; |
|
180 std::cout << "elapsed time: " << ts << std::endl; |
|
181 std::cout << "number of augmentation phases: " << i << std::endl; |
|
182 std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl; |
|
183 } |
|
184 |
|
185 { |
|
186 typedef TrivGraphWrapper<const Graph> GW; |
|
187 GW gw(G); |
|
188 std::cout << "edmonds karp demo (on-the-fly shortest path augmentation)..." << std::endl; |
|
189 GW::EdgeMap<int> flow(gw); //0 flow |
|
190 |
|
191 Timer ts; |
|
192 ts.reset(); |
|
193 |
|
194 typedef GW::EdgeMapWrapper< Graph::EdgeMap<int>, int > EMW; |
|
195 EMW cw(cap); |
|
196 MaxFlow<GW, int, GW::EdgeMap<int>, EMW> max_flow_test(gw, s, t, flow, cw); |
|
197 int i=0; |
|
198 while (max_flow_test.augmentOnShortestPath()) { |
|
199 // for(EdgeIt e=G.template first<EdgeIt>(); e.valid(); ++e) { |
|
200 // std::cout<<"("<<G.source(e)<< "-"<<flow.get(e)<<"->"<<G.target(e)<<") "; |
|
201 // } |
|
202 // std::cout<<std::endl; |
|
203 ++i; |
|
204 } |
|
205 |
|
206 // std::cout << "maximum flow: "<< std::endl; |
|
207 // for(EdgeIt e=G.first<EdgeIt>(); e.valid(); ++e) { |
|
208 // std::cout<<"("<<G.source(e)<< "-"<<flow.get(e)<<"->"<<G.target(e)<<") "; |
|
209 // } |
|
210 // std::cout<<std::endl; |
|
211 std::cout << "elapsed time: " << ts << std::endl; |
|
212 std::cout << "number of augmentation phases: " << i << std::endl; |
|
213 std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl; |
|
214 } |
|
215 |
|
216 |
|
217 return 0; |
|
218 } |
|