| 340 | } |
| 341 | |
| 342 | bool GraphCycles::IsReachableNonConst(int32 x, int32 y) { |
| 343 | if (x == y) return true; |
| 344 | Rep* r = rep_; |
| 345 | Node* nx = r->nodes_[x]; |
| 346 | Node* ny = r->nodes_[y]; |
| 347 | |
| 348 | if (nx->rank >= ny->rank) { |
| 349 | // x cannot reach y since it is after it in the topological ordering |
| 350 | return false; |
| 351 | } |
| 352 | |
| 353 | // See if x can reach y using a DFS search that is limited to y's rank |
| 354 | bool reachable = !ForwardDFS(r, x, ny->rank); |
| 355 | |
| 356 | // Clear any visited markers left by ForwardDFS. |
| 357 | ClearVisitedBits(r, r->deltaf_); |
| 358 | return reachable; |
| 359 | } |
| 360 | |
| 361 | bool GraphCycles::CanContractEdge(int32 a, int32 b) { |
| 362 | CHECK(HasEdge(a, b)) << "No edge exists from " << a << " to " << b; |