Function futures_ext::bounded_traversal::bounded_traversal_dag

pub fn bounded_traversal_dag<In, Ins, Out, OutCtx, Unfold, UFut, Fold, FFut>(
    scheduled_max: usize, 
    init: In, 
    unfold: Unfold, 
    fold: Fold
) -> impl Future<Item = Option<Out>, Error = UFut::Error> where
    In: Eq + Hash + Clone,
    Out: Clone,
    Unfold: FnMut(In) -> UFut,
    UFut: IntoFuture<Item = (OutCtx, Ins)>,
    Ins: IntoIterator<Item = In>,
    Fold: FnMut(OutCtx, Iter<Out>) -> FFut,
    FFut: IntoFuture<Item = Out, Error = UFut::Error>, 

bounded_traversal_dag traverses implicit asynchronous DAG specified by init and unfold arguments, and it also does backward pass with fold operation. All unfold and fold operations are executed in parallel if they do not depend on each other (not related by ancestor-descendant relation in implicit DAG) with amount of concurrency constrained by scheduled_max.

Difference between bounded_traversal_dag and bounded_traversal

Obvious difference is that bounded_traversal_dag correctly handles DAGs (bounded_traversal treats all children references as distinct and its execution time is proportional to number of paths from the root, since DAG can be constructed to contain O(exp(N)) path it might cause problems) but it comes with a price:

• bounded_traversal_dag keeps Out result of computation for all the nodes but bounded_traversal only keeps results for nodes that have not been completely evaluatated
• In has additional constraints to be Eq + Hash + Clone
• Out has additional constraint to be Clone

init: In

Is the root of the implicit tree to be traversed

unfold: FnMut(In) -> impl IntoFuture<Item = (OutCtx, impl IntoIterator<Item = In>)>

Asynchronous function which given input value produces list of its children. And context associated with current node. If this list is empty, it is a leaf of the tree, and fold will be run on this node.

fold: FnMut(OutCtx, impl Iterator<Out>) -> impl IntoFuture<Item=Out>

Aynchronous function which given node context and output of fold for its chidlren should produce new output value.

return value impl Future<Item = Option<Out>>

Result of running fold operation on the root of the tree. None indiciate that cycle has been found.