Module visits

Visits on graphs.

Implementation of sequential and parallel visits depend on a type parameter A implementing the trait Event; they provide visit methods accepting a callback function with argument A and returning a ControlFlow<E, ()>, where E is a type parameter of the visit method: for example, E might be StoppedWhenDone when completing early, Interrupted when interrupted or Infallible if the visit cannot be interrupted.

If a callback returns Break, the visit will be interrupted, and the interrupt propagated to the caller of the visit method; for uninterruptible visits we suggest to use the no-break crate and its continue_value_no_break method on the result to let type inference run smoothly.

Note that an interruption does not necessarily denote an error condition (see, e.g., StoppedWhenDone).

Sequential visits are visits that are executed in a single thread, whereas parallel visits use multiple threads. The signature of callbacks reflects this difference (FnMut for the sequential case vs. Fn + Sync for the parallel case).

In case of interruption sequential visits usually return immediately to the caller, whereas in general parallel visits might need to complete part of their subtasks before returning to the caller.

Additionally, implementations might accepts a filter function accepting a Event::FilterArgs that will be called when a new node is discovered. If the filter returns false, the node will be ignored, that is, not even marked as known. Note that in case of parallel visits the filter might be called multiple times on the same node (and with a different predecessor, if available) due to race conditions.

All visits have also methods accepting an init item similarly to the Rayon map_with method. For parallel visits, the item will be cloned.

There is a blanket implementation of the Parallel trait for all types implementing the Sequential trait. This approach makes it possible to have structures that can use both sequential and parallel visits.

Visit must provide a reset method that makes it possible to reuse the visit.

Examples

There are examples of visits in SeqIter, ParFair and ParLowMem.

Modules

breadth_first

Breadth-first visits.

depth_first

Depth-first visits.

Structs

Interrupted

The visit was interrupted.

StoppedWhenDone

The result of the visit was computed without completing the visit; for example, during an acyclicity test a single arc pointing at the visit path is sufficient to compute the result.

Traits

Event

Types usable as arguments for the callbacks in visits.

Parallel

A parallel visit.

Sequential

A sequential visit.

Type Aliases

FilterArgs

A convenience type alias for the filter arguments of an event.