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>
12 #include <preflowproba.h>
13 #include <for_each_macros.h>
17 // Use a DIMACS max flow file as stdin.
18 // read_dimacs_demo < dimacs_max_flow_file
28 // template <typename B>
36 int main(int, char **) {
38 typedef ListGraph MutableGraph;
40 // typedef SmartGraph Graph;
41 typedef ListGraph Graph;
42 typedef Graph::Node Node;
43 typedef Graph::EdgeIt EdgeIt;
49 // typedef Mize Tize[0];
51 // std::cout << &zize << " " << sizeof(mize) << sizeof(Tize) << std::endl;
52 // std::cout << sizeof(bize) << std::endl;
56 // std::cout << sizeof(k) << std::endl;
64 // std::cout << sizeof(Bumm) << std::endl;
69 Graph::EdgeMap<int> cap(G);
70 readDimacsMaxFlow(std::cin, G, s, t, cap);
72 Graph::EdgeMap<int> flow(G); //0 flow
73 Preflow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> >
74 pre_flow_test(G, s, t, cap, flow, true);
75 PreflowProba<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> >
76 pre_flow_proba(G, s, t, cap, flow, true, true);
77 MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> >
78 max_flow_test(G, s, t, cap, flow);
81 std::cout << "preflow ..." << std::endl;
84 std::cout << "elapsed time: " << ts << std::endl;
85 std::cout << "flow value: "<< pre_flow_test.flowValue() << std::endl;
89 std::cout << "wrapped preflow ..." << std::endl;
90 FOR_EACH_LOC(Graph::EdgeIt, e, G) flow.set(e, 0);
93 std::cout << "elapsed time: " << ts << std::endl;
94 std::cout << "flow value: "<< pre_flow_test.flowValue() << std::endl;
98 std::cout << "physical blocking flow augmentation ..." << std::endl;
99 FOR_EACH_LOC(Graph::EdgeIt, e, G) flow.set(e, 0);
102 while (max_flow_test.augmentOnBlockingFlow<MutableGraph>()) { ++i; }
103 std::cout << "elapsed time: " << ts << std::endl;
104 std::cout << "number of augmentation phases: " << i << std::endl;
105 std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
109 std::cout << "faster physical blocking flow augmentation ..." << std::endl;
110 FOR_EACH_LOC(Graph::EdgeIt, e, G) flow.set(e, 0);
113 while (max_flow_test.augmentOnBlockingFlow1<MutableGraph>()) { ++i; }
114 std::cout << "elapsed time: " << ts << std::endl;
115 std::cout << "number of augmentation phases: " << i << std::endl;
116 std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
120 std::cout << "on-the-fly blocking flow augmentation ..." << std::endl;
121 FOR_EACH_LOC(Graph::EdgeIt, e, G) flow.set(e, 0);
124 while (max_flow_test.augmentOnBlockingFlow2()) { ++i; }
125 std::cout << "elapsed time: " << ts << std::endl;
126 std::cout << "number of augmentation phases: " << i << std::endl;
127 std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
131 std::cout << "on-the-fly shortest path augmentation ..." << std::endl;
132 FOR_EACH_LOC(Graph::EdgeIt, e, G) flow.set(e, 0);
135 while (max_flow_test.augmentOnShortestPath()) { ++i; }
136 std::cout << "elapsed time: " << ts << std::endl;
137 std::cout << "number of augmentation phases: " << i << std::endl;
138 std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;