5 #include <sage_graph.h>
6 #include <hugo/smart_graph.h>
7 #include <hugo/dimacs.h>
8 #include <hugo/time_measure.h>
9 //#include <graph_wrapper.h>
11 //#include <preflow_res.h>
12 #include <hugo/for_each_macros.h>
13 #include <graph_concept.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 SageGraph MutableGraph;
40 //typedef FullFeatureGraphConcept Graph;
41 typedef SmartGraph Graph;
42 // typedef SageGraph Graph;
43 typedef Graph::Node Node;
44 typedef Graph::EdgeIt EdgeIt;
50 // typedef Mize Tize[0];
52 // std::cout << &zize << " " << sizeof(mize) << sizeof(Tize) << std::endl;
53 // std::cout << sizeof(bize) << std::endl;
57 // std::cout << sizeof(k) << std::endl;
65 // std::cout << sizeof(Bumm) << std::endl;
70 Graph::EdgeMap<int> cap(g);
71 //readDimacsMaxFlow(std::cin, g, s, t, cap);
72 readDimacs(std::cin, g, cap, s, t);
74 Graph::EdgeMap<int> flow(g); //0 flow
75 MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> >
76 max_flow_test(g, s, t, cap, flow);
77 Graph::NodeMap<bool> cut(g);
80 std::cout << "preflow ..." << std::endl;
83 std::cout << "elapsed time: " << ts << std::endl;
84 std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
85 max_flow_test.actMinCut(cut);
87 FOR_EACH_LOC(Graph::EdgeIt, e, g) {
88 if (cut[g.tail(e)] && !cut[g.head(e)] && !flow[e]==cap[e])
89 std::cout << "Slackness does not hold!" << std::endl;
90 if (!cut[g.tail(e)] && cut[g.head(e)] && flow[e]>0)
91 std::cout << "Slackness does not hold!" << std::endl;
96 std::cout << "preflow ..." << std::endl;
97 FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0);
99 max_flow_test.preflow(MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> >::GEN_FLOW);
100 std::cout << "elapsed time: " << ts << std::endl;
101 std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
103 FOR_EACH_LOC(Graph::EdgeIt, e, g) {
104 if (cut[g.tail(e)] && !cut[g.head(e)] && !flow[e]==cap[e])
105 std::cout << "Slackness does not hold!" << std::endl;
106 if (!cut[g.tail(e)] && cut[g.head(e)] && flow[e]>0)
107 std::cout << "Slackness does not hold!" << std::endl;
112 // std::cout << "wrapped preflow ..." << std::endl;
113 // FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0);
115 // pre_flow_res.run();
116 // std::cout << "elapsed time: " << ts << std::endl;
117 // std::cout << "flow value: "<< pre_flow_test.flowValue() << std::endl;
121 std::cout << "physical blocking flow augmentation ..." << std::endl;
122 FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0);
125 while (max_flow_test.augmentOnBlockingFlow<MutableGraph>()) { ++i; }
126 std::cout << "elapsed time: " << ts << std::endl;
127 std::cout << "number of augmentation phases: " << i << std::endl;
128 std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
130 FOR_EACH_LOC(Graph::EdgeIt, e, g) {
131 if (cut[g.tail(e)] && !cut[g.head(e)] && !flow[e]==cap[e])
132 std::cout << "Slackness does not hold!" << std::endl;
133 if (!cut[g.tail(e)] && cut[g.head(e)] && flow[e]>0)
134 std::cout << "Slackness does not hold!" << std::endl;
139 // std::cout << "faster physical blocking flow augmentation ..." << std::endl;
140 // FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0);
143 // while (max_flow_test.augmentOnBlockingFlow1<MutableGraph>()) { ++i; }
144 // std::cout << "elapsed time: " << ts << std::endl;
145 // std::cout << "number of augmentation phases: " << i << std::endl;
146 // std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
150 std::cout << "on-the-fly blocking flow augmentation ..." << std::endl;
151 FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0);
154 while (max_flow_test.augmentOnBlockingFlow2()) { ++i; }
155 std::cout << "elapsed time: " << ts << std::endl;
156 std::cout << "number of augmentation phases: " << i << std::endl;
157 std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
159 FOR_EACH_LOC(Graph::EdgeIt, e, g) {
160 if (cut[g.tail(e)] && !cut[g.head(e)] && !flow[e]==cap[e])
161 std::cout << "Slackness does not hold!" << std::endl;
162 if (!cut[g.tail(e)] && cut[g.head(e)] && flow[e]>0)
163 std::cout << "Slackness does not hold!" << std::endl;
168 std::cout << "on-the-fly shortest path augmentation ..." << std::endl;
169 FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0);
172 while (max_flow_test.augmentOnShortestPath()) { ++i; }
173 std::cout << "elapsed time: " << ts << std::endl;
174 std::cout << "number of augmentation phases: " << i << std::endl;
175 std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
177 FOR_EACH_LOC(Graph::EdgeIt, e, g) {
178 if (cut[g.tail(e)] && !cut[g.head(e)] && !flow[e]==cap[e])
179 std::cout << "Slackness does not hold!" << std::endl;
180 if (!cut[g.tail(e)] && cut[g.head(e)] && flow[e]>0)
181 std::cout << "Slackness does not hold!" << std::endl;
186 std::cout << "on-the-fly shortest path augmentation ..." << std::endl;
187 FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0);
190 while (max_flow_test.augmentOnShortestPath2()) { ++i; }
191 std::cout << "elapsed time: " << ts << std::endl;
192 std::cout << "number of augmentation phases: " << i << std::endl;
193 std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
195 FOR_EACH_LOC(Graph::EdgeIt, e, g) {
196 if (cut[g.tail(e)] && !cut[g.head(e)] && !flow[e]==cap[e])
197 std::cout << "Slackness does not hold!" << std::endl;
198 if (!cut[g.tail(e)] && cut[g.head(e)] && flow[e]>0)
199 std::cout << "Slackness does not hold!" << std::endl;