Completions.
3 // Use a DIMACS max flow file as stdin.
4 // max_flow_demo < dimacs_max_flow_file
9 #include <lemon/smart_graph.h>
10 #include <lemon/list_graph.h>
11 #include <lemon/dimacs.h>
12 #include <lemon/time_measure.h>
13 #include <lemon/preflow.h>
14 #include <augmenting_flow.h>
15 #include <graph_concept.h>
17 using namespace lemon;
19 int main(int, char **) {
21 typedef ListGraph MutableGraph;
22 typedef SmartGraph Graph;
23 typedef Graph::Node Node;
24 typedef Graph::EdgeIt EdgeIt;
29 Graph::EdgeMap<int> cap(g);
30 //readDimacsMaxFlow(std::cin, g, s, t, cap);
31 readDimacs(std::cin, g, cap, s, t);
33 Graph::EdgeMap<int> flow(g); //0 flow
34 Preflow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> >
35 max_flow_test(g, s, t, cap, flow);
36 AugmentingFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> >
37 augmenting_flow_test(g, s, t, cap, flow);
39 Graph::NodeMap<bool> cut(g);
42 std::cout << "preflow ..." << std::endl;
45 std::cout << "elapsed time: " << ts << std::endl;
46 std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
47 max_flow_test.minCut(cut);
49 for(Graph::EdgeIt e(g); e!=INVALID; ++e) {
50 if (cut[g.source(e)] && !cut[g.target(e)] && !flow[e]==cap[e])
51 std::cout << "Slackness does not hold!" << std::endl;
52 if (!cut[g.source(e)] && cut[g.target(e)] && flow[e]>0)
53 std::cout << "Slackness does not hold!" << std::endl;
58 std::cout << "preflow ..." << std::endl;
59 for(Graph::EdgeIt e(g); e!=INVALID; ++e) flow.set(e, 0);
61 max_flow_test.run(Preflow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> >::GEN_FLOW);
62 std::cout << "elapsed time: " << ts << std::endl;
63 std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
65 for(Graph::EdgeIt e(g); e!=INVALID; ++e) {
66 if (cut[g.source(e)] && !cut[g.target(e)] && !flow[e]==cap[e])
67 std::cout << "Slackness does not hold!" << std::endl;
68 if (!cut[g.source(e)] && cut[g.target(e)] && flow[e]>0)
69 std::cout << "Slackness does not hold!" << std::endl;
74 // std::cout << "wrapped preflow ..." << std::endl;
75 // FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0);
77 // pre_flow_res.run();
78 // std::cout << "elapsed time: " << ts << std::endl;
79 // std::cout << "flow value: "<< pre_flow_test.flowValue() << std::endl;
83 std::cout << "physical blocking flow augmentation ..." << std::endl;
84 for(Graph::EdgeIt e(g); e!=INVALID; ++e) flow.set(e, 0);
87 while (augmenting_flow_test.augmentOnBlockingFlow<MutableGraph>()) { ++i; }
88 std::cout << "elapsed time: " << ts << std::endl;
89 std::cout << "number of augmentation phases: " << i << std::endl;
90 std::cout << "flow value: "<< augmenting_flow_test.flowValue() << std::endl;
92 for(Graph::EdgeIt e(g); e!=INVALID; ++e) {
93 if (cut[g.source(e)] && !cut[g.target(e)] && !flow[e]==cap[e])
94 std::cout << "Slackness does not hold!" << std::endl;
95 if (!cut[g.source(e)] && cut[g.target(e)] && flow[e]>0)
96 std::cout << "Slackness does not hold!" << std::endl;
101 std::cout << "on-the-fly blocking flow augmentation ..." << std::endl;
102 for(Graph::EdgeIt e(g); e!=INVALID; ++e) flow.set(e, 0);
105 while (augmenting_flow_test.augmentOnBlockingFlow2()) { ++i; }
106 std::cout << "elapsed time: " << ts << std::endl;
107 std::cout << "number of augmentation phases: " << i << std::endl;
108 std::cout << "flow value: "<< augmenting_flow_test.flowValue() << std::endl;
110 for(Graph::EdgeIt e(g); e!=INVALID; ++e) {
111 if (cut[g.source(e)] && !cut[g.target(e)] && !flow[e]==cap[e])
112 std::cout << "Slackness does not hold!" << std::endl;
113 if (!cut[g.source(e)] && cut[g.target(e)] && flow[e]>0)
114 std::cout << "Slackness does not hold!" << std::endl;
119 std::cout << "on-the-fly shortest path augmentation ..." << std::endl;
120 for(Graph::EdgeIt e(g); e!=INVALID; ++e) flow.set(e, 0);
123 while (augmenting_flow_test.augmentOnShortestPath()) { ++i; }
124 std::cout << "elapsed time: " << ts << std::endl;
125 std::cout << "number of augmentation phases: " << i << std::endl;
126 std::cout << "flow value: "<< augmenting_flow_test.flowValue() << std::endl;
128 for(Graph::EdgeIt e(g); e!=INVALID; ++e) {
129 if (cut[g.source(e)] && !cut[g.target(e)] && !flow[e]==cap[e])
130 std::cout << "Slackness does not hold!" << std::endl;
131 if (!cut[g.source(e)] && cut[g.target(e)] && flow[e]>0)
132 std::cout << "Slackness does not hold!" << std::endl;
137 std::cout << "on-the-fly shortest path augmentation ..." << std::endl;
138 for(Graph::EdgeIt e(g); e!=INVALID; ++e) flow.set(e, 0);
141 while (augmenting_flow_test.augmentOnShortestPath2()) { ++i; }
142 std::cout << "elapsed time: " << ts << std::endl;
143 std::cout << "number of augmentation phases: " << i << std::endl;
144 std::cout << "flow value: "<< augmenting_flow_test.flowValue() << std::endl;
146 for(Graph::EdgeIt e(g); e!=INVALID; ++e) {
147 if (cut[g.source(e)] && !cut[g.target(e)] && !flow[e]==cap[e])
148 std::cout << "Slackness does not hold!" << std::endl;
149 if (!cut[g.source(e)] && cut[g.target(e)] && flow[e]>0)
150 std::cout << "Slackness does not hold!" << std::endl;