Struct stack_graphs::stitching::ForwardPartialPathStitcher

pub struct ForwardPartialPathStitcher { /* private fields */ }

Implements a phased forward partial path stitching algorithm.

Our overall goal is to start with a set of seed partial paths, and to repeatedly extend each partial path by concatenating another, compatible partial path onto the end of it. (If there are multiple compatible partial paths, we concatenate each of them separately, resulting in more than one extension for the current path.)

We perform this processing in phases. At the start of each phase, we have a current set of partial paths that need to be processed. As we extend those partial paths, we add the extensions to the set of partial paths to process in the next phase. Phases are processed one at a time, each time you invoke the process_next_phase method.

After each phase has completed, you can use the previous_phase_partial_paths method to retrieve all of the partial paths that were discovered during that phase. That gives you a chance to add to the Database all of the other partial paths that we might need to extend those partial paths with before invoking the next phase.

If you don’t care about this phasing nonsense, you can instead preload your Database with all possible partial paths, and run the forward partial path stitching algorithm all the way to completion, using the find_all_complete_partial_paths method.

Implementations

impl ForwardPartialPathStitcher

pub fn from_nodes<I>(
    graph: &StackGraph,
    partials: &mut PartialPaths,
    db: &mut Database,
    starting_nodes: I
) -> ForwardPartialPathStitcherwhere
    I: IntoIterator<Item = Handle<Node>>,

Creates a new forward partial path stitcher that is “seeded” with a set of starting stack graph nodes.

Before calling this method, you must ensure that db contains all of the possible partial paths that start with any of your requested starting nodes.

Before calling [process_next_phase][] for the first time, you must ensure that db contains all possible extensions of any of those initial partial paths. You can retrieve a list of those extensions via [previous_phase_partial paths][].

[previous_phase_partial paths]: #method.previous_phase_partial paths [process_next_phase]: #method.process_next_phase

pub fn from_partial_paths(
    initial_partial_paths: Vec<PartialPath>
) -> ForwardPartialPathStitcher

Creates a new forward partial path stitcher that is “seeded” with a set of initial partial paths.

Before calling [process_next_phase][] for the first time, you must ensure that db contains all possible extensions of any of those initial partial paths. You can retrieve a list of those extensions via [previous_phase_partial paths][].

[previous_phase_partial paths]: #method.previous_phase_partial paths [process_next_phase]: #method.process_next_phase

pub fn previous_phase_partial_paths(
    &self
) -> impl Iterator<Item = &PartialPath> + '_

Returns an iterator of all of the (possibly incomplete) partial paths that were encountered during the most recent phase of the algorithm.

pub fn previous_phase_partial_paths_slice(&mut self) -> &[PartialPath]

Returns a slice of all of the (possibly incomplete) partial paths that were encountered during the most recent phase of the algorithm.

pub fn previous_phase_partial_paths_slice_mut(&mut self) -> &mut [PartialPath]

Returns a mutable slice of all of the (possibly incomplete) partial paths that were encountered during the most recent phase of the algorithm.

pub fn set_max_work_per_phase(&mut self, max_work_per_phase: usize)

Sets the maximum amount of work that can be performed during each phase of the algorithm. By bounding our work this way, you can ensure that it’s not possible for our CPU-bound algorithm to starve any worker threads or processes that you might be using. If you don’t call this method, then we allow ourselves to process all of the extensions of all of the paths found in the previous phase, with no additional bound.

pub fn is_complete(&self) -> bool

Returns whether the algorithm has completed.

pub fn process_next_phase(
    &mut self,
    graph: &StackGraph,
    partials: &mut PartialPaths,
    db: &mut Database
)

Runs the next phase of the algorithm. We will have built up a set of incomplete partial paths during the previous phase. Before calling this function, you must ensure that db contains all of the possible other partial paths that we might want to extend any of those candidate partial paths with.

After this method returns, you can use previous_phase_partial_paths to retrieve a list of the (possibly incomplete) partial paths that were encountered during this phase.

pub fn find_all_complete_partial_paths<I>(
    graph: &StackGraph,
    partials: &mut PartialPaths,
    db: &mut Database,
    starting_nodes: I,
    cancellation_flag: &dyn CancellationFlag
) -> Result<Vec<PartialPath>, CancellationError>where
    I: IntoIterator<Item = Handle<Node>>,

Returns all of the complete partial paths that are reachable from a set of starting nodes, building them up by stitching together partial paths from this database.

This function will not return until all reachable partial paths have been processed, so your database must already contain all partial paths that might be needed. If you have a very large stack graph stored in some other storage system, and want more control over lazily loading only the necessary pieces, then you should code up your own loop that calls process_next_phase manually.