Struct Dag

pub struct Dag<K, V> { /* private fields */ }

A directed acyclic graph.

Implementations

impl<K: Ord + Copy, V> Dag<K, V>

pub fn new() -> Self

Create a new empty DAG.

pub fn root(key: K, value: V) -> Self

Create a DAG with a root node.

pub fn is_empty(&self) -> bool

Check whether there are any nodes in the graph.

pub fn len(&self) -> usize

Return the number of nodes in the graph.

pub fn node(&mut self, key: K, value: V) -> Option<Node<K, V>>

Add a node to the graph.

pub fn dependency(&mut self, from: K, to: K)

Add a dependency from one node to the other.

pub fn contains(&self, key: &K) -> bool

Check if the graph contains a node.

pub fn get(&self, key: &K) -> Option<&Node<K, V>>

Get a node.

pub fn has_dependency(&self, from: &K, to: &K) -> bool

Check whether there is a dependency between two nodes.

pub fn roots(&self) -> impl Iterator<Item = (&K, &Node<K, V>)> + '_

Get the graph’s root nodes, ie. nodes which don’t depend on other nodes.

pub fn tips(&self) -> impl Iterator<Item = (&K, &Node<K, V>)> + '_

Get the graph’s tip nodes, ie. nodes which aren’t depended on by other nodes.

pub fn merge(&mut self, other: Self)

Merge a DAG into this one.

pub fn sorted(&self) -> VecDeque<K>

Return a topological ordering of the graph’s nodes.

pub fn sorted_by<F>(&self, compare: F) -> VecDeque<K>

where F: FnMut(&K, &K) -> Ordering,

Return a topological ordering of the graph’s nodes. Uses a comparison function to sort partially ordered nodes.

pub fn prune<F>(&mut self, roots: &[K], filter: F)

where F: for<'r> FnMut(&'r K, &'r Node<K, V>, Box<dyn Iterator<Item = (&'r K, &'r Node<K, V>)> + 'r>) -> ControlFlow<()>,

Fold over the graph in topological order, pruning branches along the way. This is a depth-first traversal.

To continue traversing a branch, return ControlFlow::Continue from the filter function. To stop traversal of a branch and prune it, return ControlFlow::Break.

pub fn prune_by<F, P>(&mut self, roots: &[K], filter: F, ordering: P)

where F: for<'r> FnMut(&'r K, &'r Node<K, V>, Box<dyn Iterator<Item = (&'r K, &'r Node<K, V>)> + 'r>) -> ControlFlow<()>, P: Fn((&K, &V), (&K, &V)) -> Ordering,

Fold over the graph in the order provided by order, pruning branches along the way. This is a depth-first traversal.

To continue traversing a branch, return ControlFlow::Continue from the filter function. To stop traversal of a branch and prune it, return ControlFlow::Break.

pub fn fold<A, F>(&self, roots: &[K], acc: A, filter: F) -> A

where F: for<'r> FnMut(A, &'r K, &'r Node<K, V>) -> ControlFlow<A, A>,

Fold over the graph in topological order, skipping certain branches. This is a depth-first traversal.

To continue traversing a branch, return ControlFlow::Continue from the filter function. To stop traversal of a branch, return ControlFlow::Break.

pub fn remove(&mut self, key: &K) -> Option<Node<K, V>>

Remove a node from the graph, and all its dependents.

impl<K: Ord + Copy + Display, V> Dag<K, V>

pub fn to_dot(&self) -> String

Return the graph in “dot” format.

Trait Implementations

impl<K: Clone, V: Clone> Clone for Dag<K, V>

fn clone(&self) -> Dag<K, V>

Returns a copy of the value.

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

Performs copy-assignment from source.

impl<K: Debug, V: Debug> Debug for Dag<K, V>

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

Formats the value using the given formatter.

impl<K: Default, V: Default> Default for Dag<K, V>

fn default() -> Dag<K, V>

Returns the “default value” for a type.

impl<K: Ord + Copy + Debug, V> Index<&K> for Dag<K, V>

type Output = Node<K, V>

The returned type after indexing.

fn index(&self, key: &K) -> &Self::Output

Performs the indexing (container[index]) operation.

impl<K: PartialEq, V: PartialEq> PartialEq for Dag<K, V>

fn eq(&self, other: &Dag<K, V>) -> 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<K: Eq, V: Eq> Eq for Dag<K, V>

impl<K, V> StructuralPartialEq for Dag<K, V>