Copied from TF ReverseDFS, which only works for Graph.
| 269 | |
| 270 | // Copied from TF ReverseDFS, which only works for Graph. |
| 271 | void StableDFS(const SimpleGraph& g, bool reverse, |
| 272 | const std::vector<const SimpleNode*>& start, |
| 273 | const std::function<bool(const SimpleNode*)>& enter, |
| 274 | const std::function<bool(const SimpleNode*)>& leave) { |
| 275 | // Stack of work to do. |
| 276 | struct Work { |
| 277 | const SimpleNode* node; |
| 278 | bool leave; // Are we entering or leaving n? |
| 279 | }; |
| 280 | std::vector<Work> stack(start.size()); |
| 281 | for (int i = 0; i < start.size(); ++i) { |
| 282 | stack[i] = Work{start[i], false}; |
| 283 | } |
| 284 | |
| 285 | auto get_nodes = reverse ? [](const SimpleNode* n) { return n->in_nodes(); } |
| 286 | : [](const SimpleNode* n) { return n->out_nodes(); }; |
| 287 | std::vector<bool> visited(g.num_node_ids(), false); |
| 288 | while (!stack.empty()) { |
| 289 | Work w = stack.back(); |
| 290 | stack.pop_back(); |
| 291 | |
| 292 | auto n = w.node; |
| 293 | if (w.leave) { |
| 294 | if (leave && !leave(n)) return; |
| 295 | continue; |
| 296 | } |
| 297 | |
| 298 | if (visited[n->id()]) continue; |
| 299 | visited[n->id()] = true; |
| 300 | if (enter && !enter(n)) return; |
| 301 | |
| 302 | // Arrange to call leave(n) when all done with descendants. |
| 303 | if (leave) stack.push_back(Work{n, true}); |
| 304 | |
| 305 | auto nodes = get_nodes(n); |
| 306 | std::vector<const SimpleNode*> nodes_sorted(nodes.begin(), nodes.end()); |
| 307 | std::sort(nodes_sorted.begin(), nodes_sorted.end(), |
| 308 | [](const SimpleNode* lhs, const SimpleNode* rhs) { |
| 309 | return lhs->name() < rhs->name(); |
| 310 | }); |
| 311 | for (const SimpleNode* node : nodes_sorted) { |
| 312 | if (!visited[node->id()]) { |
| 313 | stack.push_back(Work{node, false}); |
| 314 | } |
| 315 | } |
| 316 | } |
| 317 | } |
| 318 | |
| 319 | bool CanContractEdge(const SimpleEdge* edge, |
| 320 | const std::unique_ptr<SimpleGraph>& graph) { |