| 199 | } |
| 200 | |
| 201 | static bool ForwardDFS(GraphCycles::Rep* r, int32 n, int32 upper_bound) { |
| 202 | // Avoid recursion since stack space might be limited. |
| 203 | // We instead keep a stack of nodes to visit. |
| 204 | r->deltaf_.clear(); |
| 205 | r->stack_.clear(); |
| 206 | r->stack_.push_back(n); |
| 207 | while (!r->stack_.empty()) { |
| 208 | n = r->stack_.back(); |
| 209 | r->stack_.pop_back(); |
| 210 | Node* nn = r->nodes_[n]; |
| 211 | if (nn->visited) continue; |
| 212 | |
| 213 | nn->visited = true; |
| 214 | r->deltaf_.push_back(n); |
| 215 | |
| 216 | for (auto w : nn->out.GetSequence()) { |
| 217 | Node* nw = r->nodes_[w]; |
| 218 | if (nw->rank == upper_bound) { |
| 219 | return false; // Cycle |
| 220 | } |
| 221 | if (!nw->visited && nw->rank < upper_bound) { |
| 222 | r->stack_.push_back(w); |
| 223 | } |
| 224 | } |
| 225 | } |
| 226 | return true; |
| 227 | } |
| 228 | |
| 229 | static void BackwardDFS(GraphCycles::Rep* r, int32 n, int32 lower_bound) { |
| 230 | r->deltab_.clear(); |