Some more docs.
Put it into the 'misc' group.
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 <preflow_res.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 Preflow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> >
76 pre_flow_ize(G, s, t, cap, flow, false);
77 PreflowRes<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> >
78 pre_flow_res(G, s, t, cap, flow, true);
79 MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> >
80 max_flow_test(G, s, t, cap, flow);
83 std::cout << "preflow ..." << std::endl;
86 std::cout << "elapsed time: " << ts << std::endl;
87 std::cout << "flow value: "<< pre_flow_test.flowValue() << std::endl;
91 std::cout << "preflow ..." << std::endl;
92 FOR_EACH_LOC(Graph::EdgeIt, e, G) flow.set(e, 0);
95 std::cout << "elapsed time: " << ts << std::endl;
96 std::cout << "flow value: "<< pre_flow_ize.flowValue() << std::endl;
100 std::cout << "wrapped preflow ..." << std::endl;
101 FOR_EACH_LOC(Graph::EdgeIt, e, G) flow.set(e, 0);
104 std::cout << "elapsed time: " << ts << std::endl;
105 std::cout << "flow value: "<< pre_flow_test.flowValue() << std::endl;
109 std::cout << "physical blocking flow augmentation ..." << std::endl;
110 FOR_EACH_LOC(Graph::EdgeIt, e, G) flow.set(e, 0);
113 while (max_flow_test.augmentOnBlockingFlow<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 << "faster physical blocking flow augmentation ..." << std::endl;
121 FOR_EACH_LOC(Graph::EdgeIt, e, G) flow.set(e, 0);
124 while (max_flow_test.augmentOnBlockingFlow1<MutableGraph>()) { ++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 blocking flow augmentation ..." << std::endl;
132 FOR_EACH_LOC(Graph::EdgeIt, e, G) flow.set(e, 0);
135 while (max_flow_test.augmentOnBlockingFlow2()) { ++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;
142 std::cout << "on-the-fly shortest path augmentation ..." << std::endl;
143 FOR_EACH_LOC(Graph::EdgeIt, e, G) flow.set(e, 0);
146 while (max_flow_test.augmentOnShortestPath()) { ++i; }
147 std::cout << "elapsed time: " << ts << std::endl;
148 std::cout << "number of augmentation phases: " << i << std::endl;
149 std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;