12 //#include <preflow_res.h> |
17 //#include <preflow_res.h> |
13 #include <for_each_macros.h> |
18 #include <for_each_macros.h> |
14 #include <graph_concept.h> |
19 #include <graph_concept.h> |
15 |
20 |
16 using namespace hugo; |
21 using namespace hugo; |
17 |
|
18 // Use a DIMACS max flow file as stdin. |
|
19 // max_flow_demo < dimacs_max_flow_file |
|
20 |
22 |
21 int main(int, char **) { |
23 int main(int, char **) { |
22 |
24 |
23 typedef SageGraph MutableGraph; |
25 typedef SageGraph MutableGraph; |
24 |
26 |
100 if (!cut[g.tail(e)] && cut[g.head(e)] && flow[e]>0) |
102 if (!cut[g.tail(e)] && cut[g.head(e)] && flow[e]>0) |
101 std::cout << "Slackness does not hold!" << std::endl; |
103 std::cout << "Slackness does not hold!" << std::endl; |
102 } |
104 } |
103 } |
105 } |
104 |
106 |
105 // { |
107 { |
106 // std::cout << "on-the-fly blocking flow augmentation ..." << std::endl; |
108 std::cout << "on-the-fly blocking flow augmentation ..." << std::endl; |
107 // FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0); |
109 FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0); |
108 // ts.reset(); |
110 ts.reset(); |
109 // int i=0; |
111 int i=0; |
110 // while (augmenting_flow_test.augmentOnBlockingFlow2()) { ++i; } |
112 while (augmenting_flow_test.augmentOnBlockingFlow2()) { ++i; } |
111 // std::cout << "elapsed time: " << ts << std::endl; |
113 std::cout << "elapsed time: " << ts << std::endl; |
112 // std::cout << "number of augmentation phases: " << i << std::endl; |
114 std::cout << "number of augmentation phases: " << i << std::endl; |
113 // std::cout << "flow value: "<< augmenting_flow_test.flowValue() << std::endl; |
115 std::cout << "flow value: "<< augmenting_flow_test.flowValue() << std::endl; |
114 |
116 |
115 // FOR_EACH_LOC(Graph::EdgeIt, e, g) { |
117 FOR_EACH_LOC(Graph::EdgeIt, e, g) { |
116 // if (cut[g.tail(e)] && !cut[g.head(e)] && !flow[e]==cap[e]) |
118 if (cut[g.tail(e)] && !cut[g.head(e)] && !flow[e]==cap[e]) |
117 // std::cout << "Slackness does not hold!" << std::endl; |
119 std::cout << "Slackness does not hold!" << std::endl; |
118 // if (!cut[g.tail(e)] && cut[g.head(e)] && flow[e]>0) |
120 if (!cut[g.tail(e)] && cut[g.head(e)] && flow[e]>0) |
119 // std::cout << "Slackness does not hold!" << std::endl; |
121 std::cout << "Slackness does not hold!" << std::endl; |
120 // } |
122 } |
121 // } |
123 } |
122 |
124 |
123 { |
125 { |
124 std::cout << "on-the-fly shortest path augmentation ..." << std::endl; |
126 std::cout << "on-the-fly shortest path augmentation ..." << std::endl; |
125 FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0); |
127 FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0); |
126 ts.reset(); |
128 ts.reset(); |