| changeset 314 | eabbe162e32e |
| parent 305 | 6720705c9095 |
| child 317 | 6e6db1c49bc1 |
| 20:72c9890c2f28 | 21:ec4bad97c6b8 |
|---|---|
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 #include <preflow.h> |
12 class CM { |
|
13 public: |
|
14 template<typename T> int get(T) const {return 1;} |
|
15 }; |
|
16 |
12 |
17 using namespace hugo; |
13 using namespace hugo; |
18 |
14 |
19 // Use a DIMACS max flow file as stdin. |
15 // Use a DIMACS max flow file as stdin. |
20 // read_dimacs_demo < dimacs_max_flow_file |
16 // read_dimacs_demo < dimacs_max_flow_file |
86 // cgw./*getF*/first(csw); |
82 // cgw./*getF*/first(csw); |
87 // std::cout << "p1:" << cgw.nodeNum() << std::endl; |
83 // std::cout << "p1:" << cgw.nodeNum() << std::endl; |
88 // //cgw.erase(csw); |
84 // //cgw.erase(csw); |
89 // std::cout << "p2:" << cgw.nodeNum() << std::endl; |
85 // std::cout << "p2:" << cgw.nodeNum() << std::endl; |
90 |
86 |
91 |
87 { |
92 { |
88 std::cout << "preflow ..." << std::endl; |
93 std::cout << "edmonds karp demo (physical blocking flow augmentation)..." << std::endl; |
89 Graph::EdgeMap<int> flow(G); //0 flow |
90 |
|
91 Timer ts; |
|
92 ts.reset(); |
|
93 |
|
94 Preflow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> > |
|
95 max_flow_test(G, s, t, cap, flow); |
|
96 max_flow_test.run(); |
|
97 // int i=0; |
|
98 // while (max_flow_test.augmentOnBlockingFlow<MutableGraph>()) { |
|
99 // for(EdgeIt e=G.template first<EdgeIt>(); e.valid(); ++e) { |
|
100 // std::cout<<"("<<G.tail(e)<< "-"<<flow.get(e)<<"->"<<G.head(e)<<") "; |
|
101 // } |
|
102 // std::cout<<std::endl; |
|
103 // ++i; |
|
104 // } |
|
105 |
|
106 // std::cout << "maximum flow: "<< std::endl; |
|
107 // for(EdgeIt e=G.first<EdgeIt>(); e.valid(); ++e) { |
|
108 // std::cout<<"("<<G.tail(e)<< "-"<<flow.get(e)<<"->"<<G.head(e)<<") "; |
|
109 // } |
|
110 // std::cout<<std::endl; |
|
111 std::cout << "elapsed time: " << ts << std::endl; |
|
112 // std::cout << "number of augmentation phases: " << i << std::endl; |
|
113 std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl; |
|
114 } |
|
115 |
|
116 { |
|
117 std::cout << "physical blocking flow augmentation ..." << std::endl; |
|
94 Graph::EdgeMap<int> flow(G); //0 flow |
118 Graph::EdgeMap<int> flow(G); //0 flow |
95 |
119 |
96 Timer ts; |
120 Timer ts; |
97 ts.reset(); |
121 ts.reset(); |
98 |
122 |
116 std::cout << "number of augmentation phases: " << i << std::endl; |
140 std::cout << "number of augmentation phases: " << i << std::endl; |
117 std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl; |
141 std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl; |
118 } |
142 } |
119 |
143 |
120 { |
144 { |
121 std::cout << "edmonds karp demo (physical blocking flow 1 augmentation)..." << std::endl; |
145 std::cout << "faster physical blocking flow augmentation ..." << std::endl; |
122 Graph::EdgeMap<int> flow(G); //0 flow |
146 Graph::EdgeMap<int> flow(G); //0 flow |
123 |
147 |
124 Timer ts; |
148 Timer ts; |
125 ts.reset(); |
149 ts.reset(); |
126 |
150 |
144 std::cout << "number of augmentation phases: " << i << std::endl; |
168 std::cout << "number of augmentation phases: " << i << std::endl; |
145 std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl; |
169 std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl; |
146 } |
170 } |
147 |
171 |
148 { |
172 { |
149 std::cout << "edmonds karp demo (on-the-fly blocking flow augmentation)..." << std::endl; |
173 std::cout << "on-the-fly blocking flow augmentation ..." << std::endl; |
150 Graph::EdgeMap<int> flow(G); //0 flow |
174 Graph::EdgeMap<int> flow(G); //0 flow |
151 |
175 |
152 Timer ts; |
176 Timer ts; |
153 ts.reset(); |
177 ts.reset(); |
154 |
178 |
172 std::cout << "number of augmentation phases: " << i << std::endl; |
196 std::cout << "number of augmentation phases: " << i << std::endl; |
173 std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl; |
197 std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl; |
174 } |
198 } |
175 |
199 |
176 { |
200 { |
177 std::cout << "edmonds karp demo (on-the-fly shortest path augmentation)..." << std::endl; |
201 std::cout << "on-the-fly shortest path augmentation ..." << std::endl; |
178 Graph::EdgeMap<int> flow(G); //0 flow |
202 Graph::EdgeMap<int> flow(G); //0 flow |
179 |
203 |
180 Timer ts; |
204 Timer ts; |
181 ts.reset(); |
205 ts.reset(); |
182 |
206 |