1 // -*- c++ -*- |
|
2 #include <iostream> |
|
3 #include <fstream> |
|
4 |
|
5 #include <sage_graph.h> |
|
6 #include <lemon/smart_graph.h> |
|
7 #include <lemon/dimacs.h> |
|
8 //#include <lemon/time_measure.h> |
|
9 //#include <graph_wrapper.h> |
|
10 #include <lemon/max_flow.h> |
|
11 //#include <preflow_res.h> |
|
12 #include <for_each_macros.h> |
|
13 #include <graph_concept.h> |
|
14 |
|
15 using std::cout; |
|
16 using std::endl; |
|
17 |
|
18 using namespace lemon; |
|
19 |
|
20 // Use a DIMACS min cost flow file as stdin. |
|
21 // read_dimacs_demo < dimacs_max_flow_file |
|
22 |
|
23 int main(int, char **) { |
|
24 |
|
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; |
|
31 |
|
32 Graph g; |
|
33 |
|
34 Node s, t; |
|
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); |
|
39 // Timer ts; |
|
40 MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> > |
|
41 max_flow_test(g, s, t, cap, flow); |
|
42 |
|
43 Graph::NodeMap<bool> cut(g); |
|
44 |
|
45 { |
|
46 Graph::EdgeIt e; |
|
47 for (g.first(e); g.valid(e); g.next(e)) |
|
48 cout << 1+g.id(g.source(e)) << "->" << 1+g.id(g.target(e)) << " cap: " << cap[e] << " preflow: " << flow[e] << endl; |
|
49 } |
|
50 { |
|
51 Graph::NodeIt n; |
|
52 for (g.first(n); g.valid(n); g.next(n)) { |
|
53 int a=0; |
|
54 { |
|
55 Graph::InEdgeIt e; |
|
56 for (g.first(e, n); g.valid(e); g.next(e)) a+=flow[e]; |
|
57 } |
|
58 { |
|
59 Graph::OutEdgeIt e; |
|
60 for (g.first(e, n); g.valid(e); g.next(e)) a-=flow[e]; |
|
61 } |
|
62 cout << 1+g.id(n) << " excess: " << a << endl; |
|
63 } |
|
64 } |
|
65 |
|
66 |
|
67 { |
|
68 // std::cout << "preflow ..." << std::endl; |
|
69 // ts.reset(); |
|
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); |
|
75 |
|
76 Graph::EdgeIt e; |
|
77 for (g.first(e); g.valid(e); g.next(e)) { |
|
78 if (cut[g.source(e)] && !cut[g.target(e)]) { |
|
79 cout << 1+g.id(g.source(e)) << "->" << 1+g.id(g.target(e)) |
|
80 << "(forward edge) flow: " << flow[e] |
|
81 << " cap: " << cap[e]<< endl; |
|
82 if (flow[e]!=cap[e]) |
|
83 std::cout << "Slackness does not hold!" << std::endl; |
|
84 } |
|
85 if (!cut[g.source(e)] && cut[g.target(e)]) { |
|
86 cout << 1+g.id(g.source(e)) << "->" << 1+g.id(g.target(e)) |
|
87 << "(backward edge) flow: " << flow[e] << endl; |
|
88 if (flow[e]!=0) |
|
89 std::cout << "Slackness does not hold!" << std::endl; |
|
90 } |
|
91 } |
|
92 Graph::NodeIt n; |
|
93 for (g.first(n); g.valid(n); g.next(n)) { |
|
94 if (cut[n]) |
|
95 cout << "in cut: " << 1+g.id(n) << endl; |
|
96 } |
|
97 } |
|
98 |
|
99 // { |
|
100 // std::cout << "preflow ..." << std::endl; |
|
101 // ts.reset(); |
|
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); |
|
106 |
|
107 // FOR_EACH_LOC(Graph::EdgeIt, e, g) { |
|
108 // if (cut[g.source(e)] && !cut[g.target(e)] && !flow[e]==cap[e]) |
|
109 // std::cout << "Slackness does not hold!" << std::endl; |
|
110 // if (!cut[g.source(e)] && cut[g.target(e)] && flow[e]>0) |
|
111 // std::cout << "Slackness does not hold!" << std::endl; |
|
112 // } |
|
113 // } |
|
114 |
|
115 // { |
|
116 // std::cout << "preflow ..." << std::endl; |
|
117 // FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0); |
|
118 // ts.reset(); |
|
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; |
|
122 |
|
123 // FOR_EACH_LOC(Graph::EdgeIt, e, g) { |
|
124 // if (cut[g.source(e)] && !cut[g.target(e)] && !flow[e]==cap[e]) |
|
125 // std::cout << "Slackness does not hold!" << std::endl; |
|
126 // if (!cut[g.source(e)] && cut[g.target(e)] && flow[e]>0) |
|
127 // std::cout << "Slackness does not hold!" << std::endl; |
|
128 // } |
|
129 // } |
|
130 |
|
131 // // { |
|
132 // // std::cout << "wrapped preflow ..." << std::endl; |
|
133 // // FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0); |
|
134 // // ts.reset(); |
|
135 // // pre_flow_res.run(); |
|
136 // // std::cout << "elapsed time: " << ts << std::endl; |
|
137 // // std::cout << "flow value: "<< pre_flow_test.flowValue() << std::endl; |
|
138 // // } |
|
139 |
|
140 // { |
|
141 // std::cout << "physical blocking flow augmentation ..." << std::endl; |
|
142 // FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0); |
|
143 // ts.reset(); |
|
144 // int i=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; |
|
149 |
|
150 // FOR_EACH_LOC(Graph::EdgeIt, e, g) { |
|
151 // if (cut[g.source(e)] && !cut[g.target(e)] && !flow[e]==cap[e]) |
|
152 // std::cout << "Slackness does not hold!" << std::endl; |
|
153 // if (!cut[g.source(e)] && cut[g.target(e)] && flow[e]>0) |
|
154 // std::cout << "Slackness does not hold!" << std::endl; |
|
155 // } |
|
156 // } |
|
157 |
|
158 // // { |
|
159 // // std::cout << "faster physical blocking flow augmentation ..." << std::endl; |
|
160 // // FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0); |
|
161 // // ts.reset(); |
|
162 // // int i=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; |
|
167 // // } |
|
168 |
|
169 // { |
|
170 // std::cout << "on-the-fly blocking flow augmentation ..." << std::endl; |
|
171 // FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0); |
|
172 // ts.reset(); |
|
173 // int i=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; |
|
178 |
|
179 // FOR_EACH_LOC(Graph::EdgeIt, e, g) { |
|
180 // if (cut[g.source(e)] && !cut[g.target(e)] && !flow[e]==cap[e]) |
|
181 // std::cout << "Slackness does not hold!" << std::endl; |
|
182 // if (!cut[g.source(e)] && cut[g.target(e)] && flow[e]>0) |
|
183 // std::cout << "Slackness does not hold!" << std::endl; |
|
184 // } |
|
185 // } |
|
186 |
|
187 // { |
|
188 // std::cout << "on-the-fly shortest path augmentation ..." << std::endl; |
|
189 // FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0); |
|
190 // ts.reset(); |
|
191 // int i=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; |
|
196 |
|
197 // FOR_EACH_LOC(Graph::EdgeIt, e, g) { |
|
198 // if (cut[g.source(e)] && !cut[g.target(e)] && !flow[e]==cap[e]) |
|
199 // std::cout << "Slackness does not hold!" << std::endl; |
|
200 // if (!cut[g.source(e)] && cut[g.target(e)] && flow[e]>0) |
|
201 // std::cout << "Slackness does not hold!" << std::endl; |
|
202 // } |
|
203 // } |
|
204 |
|
205 // { |
|
206 // std::cout << "on-the-fly shortest path augmentation ..." << std::endl; |
|
207 // FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0); |
|
208 // ts.reset(); |
|
209 // int i=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; |
|
214 |
|
215 // FOR_EACH_LOC(Graph::EdgeIt, e, g) { |
|
216 // if (cut[g.source(e)] && !cut[g.target(e)] && !flow[e]==cap[e]) |
|
217 // std::cout << "Slackness does not hold!" << std::endl; |
|
218 // if (!cut[g.source(e)] && cut[g.target(e)] && flow[e]>0) |
|
219 // std::cout << "Slackness does not hold!" << std::endl; |
|
220 // } |
|
221 // } |
|
222 |
|
223 return 0; |
|
224 } |
|