| 166 | static void ClearVisitedBits(GraphCycles::Rep* r, const Vec<int32>& nodes); |
| 167 | |
| 168 | bool GraphCycles::InsertEdge(int32 x, int32 y) { |
| 169 | if (x == y) return false; |
| 170 | Rep* r = rep_; |
| 171 | Node* nx = r->nodes_[x]; |
| 172 | if (!nx->out.Insert(y)) { |
| 173 | // Edge already exists. |
| 174 | return true; |
| 175 | } |
| 176 | |
| 177 | Node* ny = r->nodes_[y]; |
| 178 | ny->in.Insert(x); |
| 179 | |
| 180 | if (nx->rank <= ny->rank) { |
| 181 | // New edge is consistent with existing rank assignment. |
| 182 | return true; |
| 183 | } |
| 184 | |
| 185 | // Current rank assignments are incompatible with the new edge. Recompute. |
| 186 | // We only need to consider nodes that fall in the range [ny->rank,nx->rank]. |
| 187 | if (!ForwardDFS(r, y, nx->rank)) { |
| 188 | // Found a cycle. Undo the insertion and tell caller. |
| 189 | nx->out.Erase(y); |
| 190 | ny->in.Erase(x); |
| 191 | // Since we do not call Reorder() on this path, clear any visited |
| 192 | // markers left by ForwardDFS. |
| 193 | ClearVisitedBits(r, r->deltaf_); |
| 194 | return false; |
| 195 | } |
| 196 | BackwardDFS(r, x, ny->rank); |
| 197 | Reorder(r); |
| 198 | return true; |
| 199 | } |
| 200 | |
| 201 | static bool ForwardDFS(GraphCycles::Rep* r, int32 n, int32 upper_bound) { |
| 202 | // Avoid recursion since stack space might be limited. |