Struct stack_graphs::stitching::PathStitcher

pub struct PathStitcher { /* private fields */ }

Implements a phased path-stitching algorithm.

Our overall goal is to start with a set of seed paths, and to repeatedly extend each path by appending a compatible partial path onto the end of it. (If there are multiple compatible partial paths, we append 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 paths that need to be processed. As we extend those paths, we add the extensions to the set of 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_paths method to retrieve all of the paths that were discovered during that phase. That gives you a chance to add to the Database all of the partial paths that we might need to extend those 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 path-stitching algorithm all the way to completion, using the find_all_complete_paths method.

Implementations

impl PathStitcher

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

Creates a new 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 paths. You can retrieve a list of those extensions via previous_phase_paths.

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

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

pub fn previous_phase_paths_slice(&mut self) -> &[Path]

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

pub fn previous_phase_paths_slice_mut(&mut self) -> &mut [Path]

Returns a mutable slice of all of the (possibly incomplete) paths that were encountered during the most recent phase of the path-stitching 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 path-stitching algorithm has completed.

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

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

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

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

Returns all of the complete 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 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.