Function nonrecursive_dft

src/ore/src/graph.rs:131–175

A non-recursive implementation of an infallible depth-first traversal starting from `root`. Assumes that nodes in the graph all have unique node ids. `at_enter` runs when entering a node. It is expected to return an in-order list of the children of the node. You can omit children from the list returned if you want to skip the traversing subgraphs corresponding to those children. If no children a

(
    graph: &Graph,
    root: NodeId,
    at_enter: &mut AtEnter,
    at_exit: &mut AtExit,
)

/// This function only enters and exits a node at most once and thus is safe to
/// run even if the graph contains a cycle.
pub fn nonrecursive_dft<Graph, NodeId, AtEnter, AtExit>(
    graph: &Graph,
    root: NodeId,
    at_enter: &mut AtEnter,
    at_exit: &mut AtExit,
) where
    NodeId: std::cmp::Ord,
    AtEnter: FnMut(&Graph, &NodeId) -> Vec<NodeId>,
    AtExit: FnMut(&Graph, &NodeId) -> (),
{
    // All nodes that have been entered but not exited. Last node in the vec is
    // the node that we most recently entered.
    let mut entered = Vec::new();
    // All nodes that have been exited.
    let mut exited = BTreeSet::new();

    // Pseudocode for the recursive version of this function would look like:
    // ```
    // atenter(graph, node)
    // foreach child in children(graph, node):
    //    recursive_call(graph, child)
    // atexit(graph, node)
    // ```
    // In this non-recursive implementation, you can think of the call stack as
    // been replaced by `entered`. Every time an object is pushed into `entered`
    // would have been a time you would have pushed a recursive call onto the
    // call stack. Likewise, times an object is popped from `entered` would have
    // been times when recursive calls leave the stack.

    // Enter from the root.
    let children = at_enter(graph, &root);
    entered_node(&mut entered, root, children);
    while !entered.is_empty() {
        if let Some(to_enter) = find_next_child_to_enter(&mut entered, &exited) {
            let children = at_enter(graph, &to_enter);
            entered_node(&mut entered, to_enter, children);
        } else {
            // If this node has no more children to descend into,
            // exit the current node and run `at_exit`.
            let (to_exit, _) = entered.pop().unwrap();
            at_exit(graph, &to_exit);
            exited.insert(to_exit);
        }
    }
}

/// Same as [`nonrecursive_dft`], but allows changes to be made to the graph.
pub fn nonrecursive_dft_mut<Graph, NodeId, AtEnter, AtExit>(