| 369 | } |
| 370 | |
| 371 | bool GraphCycles::ContractEdge(int32 a, int32 b) { |
| 372 | CHECK(HasEdge(a, b)); |
| 373 | RemoveEdge(a, b); |
| 374 | |
| 375 | if (IsReachableNonConst(a, b)) { |
| 376 | // Restore the graph to its original state. |
| 377 | InsertEdge(a, b); |
| 378 | return false; |
| 379 | } |
| 380 | |
| 381 | Node* nb = rep_->nodes_[b]; |
| 382 | OrderedNodeSet out = std::move(nb->out); |
| 383 | OrderedNodeSet in = std::move(nb->in); |
| 384 | for (int32 y : out.GetSequence()) { |
| 385 | rep_->nodes_[y]->in.Erase(b); |
| 386 | } |
| 387 | for (int32 y : in.GetSequence()) { |
| 388 | rep_->nodes_[y]->out.Erase(b); |
| 389 | } |
| 390 | rep_->free_nodes_.push_back(b); |
| 391 | |
| 392 | rep_->nodes_[a]->out.Reserve(rep_->nodes_[a]->out.Size() + out.Size()); |
| 393 | for (int32 y : out.GetSequence()) { |
| 394 | InsertEdge(a, y); |
| 395 | } |
| 396 | |
| 397 | rep_->nodes_[a]->in.Reserve(rep_->nodes_[a]->in.Size() + in.Size()); |
| 398 | for (int32 y : in.GetSequence()) { |
| 399 | InsertEdge(y, a); |
| 400 | } |
| 401 | |
| 402 | return true; |
| 403 | } |
| 404 | |
| 405 | absl::Span<const int32> GraphCycles::Successors(int32 node) const { |
| 406 | return rep_->nodes_[node]->out.GetSequence(); |