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 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 + PartialEq + Hash + Ord + Debug + Display> Default for DirectedGraph<T>

fn default() -> Self

Returns the “default value” for a type.