70 readDimacs(std::cin, g, cap, s, t); |
70 readDimacs(std::cin, g, cap, s, t); |
71 Timer ts; |
71 Timer ts; |
72 Graph::EdgeMap<int> flow(g); //0 flow |
72 Graph::EdgeMap<int> flow(g); //0 flow |
73 MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> > |
73 MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> > |
74 max_flow_test(g, s, t, cap, flow); |
74 max_flow_test(g, s, t, cap, flow); |
|
75 Graph::NodeMap<bool> cut(g); |
75 |
76 |
76 { |
77 { |
77 std::cout << "preflow ..." << std::endl; |
78 std::cout << "preflow ..." << std::endl; |
78 ts.reset(); |
79 ts.reset(); |
79 max_flow_test.run(); |
80 max_flow_test.run(); |
80 std::cout << "elapsed time: " << ts << std::endl; |
81 std::cout << "elapsed time: " << ts << std::endl; |
81 std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl; |
82 std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl; |
|
83 max_flow_test.actMinCut(cut); |
|
84 |
|
85 FOR_EACH_LOC(Graph::EdgeIt, e, g) { |
|
86 if (cut[g.tail(e)] && !cut[g.head(e)] && !flow[e]==cap[e]) |
|
87 std::cout << "Slackness does not hold!" << std::endl; |
|
88 if (!cut[g.tail(e)] && cut[g.head(e)] && flow[e]>0) |
|
89 std::cout << "Slackness does not hold!" << std::endl; |
|
90 } |
82 } |
91 } |
83 |
92 |
84 { |
93 { |
85 std::cout << "preflow ..." << std::endl; |
94 std::cout << "preflow ..." << std::endl; |
86 FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0); |
95 FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0); |
87 ts.reset(); |
96 ts.reset(); |
88 max_flow_test.preflow(MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> >::GEN_FLOW); |
97 max_flow_test.preflow(MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> >::GEN_FLOW); |
89 std::cout << "elapsed time: " << ts << std::endl; |
98 std::cout << "elapsed time: " << ts << std::endl; |
90 std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl; |
99 std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl; |
|
100 |
|
101 FOR_EACH_LOC(Graph::EdgeIt, e, g) { |
|
102 if (cut[g.tail(e)] && !cut[g.head(e)] && !flow[e]==cap[e]) |
|
103 std::cout << "Slackness does not hold!" << std::endl; |
|
104 if (!cut[g.tail(e)] && cut[g.head(e)] && flow[e]>0) |
|
105 std::cout << "Slackness does not hold!" << std::endl; |
|
106 } |
91 } |
107 } |
92 |
108 |
93 // { |
109 // { |
94 // std::cout << "wrapped preflow ..." << std::endl; |
110 // std::cout << "wrapped preflow ..." << std::endl; |
95 // FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0); |
111 // FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0); |
106 int i=0; |
122 int i=0; |
107 while (max_flow_test.augmentOnBlockingFlow<MutableGraph>()) { ++i; } |
123 while (max_flow_test.augmentOnBlockingFlow<MutableGraph>()) { ++i; } |
108 std::cout << "elapsed time: " << ts << std::endl; |
124 std::cout << "elapsed time: " << ts << std::endl; |
109 std::cout << "number of augmentation phases: " << i << std::endl; |
125 std::cout << "number of augmentation phases: " << i << std::endl; |
110 std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl; |
126 std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl; |
|
127 |
|
128 FOR_EACH_LOC(Graph::EdgeIt, e, g) { |
|
129 if (cut[g.tail(e)] && !cut[g.head(e)] && !flow[e]==cap[e]) |
|
130 std::cout << "Slackness does not hold!" << std::endl; |
|
131 if (!cut[g.tail(e)] && cut[g.head(e)] && flow[e]>0) |
|
132 std::cout << "Slackness does not hold!" << std::endl; |
|
133 } |
111 } |
134 } |
112 |
135 |
113 // { |
136 // { |
114 // std::cout << "faster physical blocking flow augmentation ..." << std::endl; |
137 // std::cout << "faster physical blocking flow augmentation ..." << std::endl; |
115 // FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0); |
138 // FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0); |
128 int i=0; |
151 int i=0; |
129 while (max_flow_test.augmentOnBlockingFlow2()) { ++i; } |
152 while (max_flow_test.augmentOnBlockingFlow2()) { ++i; } |
130 std::cout << "elapsed time: " << ts << std::endl; |
153 std::cout << "elapsed time: " << ts << std::endl; |
131 std::cout << "number of augmentation phases: " << i << std::endl; |
154 std::cout << "number of augmentation phases: " << i << std::endl; |
132 std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl; |
155 std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl; |
|
156 |
|
157 FOR_EACH_LOC(Graph::EdgeIt, e, g) { |
|
158 if (cut[g.tail(e)] && !cut[g.head(e)] && !flow[e]==cap[e]) |
|
159 std::cout << "Slackness does not hold!" << std::endl; |
|
160 if (!cut[g.tail(e)] && cut[g.head(e)] && flow[e]>0) |
|
161 std::cout << "Slackness does not hold!" << std::endl; |
|
162 } |
133 } |
163 } |
134 |
164 |
135 { |
165 { |
136 std::cout << "on-the-fly shortest path augmentation ..." << std::endl; |
166 std::cout << "on-the-fly shortest path augmentation ..." << std::endl; |
137 FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0); |
167 FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0); |
139 int i=0; |
169 int i=0; |
140 while (max_flow_test.augmentOnShortestPath()) { ++i; } |
170 while (max_flow_test.augmentOnShortestPath()) { ++i; } |
141 std::cout << "elapsed time: " << ts << std::endl; |
171 std::cout << "elapsed time: " << ts << std::endl; |
142 std::cout << "number of augmentation phases: " << i << std::endl; |
172 std::cout << "number of augmentation phases: " << i << std::endl; |
143 std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl; |
173 std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl; |
144 } |
174 |
145 |
175 FOR_EACH_LOC(Graph::EdgeIt, e, g) { |
|
176 if (cut[g.tail(e)] && !cut[g.head(e)] && !flow[e]==cap[e]) |
|
177 std::cout << "Slackness does not hold!" << std::endl; |
|
178 if (!cut[g.tail(e)] && cut[g.head(e)] && flow[e]>0) |
|
179 std::cout << "Slackness does not hold!" << std::endl; |
|
180 } |
|
181 } |
|
182 |
|
183 { |
|
184 std::cout << "on-the-fly shortest path augmentation ..." << std::endl; |
|
185 FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0); |
|
186 ts.reset(); |
|
187 int i=0; |
|
188 while (max_flow_test.augmentOnShortestPath2()) { ++i; } |
|
189 std::cout << "elapsed time: " << ts << std::endl; |
|
190 std::cout << "number of augmentation phases: " << i << std::endl; |
|
191 std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl; |
|
192 |
|
193 FOR_EACH_LOC(Graph::EdgeIt, e, g) { |
|
194 if (cut[g.tail(e)] && !cut[g.head(e)] && !flow[e]==cap[e]) |
|
195 std::cout << "Slackness does not hold!" << std::endl; |
|
196 if (!cut[g.tail(e)] && cut[g.head(e)] && flow[e]>0) |
|
197 std::cout << "Slackness does not hold!" << std::endl; |
|
198 } |
|
199 } |
146 |
200 |
147 return 0; |
201 return 0; |
148 } |
202 } |