Trait Graph

Source

pub trait Graph: Debug {
    type Node: Clone + Debug + Hash + Eq;
    type Error: Error;

    // Required method
    fn is_ancestor(
        &self,
        ancestor: Self::Node,
        descendant: Self::Node,
    ) -> Result<bool, Self::Error>;

    // Provided methods
    fn simplify_success_bounds(
        &self,
        nodes: HashSet<Self::Node>,
    ) -> Result<HashSet<Self::Node>, Self::Error> { ... }
    fn simplify_failure_bounds(
        &self,
        nodes: HashSet<Self::Node>,
    ) -> Result<HashSet<Self::Node>, Self::Error> { ... }
}

Expand description

The set of nodes compromising a directed acyclic graph to be searched.

Required Associated Types§

Source

type Node: Clone + Debug + Hash + Eq

The type of nodes in the graph. This should be cheap to clone.

Source

type Error: Error

An error type.

Required Methods§

Source

fn is_ancestor( &self, ancestor: Self::Node, descendant: Self::Node, ) -> Result<bool, Self::Error>

Return whether or not node is an ancestor of descendant. A node X`` is said to be an "ancestor" of node Y` if one of the following is true:

X == Y
X is an immediate parent of Y.
X is an ancestor of an immediate parent of Y (defined recursively).

Provided Methods§

Source

fn simplify_success_bounds( &self, nodes: HashSet<Self::Node>, ) -> Result<HashSet<Self::Node>, Self::Error>

Filter nodes to only include nodes that are not ancestors of any other node in nodes. This is not strictly necessary, but it improves performance as some operations are linear in the size of the success bounds, and it can make the intermediate results more sensible.

This operation is called heads in e.g. Mercurial.

Source

fn simplify_failure_bounds( &self, nodes: HashSet<Self::Node>, ) -> Result<HashSet<Self::Node>, Self::Error>

Filter nodes to only include nodes that are not descendants of any other node in nodes. This is not strictly necessary, but it improves performance as some operations are linear in the size of the failure bounds, and it can make the intermediate results more sensible.

This operation is called roots in e.g. Mercurial.