1 // -*- c++ -*- |
1 // -*- c++ -*- |
2 #include <iostream> |
2 #include <iostream> |
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 |
11 |
12 class CM { |
12 class CM { |
13 public: |
13 public: |
14 template<typename T> int get(T) const {return 1;} |
14 template<typename T> int get(T) const {return 1;} |
15 }; |
15 }; |
88 // //cgw.erase(csw); |
88 // //cgw.erase(csw); |
89 // std::cout << "p2:" << cgw.nodeNum() << std::endl; |
89 // std::cout << "p2:" << cgw.nodeNum() << std::endl; |
90 |
90 |
91 |
91 |
92 { |
92 { |
93 typedef TrivGraphWrapper<const Graph> GW; |
|
94 GW gw(G); |
|
95 std::cout << "edmonds karp demo (physical blocking flow augmentation)..." << std::endl; |
93 std::cout << "edmonds karp demo (physical blocking flow augmentation)..." << std::endl; |
96 GW::EdgeMap<int> flow(gw); //0 flow |
94 Graph::EdgeMap<int> flow(G); //0 flow |
97 |
95 |
98 Timer ts; |
96 Timer ts; |
99 ts.reset(); |
97 ts.reset(); |
100 |
98 |
101 typedef GW::EdgeMapWrapper< Graph::EdgeMap<int>, int > EMW; |
99 MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> > |
102 EMW cw(cap); |
100 max_flow_test(G, s, t, flow, cap); |
103 MaxFlow<GW, int, GW::EdgeMap<int>, EMW > max_flow_test(gw, s, t, flow, cw); |
|
104 int i=0; |
101 int i=0; |
105 while (max_flow_test.augmentOnBlockingFlow<MutableGraph>()) { |
102 while (max_flow_test.augmentOnBlockingFlow<MutableGraph>()) { |
106 // for(EdgeIt e=G.template first<EdgeIt>(); e.valid(); ++e) { |
103 // for(EdgeIt e=G.template first<EdgeIt>(); e.valid(); ++e) { |
107 // std::cout<<"("<<G.tail(e)<< "-"<<flow.get(e)<<"->"<<G.head(e)<<") "; |
104 // std::cout<<"("<<G.tail(e)<< "-"<<flow.get(e)<<"->"<<G.head(e)<<") "; |
108 // } |
105 // } |
119 std::cout << "number of augmentation phases: " << i << std::endl; |
116 std::cout << "number of augmentation phases: " << i << std::endl; |
120 std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl; |
117 std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl; |
121 } |
118 } |
122 |
119 |
123 { |
120 { |
124 typedef TrivGraphWrapper<const Graph> GW; |
|
125 GW gw(G); |
|
126 std::cout << "edmonds karp demo (physical blocking flow 1 augmentation)..." << std::endl; |
121 std::cout << "edmonds karp demo (physical blocking flow 1 augmentation)..." << std::endl; |
127 GW::EdgeMap<int> flow(gw); //0 flow |
122 Graph::EdgeMap<int> flow(G); //0 flow |
128 |
123 |
129 Timer ts; |
124 Timer ts; |
130 ts.reset(); |
125 ts.reset(); |
131 |
126 |
132 typedef GW::EdgeMapWrapper< Graph::EdgeMap<int>, int > EMW; |
127 MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> > |
133 EMW cw(cap); |
128 max_flow_test(G, s, t, flow, cap); |
134 MaxFlow<GW, int, GW::EdgeMap<int>, EMW > max_flow_test(gw, s, t, flow, cw); |
|
135 int i=0; |
129 int i=0; |
136 while (max_flow_test.augmentOnBlockingFlow1<MutableGraph>()) { |
130 while (max_flow_test.augmentOnBlockingFlow1<MutableGraph>()) { |
137 // for(EdgeIt e=G.template first<EdgeIt>(); e.valid(); ++e) { |
131 // for(EdgeIt e=G.template first<EdgeIt>(); e.valid(); ++e) { |
138 // std::cout<<"("<<G.tail(e)<< "-"<<flow.get(e)<<"->"<<G.head(e)<<") "; |
132 // std::cout<<"("<<G.tail(e)<< "-"<<flow.get(e)<<"->"<<G.head(e)<<") "; |
139 // } |
133 // } |
150 std::cout << "number of augmentation phases: " << i << std::endl; |
144 std::cout << "number of augmentation phases: " << i << std::endl; |
151 std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl; |
145 std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl; |
152 } |
146 } |
153 |
147 |
154 { |
148 { |
155 typedef TrivGraphWrapper<const Graph> GW; |
|
156 GW gw(G); |
|
157 std::cout << "edmonds karp demo (on-the-fly blocking flow augmentation)..." << std::endl; |
149 std::cout << "edmonds karp demo (on-the-fly blocking flow augmentation)..." << std::endl; |
158 GW::EdgeMap<int> flow(gw); //0 flow |
150 Graph::EdgeMap<int> flow(G); //0 flow |
159 |
151 |
160 Timer ts; |
152 Timer ts; |
161 ts.reset(); |
153 ts.reset(); |
162 |
154 |
163 typedef GW::EdgeMapWrapper< Graph::EdgeMap<int>, int > EMW; |
155 MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> > |
164 EMW cw(cap); |
156 max_flow_test(G, s, t, flow, cap); |
165 MaxFlow<GW, int, GW::EdgeMap<int>, EMW > max_flow_test(gw, s, t, flow, cw); |
|
166 int i=0; |
157 int i=0; |
167 while (max_flow_test.augmentOnBlockingFlow2()) { |
158 while (max_flow_test.augmentOnBlockingFlow2()) { |
168 // for(EdgeIt e=G.template first<EdgeIt>(); e.valid(); ++e) { |
159 // for(EdgeIt e=G.template first<EdgeIt>(); e.valid(); ++e) { |
169 // std::cout<<"("<<G.tail(e)<< "-"<<flow.get(e)<<"->"<<G.head(e)<<") "; |
160 // std::cout<<"("<<G.tail(e)<< "-"<<flow.get(e)<<"->"<<G.head(e)<<") "; |
170 // } |
161 // } |
181 std::cout << "number of augmentation phases: " << i << std::endl; |
172 std::cout << "number of augmentation phases: " << i << std::endl; |
182 std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl; |
173 std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl; |
183 } |
174 } |
184 |
175 |
185 { |
176 { |
186 typedef TrivGraphWrapper<const Graph> GW; |
|
187 GW gw(G); |
|
188 std::cout << "edmonds karp demo (on-the-fly shortest path augmentation)..." << std::endl; |
177 std::cout << "edmonds karp demo (on-the-fly shortest path augmentation)..." << std::endl; |
189 GW::EdgeMap<int> flow(gw); //0 flow |
178 Graph::EdgeMap<int> flow(G); //0 flow |
190 |
179 |
191 Timer ts; |
180 Timer ts; |
192 ts.reset(); |
181 ts.reset(); |
193 |
182 |
194 typedef GW::EdgeMapWrapper< Graph::EdgeMap<int>, int > EMW; |
183 MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> > |
195 EMW cw(cap); |
184 max_flow_test(G, s, t, flow, cap); |
196 MaxFlow<GW, int, GW::EdgeMap<int>, EMW> max_flow_test(gw, s, t, flow, cw); |
|
197 int i=0; |
185 int i=0; |
198 while (max_flow_test.augmentOnShortestPath()) { |
186 while (max_flow_test.augmentOnShortestPath()) { |
199 // for(EdgeIt e=G.template first<EdgeIt>(); e.valid(); ++e) { |
187 // for(EdgeIt e=G.template first<EdgeIt>(); e.valid(); ++e) { |
200 // std::cout<<"("<<G.tail(e)<< "-"<<flow.get(e)<<"->"<<G.head(e)<<") "; |
188 // std::cout<<"("<<G.tail(e)<< "-"<<flow.get(e)<<"->"<<G.head(e)<<") "; |
201 // } |
189 // } |