| 296 | } |
| 297 | |
| 298 | int GraphCycles::FindPath(int32 x, int32 y, int max_path_len, |
| 299 | int32 path[]) const { |
| 300 | // Forward depth first search starting at x until we hit y. |
| 301 | // As we descend into a node, we push it onto the path. |
| 302 | // As we leave a node, we remove it from the path. |
| 303 | int path_len = 0; |
| 304 | |
| 305 | Rep* r = rep_; |
| 306 | NodeSet seen; |
| 307 | r->stack_.clear(); |
| 308 | r->stack_.push_back(x); |
| 309 | while (!r->stack_.empty()) { |
| 310 | int32 n = r->stack_.back(); |
| 311 | r->stack_.pop_back(); |
| 312 | if (n < 0) { |
| 313 | // Marker to indicate that we are leaving a node |
| 314 | path_len--; |
| 315 | continue; |
| 316 | } |
| 317 | |
| 318 | if (path_len < max_path_len) { |
| 319 | path[path_len] = n; |
| 320 | } |
| 321 | path_len++; |
| 322 | r->stack_.push_back(-1); // Will remove tentative path entry |
| 323 | |
| 324 | if (n == y) { |
| 325 | return path_len; |
| 326 | } |
| 327 | |
| 328 | for (auto w : r->nodes_[n]->out.GetSequence()) { |
| 329 | if (seen.insert(w).second) { |
| 330 | r->stack_.push_back(w); |
| 331 | } |
| 332 | } |
| 333 | } |
| 334 | |
| 335 | return 0; |
| 336 | } |
| 337 | |
| 338 | bool GraphCycles::IsReachable(int32 x, int32 y) const { |
| 339 | return FindPath(x, y, 0, nullptr) > 0; |