| 247 | } |
| 248 | |
| 249 | void Graph::TopologicalSort() { |
| 250 | rank_to_node_.clear(); |
| 251 | |
| 252 | std::vector<std::uint8_t> marks(nodes_.size(), 0); |
| 253 | std::vector<bool> ignored(nodes_.size(), 0); |
| 254 | |
| 255 | std::stack<Node*> stack; |
| 256 | for (const auto& it : nodes_) { |
| 257 | if (marks[it->id] != 0) { |
| 258 | continue; |
| 259 | } |
| 260 | stack.push(it.get()); |
| 261 | while (!stack.empty()) { |
| 262 | auto curr = stack.top(); |
| 263 | bool is_valid = true; |
| 264 | if (marks[curr->id] != 2) { |
| 265 | for (const auto& jt : curr->inedges) { |
| 266 | if (marks[jt->tail->id] != 2) { |
| 267 | stack.push(jt->tail); |
| 268 | is_valid = false; |
| 269 | } |
| 270 | } |
| 271 | if (!ignored[curr->id]) { |
| 272 | for (const auto& jt : curr->aligned_nodes) { |
| 273 | if (marks[jt->id] != 2) { |
| 274 | stack.push(jt); |
| 275 | ignored[jt->id] = true; |
| 276 | is_valid = false; |
| 277 | } |
| 278 | } |
| 279 | } |
| 280 | |
| 281 | assert((is_valid || marks[curr->id] != 1) && "Graph is not a DAG"); |
| 282 | |
| 283 | if (is_valid) { |
| 284 | marks[curr->id] = 2; |
| 285 | if (!ignored[curr->id]) { |
| 286 | rank_to_node_.emplace_back(curr); |
| 287 | for (const auto& jt : curr->aligned_nodes) { |
| 288 | rank_to_node_.emplace_back(jt); |
| 289 | } |
| 290 | } |
| 291 | } else { |
| 292 | marks[curr->id] = 1; |
| 293 | } |
| 294 | } |
| 295 | |
| 296 | if (is_valid) { |
| 297 | stack.pop(); |
| 298 | } |
| 299 | } |
| 300 | } |
| 301 | |
| 302 | assert(IsTopologicallySorted() && "Graph is not topologically sorted"); |
| 303 | } |
| 304 | |
| 305 | bool Graph::IsTopologicallySorted() const { |
| 306 | assert(nodes_.size() == rank_to_node_.size() && "Topological sort not called "); // NOLINT |