1 // -*- c++ -*- |
|
2 #include <iostream> |
|
3 #include <fstream> |
|
4 |
|
5 #include <lemon/smart_graph.h> |
|
6 #include <lemon/list_graph.h> |
|
7 #include <lemon/dimacs.h> |
|
8 #include <lemon/time_measure.h> |
|
9 //#include <graph_wrapper.h> |
|
10 #include <lemon/preflow.h> |
|
11 #include <augmenting_flow.h> |
|
12 //#include <preflow_res.h> |
|
13 //#include <lp_solver_wrapper_2.h> |
|
14 #include <min_cost_gen_flow.h> |
|
15 |
|
16 // Use a DIMACS max flow file as stdin. |
|
17 // max_flow_demo < dimacs_max_flow_file |
|
18 |
|
19 using namespace lemon; |
|
20 |
|
21 int main(int, char **) { |
|
22 |
|
23 typedef ListGraph MutableGraph; |
|
24 typedef ListGraph Graph; |
|
25 typedef Graph::Node Node; |
|
26 typedef Graph::Edge Edge; |
|
27 typedef Graph::EdgeIt EdgeIt; |
|
28 |
|
29 Graph g; |
|
30 |
|
31 Node s, t; |
|
32 Graph::EdgeMap<int> cap(g); |
|
33 //readDimacsMaxFlow(std::cin, g, s, t, cap); |
|
34 readDimacs(std::cin, g, cap, s, t); |
|
35 Timer ts; |
|
36 Graph::EdgeMap<int> flow(g); //0 flow |
|
37 Preflow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> > |
|
38 max_flow_test(g, s, t, cap, flow); |
|
39 AugmentingFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> > |
|
40 augmenting_flow_test(g, s, t, cap, flow); |
|
41 |
|
42 Graph::NodeMap<bool> cut(g); |
|
43 |
|
44 { |
|
45 std::cout << "preflow ..." << std::endl; |
|
46 ts.reset(); |
|
47 max_flow_test.run(); |
|
48 std::cout << "elapsed time: " << ts << std::endl; |
|
49 std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl; |
|
50 max_flow_test.minCut(cut); |
|
51 |
|
52 for (EdgeIt e(g); e!=INVALID; ++e) { |
|
53 if (cut[g.source(e)] && !cut[g.target(e)] && !flow[e]==cap[e]) |
|
54 std::cout << "Slackness does not hold!" << std::endl; |
|
55 if (!cut[g.source(e)] && cut[g.target(e)] && flow[e]>0) |
|
56 std::cout << "Slackness does not hold!" << std::endl; |
|
57 } |
|
58 } |
|
59 |
|
60 // { |
|
61 // std::cout << "preflow ..." << std::endl; |
|
62 // FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0); |
|
63 // ts.reset(); |
|
64 // max_flow_test.preflow(Preflow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> >::GEN_FLOW); |
|
65 // std::cout << "elapsed time: " << ts << std::endl; |
|
66 // std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl; |
|
67 |
|
68 // FOR_EACH_LOC(Graph::EdgeIt, e, g) { |
|
69 // if (cut[g.source(e)] && !cut[g.target(e)] && !flow[e]==cap[e]) |
|
70 // std::cout << "Slackness does not hold!" << std::endl; |
|
71 // if (!cut[g.source(e)] && cut[g.target(e)] && flow[e]>0) |
|
72 // std::cout << "Slackness does not hold!" << std::endl; |
|
73 // } |
|
74 // } |
|
75 |
|
76 // { |
|
77 // std::cout << "wrapped preflow ..." << std::endl; |
|
78 // FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0); |
|
79 // ts.reset(); |
|
80 // pre_flow_res.run(); |
|
81 // std::cout << "elapsed time: " << ts << std::endl; |
|
82 // std::cout << "flow value: "<< pre_flow_test.flowValue() << std::endl; |
|
83 // } |
|
84 |
|
85 { |
|
86 std::cout << "physical blocking flow augmentation ..." << std::endl; |
|
87 for (EdgeIt e(g); e!=INVALID; ++e) flow.set(e, 0); |
|
88 ts.reset(); |
|
89 int i=0; |
|
90 while (augmenting_flow_test.augmentOnBlockingFlow<MutableGraph>()) { ++i; } |
|
91 std::cout << "elapsed time: " << ts << std::endl; |
|
92 std::cout << "number of augmentation phases: " << i << std::endl; |
|
93 std::cout << "flow value: "<< augmenting_flow_test.flowValue() << std::endl; |
|
94 |
|
95 for (EdgeIt e(g); e!=INVALID; ++e) { |
|
96 if (cut[g.source(e)] && !cut[g.target(e)] && !flow[e]==cap[e]) |
|
97 std::cout << "Slackness does not hold!" << std::endl; |
|
98 if (!cut[g.source(e)] && cut[g.target(e)] && flow[e]>0) |
|
99 std::cout << "Slackness does not hold!" << std::endl; |
|
100 } |
|
101 } |
|
102 |
|
103 // { |
|
104 // std::cout << "faster physical blocking flow augmentation ..." << std::endl; |
|
105 // FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0); |
|
106 // ts.reset(); |
|
107 // int i=0; |
|
108 // while (max_flow_test.augmentOnBlockingFlow1<MutableGraph>()) { ++i; } |
|
109 // std::cout << "elapsed time: " << ts << std::endl; |
|
110 // std::cout << "number of augmentation phases: " << i << std::endl; |
|
111 // std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl; |
|
112 // } |
|
113 |
|
114 { |
|
115 std::cout << "on-the-fly blocking flow augmentation ..." << std::endl; |
|
116 for (EdgeIt e(g); e!=INVALID; ++e) flow.set(e, 0); |
|
117 ts.reset(); |
|
118 int i=0; |
|
119 while (augmenting_flow_test.augmentOnBlockingFlow2()) { ++i; } |
|
120 std::cout << "elapsed time: " << ts << std::endl; |
|
121 std::cout << "number of augmentation phases: " << i << std::endl; |
|
122 std::cout << "flow value: "<< augmenting_flow_test.flowValue() << std::endl; |
|
123 |
|
124 for (EdgeIt e(g); e!=INVALID; ++e) { |
|
125 if (cut[g.source(e)] && !cut[g.target(e)] && !flow[e]==cap[e]) |
|
126 std::cout << "Slackness does not hold!" << std::endl; |
|
127 if (!cut[g.source(e)] && cut[g.target(e)] && flow[e]>0) |
|
128 std::cout << "Slackness does not hold!" << std::endl; |
|
129 } |
|
130 } |
|
131 |
|
132 // { |
|
133 // std::cout << "on-the-fly shortest path augmentation ..." << std::endl; |
|
134 // FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0); |
|
135 // ts.reset(); |
|
136 // int i=0; |
|
137 // while (augmenting_flow_test.augmentOnShortestPath()) { ++i; } |
|
138 // std::cout << "elapsed time: " << ts << std::endl; |
|
139 // std::cout << "number of augmentation phases: " << i << std::endl; |
|
140 // std::cout << "flow value: "<< augmenting_flow_test.flowValue() << std::endl; |
|
141 |
|
142 // FOR_EACH_LOC(Graph::EdgeIt, e, g) { |
|
143 // if (cut[g.source(e)] && !cut[g.target(e)] && !flow[e]==cap[e]) |
|
144 // std::cout << "Slackness does not hold!" << std::endl; |
|
145 // if (!cut[g.source(e)] && cut[g.target(e)] && flow[e]>0) |
|
146 // std::cout << "Slackness does not hold!" << std::endl; |
|
147 // } |
|
148 // } |
|
149 |
|
150 // { |
|
151 // std::cout << "on-the-fly shortest path augmentation ..." << std::endl; |
|
152 // FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0); |
|
153 // ts.reset(); |
|
154 // int i=0; |
|
155 // while (augmenting_flow_test.augmentOnShortestPath2()) { ++i; } |
|
156 // std::cout << "elapsed time: " << ts << std::endl; |
|
157 // std::cout << "number of augmentation phases: " << i << std::endl; |
|
158 // std::cout << "flow value: "<< augmenting_flow_test.flowValue() << std::endl; |
|
159 |
|
160 // FOR_EACH_LOC(Graph::EdgeIt, e, g) { |
|
161 // if (cut[g.source(e)] && !cut[g.target(e)] && !flow[e]==cap[e]) |
|
162 // std::cout << "Slackness does not hold!" << std::endl; |
|
163 // if (!cut[g.source(e)] && cut[g.target(e)] && flow[e]>0) |
|
164 // std::cout << "Slackness does not hold!" << std::endl; |
|
165 // } |
|
166 // } |
|
167 |
|
168 ts.reset(); |
|
169 |
|
170 Edge e=g.addEdge(t, s); |
|
171 Graph::EdgeMap<int> cost(g, 0); |
|
172 cost.set(e, -1); |
|
173 cap.set(e, 10000); |
|
174 typedef ConstMap<Node, int> Excess; |
|
175 Excess excess(0); |
|
176 typedef ConstMap<Edge, int> LCap; |
|
177 LCap lcap(0); |
|
178 |
|
179 MinCostGenFlow<Graph, int, Excess, LCap> |
|
180 min_cost(g, excess, lcap, cap, flow, cost); |
|
181 min_cost.feasible(); |
|
182 min_cost.runByLP(); |
|
183 |
|
184 std::cout << "elapsed time: " << ts << std::endl; |
|
185 std::cout << "flow value: "<< flow[e] << std::endl; |
|
186 } |
|