equal
deleted
inserted
replaced
43 Graph::NodeMap<bool> cut(g); |
43 Graph::NodeMap<bool> cut(g); |
44 |
44 |
45 { |
45 { |
46 Graph::EdgeIt e; |
46 Graph::EdgeIt e; |
47 for (g.first(e); g.valid(e); g.next(e)) |
47 for (g.first(e); g.valid(e); g.next(e)) |
48 cout << 1+g.id(g.tail(e)) << "->" << 1+g.id(g.head(e)) << " cap: " << cap[e] << " preflow: " << flow[e] << endl; |
48 cout << 1+g.id(g.source(e)) << "->" << 1+g.id(g.target(e)) << " cap: " << cap[e] << " preflow: " << flow[e] << endl; |
49 } |
49 } |
50 { |
50 { |
51 Graph::NodeIt n; |
51 Graph::NodeIt n; |
52 for (g.first(n); g.valid(n); g.next(n)) { |
52 for (g.first(n); g.valid(n); g.next(n)) { |
53 int a=0; |
53 int a=0; |
73 std::cout << "flow value 2: "<< max_flow_test.flowValue2() << std::endl; |
73 std::cout << "flow value 2: "<< max_flow_test.flowValue2() << std::endl; |
74 max_flow_test.actMinCut(cut); |
74 max_flow_test.actMinCut(cut); |
75 |
75 |
76 Graph::EdgeIt e; |
76 Graph::EdgeIt e; |
77 for (g.first(e); g.valid(e); g.next(e)) { |
77 for (g.first(e); g.valid(e); g.next(e)) { |
78 if (cut[g.tail(e)] && !cut[g.head(e)]) { |
78 if (cut[g.source(e)] && !cut[g.target(e)]) { |
79 cout << 1+g.id(g.tail(e)) << "->" << 1+g.id(g.head(e)) |
79 cout << 1+g.id(g.source(e)) << "->" << 1+g.id(g.target(e)) |
80 << "(forward edge) flow: " << flow[e] |
80 << "(forward edge) flow: " << flow[e] |
81 << " cap: " << cap[e]<< endl; |
81 << " cap: " << cap[e]<< endl; |
82 if (flow[e]!=cap[e]) |
82 if (flow[e]!=cap[e]) |
83 std::cout << "Slackness does not hold!" << std::endl; |
83 std::cout << "Slackness does not hold!" << std::endl; |
84 } |
84 } |
85 if (!cut[g.tail(e)] && cut[g.head(e)]) { |
85 if (!cut[g.source(e)] && cut[g.target(e)]) { |
86 cout << 1+g.id(g.tail(e)) << "->" << 1+g.id(g.head(e)) |
86 cout << 1+g.id(g.source(e)) << "->" << 1+g.id(g.target(e)) |
87 << "(backward edge) flow: " << flow[e] << endl; |
87 << "(backward edge) flow: " << flow[e] << endl; |
88 if (flow[e]!=0) |
88 if (flow[e]!=0) |
89 std::cout << "Slackness does not hold!" << std::endl; |
89 std::cout << "Slackness does not hold!" << std::endl; |
90 } |
90 } |
91 } |
91 } |
103 // std::cout << "elapsed time: " << ts << std::endl; |
103 // std::cout << "elapsed time: " << ts << std::endl; |
104 // std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl; |
104 // std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl; |
105 // max_flow_test.actMinCut(cut); |
105 // max_flow_test.actMinCut(cut); |
106 |
106 |
107 // FOR_EACH_LOC(Graph::EdgeIt, e, g) { |
107 // FOR_EACH_LOC(Graph::EdgeIt, e, g) { |
108 // if (cut[g.tail(e)] && !cut[g.head(e)] && !flow[e]==cap[e]) |
108 // if (cut[g.source(e)] && !cut[g.target(e)] && !flow[e]==cap[e]) |
109 // std::cout << "Slackness does not hold!" << std::endl; |
109 // std::cout << "Slackness does not hold!" << std::endl; |
110 // if (!cut[g.tail(e)] && cut[g.head(e)] && flow[e]>0) |
110 // if (!cut[g.source(e)] && cut[g.target(e)] && flow[e]>0) |
111 // std::cout << "Slackness does not hold!" << std::endl; |
111 // std::cout << "Slackness does not hold!" << std::endl; |
112 // } |
112 // } |
113 // } |
113 // } |
114 |
114 |
115 // { |
115 // { |
119 // max_flow_test.preflow(MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> >::GEN_FLOW); |
119 // max_flow_test.preflow(MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> >::GEN_FLOW); |
120 // std::cout << "elapsed time: " << ts << std::endl; |
120 // std::cout << "elapsed time: " << ts << std::endl; |
121 // std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl; |
121 // std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl; |
122 |
122 |
123 // FOR_EACH_LOC(Graph::EdgeIt, e, g) { |
123 // FOR_EACH_LOC(Graph::EdgeIt, e, g) { |
124 // if (cut[g.tail(e)] && !cut[g.head(e)] && !flow[e]==cap[e]) |
124 // if (cut[g.source(e)] && !cut[g.target(e)] && !flow[e]==cap[e]) |
125 // std::cout << "Slackness does not hold!" << std::endl; |
125 // std::cout << "Slackness does not hold!" << std::endl; |
126 // if (!cut[g.tail(e)] && cut[g.head(e)] && flow[e]>0) |
126 // if (!cut[g.source(e)] && cut[g.target(e)] && flow[e]>0) |
127 // std::cout << "Slackness does not hold!" << std::endl; |
127 // std::cout << "Slackness does not hold!" << std::endl; |
128 // } |
128 // } |
129 // } |
129 // } |
130 |
130 |
131 // // { |
131 // // { |
146 // std::cout << "elapsed time: " << ts << std::endl; |
146 // std::cout << "elapsed time: " << ts << std::endl; |
147 // std::cout << "number of augmentation phases: " << i << std::endl; |
147 // std::cout << "number of augmentation phases: " << i << std::endl; |
148 // std::cout << "flow value: "<< augmenting_flow_test.flowValue() << std::endl; |
148 // std::cout << "flow value: "<< augmenting_flow_test.flowValue() << std::endl; |
149 |
149 |
150 // FOR_EACH_LOC(Graph::EdgeIt, e, g) { |
150 // FOR_EACH_LOC(Graph::EdgeIt, e, g) { |
151 // if (cut[g.tail(e)] && !cut[g.head(e)] && !flow[e]==cap[e]) |
151 // if (cut[g.source(e)] && !cut[g.target(e)] && !flow[e]==cap[e]) |
152 // std::cout << "Slackness does not hold!" << std::endl; |
152 // std::cout << "Slackness does not hold!" << std::endl; |
153 // if (!cut[g.tail(e)] && cut[g.head(e)] && flow[e]>0) |
153 // if (!cut[g.source(e)] && cut[g.target(e)] && flow[e]>0) |
154 // std::cout << "Slackness does not hold!" << std::endl; |
154 // std::cout << "Slackness does not hold!" << std::endl; |
155 // } |
155 // } |
156 // } |
156 // } |
157 |
157 |
158 // // { |
158 // // { |
175 // std::cout << "elapsed time: " << ts << std::endl; |
175 // std::cout << "elapsed time: " << ts << std::endl; |
176 // std::cout << "number of augmentation phases: " << i << std::endl; |
176 // std::cout << "number of augmentation phases: " << i << std::endl; |
177 // std::cout << "flow value: "<< augmenting_flow_test.flowValue() << std::endl; |
177 // std::cout << "flow value: "<< augmenting_flow_test.flowValue() << std::endl; |
178 |
178 |
179 // FOR_EACH_LOC(Graph::EdgeIt, e, g) { |
179 // FOR_EACH_LOC(Graph::EdgeIt, e, g) { |
180 // if (cut[g.tail(e)] && !cut[g.head(e)] && !flow[e]==cap[e]) |
180 // if (cut[g.source(e)] && !cut[g.target(e)] && !flow[e]==cap[e]) |
181 // std::cout << "Slackness does not hold!" << std::endl; |
181 // std::cout << "Slackness does not hold!" << std::endl; |
182 // if (!cut[g.tail(e)] && cut[g.head(e)] && flow[e]>0) |
182 // if (!cut[g.source(e)] && cut[g.target(e)] && flow[e]>0) |
183 // std::cout << "Slackness does not hold!" << std::endl; |
183 // std::cout << "Slackness does not hold!" << std::endl; |
184 // } |
184 // } |
185 // } |
185 // } |
186 |
186 |
187 // { |
187 // { |
193 // std::cout << "elapsed time: " << ts << std::endl; |
193 // std::cout << "elapsed time: " << ts << std::endl; |
194 // std::cout << "number of augmentation phases: " << i << std::endl; |
194 // std::cout << "number of augmentation phases: " << i << std::endl; |
195 // std::cout << "flow value: "<< augmenting_flow_test.flowValue() << std::endl; |
195 // std::cout << "flow value: "<< augmenting_flow_test.flowValue() << std::endl; |
196 |
196 |
197 // FOR_EACH_LOC(Graph::EdgeIt, e, g) { |
197 // FOR_EACH_LOC(Graph::EdgeIt, e, g) { |
198 // if (cut[g.tail(e)] && !cut[g.head(e)] && !flow[e]==cap[e]) |
198 // if (cut[g.source(e)] && !cut[g.target(e)] && !flow[e]==cap[e]) |
199 // std::cout << "Slackness does not hold!" << std::endl; |
199 // std::cout << "Slackness does not hold!" << std::endl; |
200 // if (!cut[g.tail(e)] && cut[g.head(e)] && flow[e]>0) |
200 // if (!cut[g.source(e)] && cut[g.target(e)] && flow[e]>0) |
201 // std::cout << "Slackness does not hold!" << std::endl; |
201 // std::cout << "Slackness does not hold!" << std::endl; |
202 // } |
202 // } |
203 // } |
203 // } |
204 |
204 |
205 // { |
205 // { |
211 // std::cout << "elapsed time: " << ts << std::endl; |
211 // std::cout << "elapsed time: " << ts << std::endl; |
212 // std::cout << "number of augmentation phases: " << i << std::endl; |
212 // std::cout << "number of augmentation phases: " << i << std::endl; |
213 // std::cout << "flow value: "<< augmenting_flow_test.flowValue() << std::endl; |
213 // std::cout << "flow value: "<< augmenting_flow_test.flowValue() << std::endl; |
214 |
214 |
215 // FOR_EACH_LOC(Graph::EdgeIt, e, g) { |
215 // FOR_EACH_LOC(Graph::EdgeIt, e, g) { |
216 // if (cut[g.tail(e)] && !cut[g.head(e)] && !flow[e]==cap[e]) |
216 // if (cut[g.source(e)] && !cut[g.target(e)] && !flow[e]==cap[e]) |
217 // std::cout << "Slackness does not hold!" << std::endl; |
217 // std::cout << "Slackness does not hold!" << std::endl; |
218 // if (!cut[g.tail(e)] && cut[g.head(e)] && flow[e]>0) |
218 // if (!cut[g.source(e)] && cut[g.target(e)] && flow[e]>0) |
219 // std::cout << "Slackness does not hold!" << std::endl; |
219 // std::cout << "Slackness does not hold!" << std::endl; |
220 // } |
220 // } |
221 // } |
221 // } |
222 |
222 |
223 return 0; |
223 return 0; |