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 <augmenting_flow.h>
12 //#include <preflow_res.h>
13 #include <for_each_macros.h>
14 #include <graph_concept.h>
18 // Use a DIMACS max flow file as stdin.
19 // max_flow_demo < dimacs_max_flow_file
21 int main(int, char **) {
23 typedef SageGraph MutableGraph;
25 //typedef FullFeatureGraphConcept Graph;
26 //typedef SmartGraph Graph;
27 typedef SageGraph Graph;
28 typedef Graph::Node Node;
29 typedef Graph::EdgeIt EdgeIt;
34 Graph::EdgeMap<int> cap(g);
35 //readDimacsMaxFlow(std::cin, g, s, t, cap);
36 readDimacs(std::cin, g, cap, s, t);
38 Graph::EdgeMap<int> flow(g); //0 flow
39 MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> >
40 max_flow_test(g, s, t, cap, flow);
41 AugmentingFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> >
42 augmenting_flow_test(g, s, t, cap, flow);
44 Graph::NodeMap<bool> cut(g);
47 std::cout << "preflow ..." << std::endl;
50 std::cout << "elapsed time: " << ts << std::endl;
51 std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
52 max_flow_test.actMinCut(cut);
54 FOR_EACH_LOC(Graph::EdgeIt, e, g) {
55 if (cut[g.tail(e)] && !cut[g.head(e)] && !flow[e]==cap[e])
56 std::cout << "Slackness does not hold!" << std::endl;
57 if (!cut[g.tail(e)] && cut[g.head(e)] && flow[e]>0)
58 std::cout << "Slackness does not hold!" << std::endl;
63 std::cout << "preflow ..." << std::endl;
64 FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0);
66 max_flow_test.preflow(MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> >::GEN_FLOW);
67 std::cout << "elapsed time: " << ts << std::endl;
68 std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
70 FOR_EACH_LOC(Graph::EdgeIt, e, g) {
71 if (cut[g.tail(e)] && !cut[g.head(e)] && !flow[e]==cap[e])
72 std::cout << "Slackness does not hold!" << std::endl;
73 if (!cut[g.tail(e)] && cut[g.head(e)] && flow[e]>0)
74 std::cout << "Slackness does not hold!" << std::endl;
79 // std::cout << "wrapped preflow ..." << std::endl;
80 // FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0);
82 // pre_flow_res.run();
83 // std::cout << "elapsed time: " << ts << std::endl;
84 // std::cout << "flow value: "<< pre_flow_test.flowValue() << std::endl;
88 std::cout << "physical blocking flow augmentation ..." << std::endl;
89 FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0);
92 while (augmenting_flow_test.augmentOnBlockingFlow<MutableGraph>()) { ++i; }
93 std::cout << "elapsed time: " << ts << std::endl;
94 std::cout << "number of augmentation phases: " << i << std::endl;
95 std::cout << "flow value: "<< augmenting_flow_test.flowValue() << std::endl;
97 FOR_EACH_LOC(Graph::EdgeIt, e, g) {
98 if (cut[g.tail(e)] && !cut[g.head(e)] && !flow[e]==cap[e])
99 std::cout << "Slackness does not hold!" << std::endl;
100 if (!cut[g.tail(e)] && cut[g.head(e)] && flow[e]>0)
101 std::cout << "Slackness does not hold!" << std::endl;
106 // std::cout << "on-the-fly blocking flow augmentation ..." << std::endl;
107 // FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0);
110 // while (augmenting_flow_test.augmentOnBlockingFlow2()) { ++i; }
111 // std::cout << "elapsed time: " << ts << std::endl;
112 // std::cout << "number of augmentation phases: " << i << std::endl;
113 // std::cout << "flow value: "<< augmenting_flow_test.flowValue() << std::endl;
115 // FOR_EACH_LOC(Graph::EdgeIt, e, g) {
116 // if (cut[g.tail(e)] && !cut[g.head(e)] && !flow[e]==cap[e])
117 // std::cout << "Slackness does not hold!" << std::endl;
118 // if (!cut[g.tail(e)] && cut[g.head(e)] && flow[e]>0)
119 // std::cout << "Slackness does not hold!" << std::endl;
124 std::cout << "on-the-fly shortest path augmentation ..." << std::endl;
125 FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0);
128 while (augmenting_flow_test.augmentOnShortestPath()) { ++i; }
129 std::cout << "elapsed time: " << ts << std::endl;
130 std::cout << "number of augmentation phases: " << i << std::endl;
131 std::cout << "flow value: "<< augmenting_flow_test.flowValue() << std::endl;
133 FOR_EACH_LOC(Graph::EdgeIt, e, g) {
134 if (cut[g.tail(e)] && !cut[g.head(e)] && !flow[e]==cap[e])
135 std::cout << "Slackness does not hold!" << std::endl;
136 if (!cut[g.tail(e)] && cut[g.head(e)] && flow[e]>0)
137 std::cout << "Slackness does not hold!" << 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 (augmenting_flow_test.augmentOnShortestPath2()) { ++i; }
147 std::cout << "elapsed time: " << ts << std::endl;
148 std::cout << "number of augmentation phases: " << i << std::endl;
149 std::cout << "flow value: "<< augmenting_flow_test.flowValue() << std::endl;
151 FOR_EACH_LOC(Graph::EdgeIt, e, g) {
152 if (cut[g.tail(e)] && !cut[g.head(e)] && !flow[e]==cap[e])
153 std::cout << "Slackness does not hold!" << std::endl;
154 if (!cut[g.tail(e)] && cut[g.head(e)] && flow[e]>0)
155 std::cout << "Slackness does not hold!" << std::endl;