| 157 | |
| 158 | template <typename captype, typename tcaptype, typename flowtype> |
| 159 | void Graph<captype,tcaptype,flowtype>::maxflow_reuse_trees_init() |
| 160 | { |
| 161 | node* i; |
| 162 | node* j; |
| 163 | node* queue = queue_first[1]; |
| 164 | arc* a; |
| 165 | nodeptr* np; |
| 166 | |
| 167 | queue_first[0] = queue_last[0] = NULL; |
| 168 | queue_first[1] = queue_last[1] = NULL; |
| 169 | orphan_first = orphan_last = NULL; |
| 170 | |
| 171 | TIME ++; |
| 172 | |
| 173 | while ((i=queue)) |
| 174 | { |
| 175 | queue = i->next; |
| 176 | if (queue == i) queue = NULL; |
| 177 | i->next = NULL; |
| 178 | i->is_marked = 0; |
| 179 | set_active(i); |
| 180 | |
| 181 | if (i->tr_cap == 0) |
| 182 | { |
| 183 | if (i->parent) set_orphan_rear(i); |
| 184 | continue; |
| 185 | } |
| 186 | |
| 187 | if (i->tr_cap > 0) |
| 188 | { |
| 189 | if (!i->parent || i->is_sink) |
| 190 | { |
| 191 | i->is_sink = 0; |
| 192 | for (a=i->first; a; a=a->next) |
| 193 | { |
| 194 | j = a->head; |
| 195 | if (!j->is_marked) |
| 196 | { |
| 197 | if (j->parent == a->sister) set_orphan_rear(j); |
| 198 | if (j->parent && j->is_sink && a->r_cap > 0) set_active(j); |
| 199 | } |
| 200 | } |
| 201 | add_to_changed_list(i); |
| 202 | } |
| 203 | } |
| 204 | else |
| 205 | { |
| 206 | if (!i->parent || !i->is_sink) |
| 207 | { |
| 208 | i->is_sink = 1; |
| 209 | for (a=i->first; a; a=a->next) |
| 210 | { |
| 211 | j = a->head; |
| 212 | if (!j->is_marked) |
| 213 | { |
| 214 | if (j->parent == a->sister) set_orphan_rear(j); |
| 215 | if (j->parent && !j->is_sink && a->sister->r_cap > 0) set_active(j); |
| 216 | } |