ResGraphWrapper<Graph> is done, so does dimacs.h.
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>
10 #include <hugo/max_flow.h>
11 //#include <preflow_res.h>
12 #include <for_each_macros.h>
13 #include <graph_concept.h>
20 // Use a DIMACS min cost flow file as stdin.
21 // read_dimacs_demo < dimacs_max_flow_file
23 int main(int, char **) {
25 //typedef SageGraph MutableGraph;
26 //typedef FullFeatureGraphConcept Graph;
27 //typedef SmartGraph Graph;
28 typedef SageGraph Graph;
29 typedef Graph::Node Node;
30 typedef Graph::EdgeIt EdgeIt;
35 Graph::EdgeMap<int> cap(g);
36 Graph::EdgeMap<int> flow(g); //0 flow
37 //readDimacs(std::cin, g, cap, s, t);
38 readDimacs(std::cin, g, cap, s, t, flow);
40 MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> >
41 max_flow_test(g, s, t, cap, flow);
43 Graph::NodeMap<bool> cut(g);
47 for (g.first(e); g.valid(e); g.next(e))
48 cout << 1+g.id(g.tail(e)) << "->" << 1+g.id(g.head(e)) << " cap: " << cap[e] << " preflow: " << flow[e] << endl;
52 for (g.first(n); g.valid(n); g.next(n)) {
56 for (g.first(e, n); g.valid(e); g.next(e)) a+=flow[e];
60 for (g.first(e, n); g.valid(e); g.next(e)) a-=flow[e];
62 cout << 1+g.id(n) << " excess: " << a << endl;
68 // std::cout << "preflow ..." << std::endl;
70 max_flow_test.preflowPhase1(MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> >::PRE_FLOW);
71 // std::cout << "elapsed time: " << ts << std::endl;
72 std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
73 std::cout << "flow value 2: "<< max_flow_test.flowValue2() << std::endl;
74 max_flow_test.actMinCut(cut);
77 for (g.first(e); g.valid(e); g.next(e)) {
78 if (cut[g.tail(e)] && !cut[g.head(e)]) {
79 cout << 1+g.id(g.tail(e)) << "->" << 1+g.id(g.head(e))
80 << "(forward edge) flow: " << flow[e]
81 << " cap: " << cap[e]<< endl;
83 std::cout << "Slackness does not hold!" << std::endl;
85 if (!cut[g.tail(e)] && cut[g.head(e)]) {
86 cout << 1+g.id(g.tail(e)) << "->" << 1+g.id(g.head(e))
87 << "(backward edge) flow: " << flow[e] << endl;
89 std::cout << "Slackness does not hold!" << std::endl;
93 for (g.first(n); g.valid(n); g.next(n)) {
95 cout << "in cut: " << 1+g.id(n) << endl;
100 // std::cout << "preflow ..." << std::endl;
102 // max_flow_test.run();
103 // std::cout << "elapsed time: " << ts << std::endl;
104 // std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
105 // max_flow_test.actMinCut(cut);
107 // FOR_EACH_LOC(Graph::EdgeIt, e, g) {
108 // if (cut[g.tail(e)] && !cut[g.head(e)] && !flow[e]==cap[e])
109 // std::cout << "Slackness does not hold!" << std::endl;
110 // if (!cut[g.tail(e)] && cut[g.head(e)] && flow[e]>0)
111 // std::cout << "Slackness does not hold!" << std::endl;
116 // std::cout << "preflow ..." << std::endl;
117 // FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0);
119 // max_flow_test.preflow(MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> >::GEN_FLOW);
120 // std::cout << "elapsed time: " << ts << std::endl;
121 // std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
123 // FOR_EACH_LOC(Graph::EdgeIt, e, g) {
124 // if (cut[g.tail(e)] && !cut[g.head(e)] && !flow[e]==cap[e])
125 // std::cout << "Slackness does not hold!" << std::endl;
126 // if (!cut[g.tail(e)] && cut[g.head(e)] && flow[e]>0)
127 // std::cout << "Slackness does not hold!" << std::endl;
132 // // std::cout << "wrapped preflow ..." << std::endl;
133 // // FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0);
135 // // pre_flow_res.run();
136 // // std::cout << "elapsed time: " << ts << std::endl;
137 // // std::cout << "flow value: "<< pre_flow_test.flowValue() << std::endl;
141 // std::cout << "physical blocking flow augmentation ..." << std::endl;
142 // FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0);
145 // while (augmenting_flow_test.augmentOnBlockingFlow<MutableGraph>()) { ++i; }
146 // std::cout << "elapsed time: " << ts << std::endl;
147 // std::cout << "number of augmentation phases: " << i << std::endl;
148 // std::cout << "flow value: "<< augmenting_flow_test.flowValue() << std::endl;
150 // FOR_EACH_LOC(Graph::EdgeIt, e, g) {
151 // if (cut[g.tail(e)] && !cut[g.head(e)] && !flow[e]==cap[e])
152 // std::cout << "Slackness does not hold!" << std::endl;
153 // if (!cut[g.tail(e)] && cut[g.head(e)] && flow[e]>0)
154 // std::cout << "Slackness does not hold!" << std::endl;
159 // // std::cout << "faster physical blocking flow augmentation ..." << std::endl;
160 // // FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0);
163 // // while (max_flow_test.augmentOnBlockingFlow1<MutableGraph>()) { ++i; }
164 // // std::cout << "elapsed time: " << ts << std::endl;
165 // // std::cout << "number of augmentation phases: " << i << std::endl;
166 // // std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
170 // std::cout << "on-the-fly blocking flow augmentation ..." << std::endl;
171 // FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0);
174 // while (augmenting_flow_test.augmentOnBlockingFlow2()) { ++i; }
175 // std::cout << "elapsed time: " << ts << std::endl;
176 // std::cout << "number of augmentation phases: " << i << std::endl;
177 // std::cout << "flow value: "<< augmenting_flow_test.flowValue() << std::endl;
179 // FOR_EACH_LOC(Graph::EdgeIt, e, g) {
180 // if (cut[g.tail(e)] && !cut[g.head(e)] && !flow[e]==cap[e])
181 // std::cout << "Slackness does not hold!" << std::endl;
182 // if (!cut[g.tail(e)] && cut[g.head(e)] && flow[e]>0)
183 // std::cout << "Slackness does not hold!" << std::endl;
188 // std::cout << "on-the-fly shortest path augmentation ..." << std::endl;
189 // FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0);
192 // while (augmenting_flow_test.augmentOnShortestPath()) { ++i; }
193 // std::cout << "elapsed time: " << ts << std::endl;
194 // std::cout << "number of augmentation phases: " << i << std::endl;
195 // std::cout << "flow value: "<< augmenting_flow_test.flowValue() << std::endl;
197 // FOR_EACH_LOC(Graph::EdgeIt, e, g) {
198 // if (cut[g.tail(e)] && !cut[g.head(e)] && !flow[e]==cap[e])
199 // std::cout << "Slackness does not hold!" << std::endl;
200 // if (!cut[g.tail(e)] && cut[g.head(e)] && flow[e]>0)
201 // std::cout << "Slackness does not hold!" << std::endl;
206 // std::cout << "on-the-fly shortest path augmentation ..." << std::endl;
207 // FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0);
210 // while (augmenting_flow_test.augmentOnShortestPath2()) { ++i; }
211 // std::cout << "elapsed time: " << ts << std::endl;
212 // std::cout << "number of augmentation phases: " << i << std::endl;
213 // std::cout << "flow value: "<< augmenting_flow_test.flowValue() << std::endl;
215 // FOR_EACH_LOC(Graph::EdgeIt, e, g) {
216 // if (cut[g.tail(e)] && !cut[g.head(e)] && !flow[e]==cap[e])
217 // std::cout << "Slackness does not hold!" << std::endl;
218 // if (!cut[g.tail(e)] && cut[g.head(e)] && flow[e]>0)
219 // std::cout << "Slackness does not hold!" << std::endl;