| 25 | namespace { |
| 26 | template <typename T> |
| 27 | void DFSFromHelper(const Graph& g, gtl::ArraySlice<T> start, |
| 28 | const std::function<void(T)>& enter, |
| 29 | const std::function<void(T)>& leave, |
| 30 | const NodeComparator& stable_comparator, |
| 31 | const EdgeFilter& edge_filter) { |
| 32 | // Stack of work to do. |
| 33 | struct Work { |
| 34 | T node; |
| 35 | bool leave; // Are we entering or leaving n? |
| 36 | }; |
| 37 | std::vector<Work> stack(start.size()); |
| 38 | for (int i = 0; i < start.size(); ++i) { |
| 39 | stack[i] = Work{start[i], false}; |
| 40 | } |
| 41 | |
| 42 | std::vector<bool> visited(g.num_node_ids(), false); |
| 43 | while (!stack.empty()) { |
| 44 | Work w = stack.back(); |
| 45 | stack.pop_back(); |
| 46 | |
| 47 | T n = w.node; |
| 48 | if (w.leave) { |
| 49 | leave(n); |
| 50 | continue; |
| 51 | } |
| 52 | |
| 53 | if (visited[n->id()]) continue; |
| 54 | visited[n->id()] = true; |
| 55 | if (enter) enter(n); |
| 56 | |
| 57 | // Arrange to call leave(n) when all done with descendants. |
| 58 | if (leave) stack.push_back(Work{n, true}); |
| 59 | |
| 60 | auto add_work = [&visited, &stack](Node* out) { |
| 61 | if (!visited[out->id()]) { |
| 62 | // Note; we must not mark as visited until we actually process it. |
| 63 | stack.push_back(Work{out, false}); |
| 64 | } |
| 65 | }; |
| 66 | |
| 67 | if (stable_comparator) { |
| 68 | std::vector<Node*> nodes_sorted; |
| 69 | for (const Edge* out_edge : n->out_edges()) { |
| 70 | if (!edge_filter || edge_filter(*out_edge)) { |
| 71 | nodes_sorted.emplace_back(out_edge->dst()); |
| 72 | } |
| 73 | } |
| 74 | std::sort(nodes_sorted.begin(), nodes_sorted.end(), stable_comparator); |
| 75 | for (Node* out : nodes_sorted) { |
| 76 | add_work(out); |
| 77 | } |
| 78 | } else { |
| 79 | for (const Edge* out_edge : n->out_edges()) { |
| 80 | if (!edge_filter || edge_filter(*out_edge)) { |
| 81 | add_work(out_edge->dst()); |
| 82 | } |
| 83 | } |
| 84 | } |