Naming conventions...
5 #include <list_graph.h>
6 #include <smart_graph.h>
8 #include <edmonds_karp.h>
9 #include <time_measure.h>
10 //#include <graph_wrapper.h>
15 // Use a DIMACS max flow file as stdin.
16 // read_dimacs_demo < dimacs_max_flow_file
26 // template <typename B>
34 int main(int, char **) {
36 typedef ListGraph MutableGraph;
38 // typedef SmartGraph Graph;
39 typedef ListGraph Graph;
40 typedef Graph::Node Node;
41 typedef Graph::EdgeIt EdgeIt;
47 // typedef Mize Tize[0];
49 // std::cout << &zize << " " << sizeof(mize) << sizeof(Tize) << std::endl;
50 // std::cout << sizeof(bize) << std::endl;
54 // std::cout << sizeof(k) << std::endl;
62 // std::cout << sizeof(Bumm) << std::endl;
67 Graph::EdgeMap<int> cap(G);
68 readDimacsMaxFlow(std::cin, G, s, t, cap);
71 std::cout << "preflow ..." << std::endl;
72 Graph::EdgeMap<int> flow(G); //0 flow
77 Preflow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> >
78 max_flow_test(G, s, t, cap, flow);
81 // while (max_flow_test.augmentOnBlockingFlow<MutableGraph>()) {
82 // for(EdgeIt e=G.template first<EdgeIt>(); e.valid(); ++e) {
83 // std::cout<<"("<<G.tail(e)<< "-"<<flow.get(e)<<"->"<<G.head(e)<<") ";
85 // std::cout<<std::endl;
89 // std::cout << "maximum flow: "<< std::endl;
90 // for(EdgeIt e=G.first<EdgeIt>(); e.valid(); ++e) {
91 // std::cout<<"("<<G.tail(e)<< "-"<<flow.get(e)<<"->"<<G.head(e)<<") ";
93 // std::cout<<std::endl;
94 std::cout << "elapsed time: " << ts << std::endl;
95 // std::cout << "number of augmentation phases: " << i << std::endl;
96 std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
100 std::cout << "physical blocking flow augmentation ..." << std::endl;
101 Graph::EdgeMap<int> flow(G); //0 flow
106 MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> >
107 max_flow_test(G, s, t, flow, cap);
109 while (max_flow_test.augmentOnBlockingFlow<MutableGraph>()) {
110 // for(EdgeIt e=G.template first<EdgeIt>(); e.valid(); ++e) {
111 // std::cout<<"("<<G.tail(e)<< "-"<<flow.get(e)<<"->"<<G.head(e)<<") ";
113 // std::cout<<std::endl;
117 // std::cout << "maximum flow: "<< std::endl;
118 // for(EdgeIt e=G.first<EdgeIt>(); e.valid(); ++e) {
119 // std::cout<<"("<<G.tail(e)<< "-"<<flow.get(e)<<"->"<<G.head(e)<<") ";
121 // std::cout<<std::endl;
122 std::cout << "elapsed time: " << ts << std::endl;
123 std::cout << "number of augmentation phases: " << i << std::endl;
124 std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
128 std::cout << "faster physical blocking flow augmentation ..." << std::endl;
129 Graph::EdgeMap<int> flow(G); //0 flow
134 MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> >
135 max_flow_test(G, s, t, flow, cap);
137 while (max_flow_test.augmentOnBlockingFlow1<MutableGraph>()) {
138 // for(EdgeIt e=G.template first<EdgeIt>(); e.valid(); ++e) {
139 // std::cout<<"("<<G.tail(e)<< "-"<<flow.get(e)<<"->"<<G.head(e)<<") ";
141 // std::cout<<std::endl;
145 // std::cout << "maximum flow: "<< std::endl;
146 // for(EdgeIt e=G.first<EdgeIt>(); e.valid(); ++e) {
147 // std::cout<<"("<<G.tail(e)<< "-"<<flow.get(e)<<"->"<<G.head(e)<<") ";
149 // std::cout<<std::endl;
150 std::cout << "elapsed time: " << ts << std::endl;
151 std::cout << "number of augmentation phases: " << i << std::endl;
152 std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
156 std::cout << "on-the-fly blocking flow augmentation ..." << std::endl;
157 Graph::EdgeMap<int> flow(G); //0 flow
162 MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> >
163 max_flow_test(G, s, t, flow, cap);
165 while (max_flow_test.augmentOnBlockingFlow2()) {
166 // for(EdgeIt e=G.template first<EdgeIt>(); e.valid(); ++e) {
167 // std::cout<<"("<<G.tail(e)<< "-"<<flow.get(e)<<"->"<<G.head(e)<<") ";
169 // std::cout<<std::endl;
173 // std::cout << "maximum flow: "<< std::endl;
174 // for(EdgeIt e=G.first<EdgeIt>(); e.valid(); ++e) {
175 // std::cout<<"("<<G.tail(e)<< "-"<<flow.get(e)<<"->"<<G.head(e)<<") ";
177 // std::cout<<std::endl;
178 std::cout << "elapsed time: " << ts << std::endl;
179 std::cout << "number of augmentation phases: " << i << std::endl;
180 std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
184 std::cout << "on-the-fly shortest path augmentation ..." << std::endl;
185 Graph::EdgeMap<int> flow(G); //0 flow
190 MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> >
191 max_flow_test(G, s, t, flow, cap);
193 while (max_flow_test.augmentOnShortestPath()) {
194 // for(EdgeIt e=G.template first<EdgeIt>(); e.valid(); ++e) {
195 // std::cout<<"("<<G.tail(e)<< "-"<<flow.get(e)<<"->"<<G.head(e)<<") ";
197 // std::cout<<std::endl;
201 // std::cout << "maximum flow: "<< std::endl;
202 // for(EdgeIt e=G.first<EdgeIt>(); e.valid(); ++e) {
203 // std::cout<<"("<<G.tail(e)<< "-"<<flow.get(e)<<"->"<<G.head(e)<<") ";
205 // std::cout<<std::endl;
206 std::cout << "elapsed time: " << ts << std::endl;
207 std::cout << "number of augmentation phases: " << i << std::endl;
208 std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;