Struct DirectedGraph 

pub struct DirectedGraph<T: Clone + PartialEq + Hash + Ord + Debug + Display>(/* private fields */);

A directed graph, whose nodes contain an identifier of type T.

Implementations

impl<T: Clone + PartialEq + Hash + Ord + Debug + Display> DirectedGraph<T>

pub fn new() -> Self

Created a new empty DirectedGraph.

pub fn retain(&mut self, predicate: impl Fn(&T, &T) -> bool)

Remove all edges that don’t match the given predicate.

pub fn extend(&mut self, other: impl IntoIterator<Item = (T, T)>)

pub fn add_edge(&mut self, source: T, target: T)

Add an edge to the graph, adding nodes if necessary.

pub fn get_targets<'a>(&'a self, id: &T) -> Option<&'a HashSet<T>>

Get targets of all edges from this node.

pub fn get_closure<'a>(&'a self, start: &T) -> HashSet<&'a T>

Given a dependency graph, find the set of all nodes that have a dependency on the start node (i.e., the reverse dependency closure). This includes start itself.

pub fn add_node(&mut self, source: T)

Adds an edgeless node to the graph. Used by shutdown to ensure every node gets visited, even if there are no paths to the node.

pub fn topological_sort<'a>(&'a self) -> Result<Vec<&'a T>, Error<'_, T>>

Returns the nodes of the graph in reverse topological order, or an error if the graph contains a cycle.

pub fn find_shortest_path<'a>(&'a self, from: &T, to: &T) -> Option<Vec<&'a T>>

Finds the shortest path between the from and to nodes in this graph, if such a path exists. Both from and to are included in the returned path.

Trait Implementations

impl<T: Clone + Clone + PartialEq + Hash + Ord + Debug + Display> Clone for DirectedGraph<T>

fn clone(&self) -> DirectedGraph<T>

Returns a duplicate of the value.

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.

impl<T: Debug + Clone + PartialEq + Hash + Ord + Debug + Display> Debug for DirectedGraph<T>

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.

impl<T: Clone + PartialEq + Hash + Ord + Debug + Display> Default for DirectedGraph<T>

fn default() -> Self

Returns the “default value” for a type.

impl<T: Clone + PartialEq + Hash + Ord + Debug + Display, const N: usize> From<[(T, T); N]> for DirectedGraph<T>

fn from(items: [(T, T); N]) -> Self

Converts to this type from the input type.

impl<T: Clone + PartialEq + Hash + Ord + Debug + Display> From<Box<[(T, T)]>> for DirectedGraph<T>

fn from(items: Box<[(T, T)]>) -> Self

Converts to this type from the input type.

impl<T: Clone + PartialEq + Hash + Ord + Debug + Display + 'static> IntoIterator for DirectedGraph<T>

type Item = (T, T)

The type of the elements being iterated over.

type IntoIter = Box<dyn Iterator<Item = (T, T)>>

Which kind of iterator are we turning this into?

fn into_iter(self) -> Self::IntoIter

Creates an iterator from a value.

impl<T: PartialEq + Clone + PartialEq + Hash + Ord + Debug + Display> PartialEq for DirectedGraph<T>

fn eq(&self, other: &DirectedGraph<T>) -> bool

Tests for self and other values to be equal, and is used by ==.

fn ne(&self, other: &Rhs) -> bool

Tests for !=. The default implementation is almost always sufficient, and should not be overridden without very good reason.

impl<T: Eq + Clone + PartialEq + Hash + Ord + Debug + Display> Eq for DirectedGraph<T>

impl<T: Clone + PartialEq + Hash + Ord + Debug + Display> StructuralPartialEq for DirectedGraph<T>