Struct enso_data::dependency_graph::DependencyGraph

pub struct DependencyGraph<T> { /* fields omitted */ }

Dependency graph keeping track of Nodes and their dependencies.

The primary use case of this graph is topological sorting of dependencies. Please note that this graph implementation is not DAG, it can contain cycles. In case a cycle occurs it will be automatically broken on the lowest node id.

Implementations

impl<T: Clone + Eq + Hash + Ord> DependencyGraph<T>

pub fn new() -> Self

Constructor.

pub fn insert_dependency(&mut self, first: T, second: T) -> bool

Insert a new dependency to the graph. Returns true if the insertion was successful (the dependency was not present already), or false otherwise.

pub fn remove_dependency(&mut self, first: T, second: T) -> bool

Remove a dependency from the graph. Returns true if the dependency was found, or false otherwise.

pub fn keep_only(&mut self, keys: &[T])

Removes all (incoming and outgoing) dependencies from nodes whose indexes do not belong to the provided slice.

pub fn kept_only(self, keys: &[T]) -> Self

Removes all (incoming and outgoing) dependencies from nodes whose indexes do not belong to the provided slice.

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

Just like [keep_only], but the provided slice must be sorted.

pub fn unchecked_kept_only(
    self,
    sorted_keys: impl IntoIterator<Item = T>
) -> Self

Just like [kept_only], but the provided slice must be sorted.

pub fn topo_sort(&self, keys: &[T]) -> Vec<T>

Sorts the provided indexes in topological order based on the rules recorded in the graph. In case the graph is not a DAG, it will still be sorted by breaking cycles on elements with the smallest index.

pub fn into_topo_sort(self, keys: &[T]) -> Vec<T>

Just like [topo_sort], but consumes the current dependency graph instead of cloning it.

pub fn unchecked_topo_sort(&self, sorted_keys: Vec<T>) -> Vec<T>

Just like [topo_sort], but the provided slice must be sorted.

pub fn into_unchecked_topo_sort(self, sorted_keys: Vec<T>) -> Vec<T>

Just like [unchecked_topo_sort], bbut consumes the current dependency graph instead of cloning it.

Trait Implementations

impl<T: Clone> Clone for DependencyGraph<T>

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

Returns a copy of the value.

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

Performs copy-assignment from source.

impl<T> Debug for DependencyGraph<T> where
    T: Debug + Eq + Hash, 

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

Formats the value using the given formatter.

impl<T> Default for DependencyGraph<T> where
    T: Eq + Hash + Ord, 

fn default() -> Self

Returns the “default value” for a type.

impl<T: Ord> Extend<(T, Node<T>)> for DependencyGraph<T>

fn extend<I: IntoIterator<Item = (T, Node<T>)>>(&mut self, iter: I)

Extends a collection with the contents of an iterator.

fn extend_one(&mut self, item: A)

🔬 This is a nightly-only experimental API. (extend_one)

Extends a collection with exactly one element.

fn extend_reserve(&mut self, additional: usize)

🔬 This is a nightly-only experimental API. (extend_one)

Reserves capacity in a collection for the given number of additional elements.

impl<'a, T> IntoIterator for &'a DependencyGraph<T>

type Item = (&'a T, &'a Node<T>)

The type of the elements being iterated over.

type IntoIter = Iter<'a, T, Node<T>>

Which kind of iterator are we turning this into?

fn into_iter(self) -> Iter<'a, T, Node<T>>

Creates an iterator from a value.

impl<T> IntoIterator for DependencyGraph<T>

type Item = (T, Node<T>)

The type of the elements being iterated over.

type IntoIter = IntoIter<T, Node<T>>

Which kind of iterator are we turning this into?

fn into_iter(self) -> IntoIter<T, Node<T>>

Creates an iterator from a value.