Struct zepter::dag::Dag

pub struct Dag<T: Ord> {
    pub edges: BTreeMap<T, BTreeSet<T>>,
}

Represents Directed Acyclic Graph through its edge relation.

A “node” in that sense is anything on the left- or right-hand side of this relation.

Fields

edges: BTreeMap<T, BTreeSet<T>>

Dependant -> Dependency eg: Polkadot -> Substrate or Me -> Rust

Implementations

impl<T> Dag<T>

where T: Ord + PartialEq + Clone,

pub fn new() -> Self

Create a new empty Dag.

pub fn add_edge(&mut self, from: T, to: T)

Connect two nodes.

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

Add a node to the Dag without any edges.

pub fn degree(&self, node: &T) -> usize

pub fn adjacent(&self, from: &T, to: &T) -> bool

Whether from is directly adjacent to to.

Directly means with via an edge.

pub fn reachable(&self, from: &T, to: &T) -> bool

Whether from is reachable to to via.

pub fn lhs_contains(&self, from: &T) -> bool

Whether from appears on the lhs of the edge relation.

Aka: Whether self has any dependencies nodes.

pub fn rhs_contains(&self, to: &T) -> bool

Whether to appears on the rhs of the edge relation.

Aka: Whether any other node depends on self.

pub fn dag_of(&self, from: T) -> Self

The Dag only containing the node from and its direct dependencies.

This can be inflated back to the original Dag by calling from.into_transitive_hull_in(self).

pub fn sub(&self, pred: impl Fn(&T) -> bool) -> Self

pub fn lhs_node(&self, from: &T) -> Option<&T>

Get get a ref to the a LHS node.

pub fn lhs_nodes(&self) -> impl Iterator<Item = &T>

pub fn rhs_nodes(&self) -> impl Iterator<Item = &T>

pub fn inverse_lookup<'a>(&'a self, to: &'a T) -> impl Iterator<Item = &'a T>

pub fn transitive_hull(&mut self)

Calculate the transitive hull of self.

pub fn transitive_hull_in(&mut self, topology: &Self)

Calculate the transitive hull of self while using the connectivity of topology.

pub fn into_transitive_hull(self) -> Self

Consume self and return the transitive hull.

pub fn into_transitive_hull_in(self, topology: &Self) -> Self

Consume self and return the transitive hull while using the connectivity of topology.

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

Find any path from from to to.

Note that 1) the shortest path does not necessarily exist and 2) this function does not give any guarantee about the returned path.

This returns Some if (and only if) to is reachable from from.

pub fn reachable_predicate<'a>( &'a self, from: &'a T, pred: impl Fn(&T) -> bool ) -> Option<Path<'a, T>>

Check if any node which fulfills pred can be reached from from and return the first path.

pub fn num_edges(&self) -> usize

The number of edges in the graph.

pub fn num_nodes(&self) -> usize

The number of nodes in the graph.

pub fn lhs_iter(&self) -> impl Iterator<Item = &T>

pub fn rhs_iter(&self) -> impl Iterator<Item = &T>

pub fn node_iter(&self) -> impl Iterator<Item = &T>

Iterate though all LHS and RHS nodes.

Trait Implementations

impl<T: Clone + Ord> Clone for Dag<T>

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

Returns a copy of the value.

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

Performs copy-assignment from source.

impl<T: Ord> Default for Dag<T>

fn default() -> Self

Returns the “default value” for a type.

impl<'de, T> Deserialize<'de> for Dag<T>

where T: Deserialize<'de> + Ord,

fn deserialize<__D>(__deserializer: __D) -> Result<Self, __D::Error>

where __D: Deserializer<'de>,

Deserialize this value from the given Serde deserializer.

impl<T> Display for Dag<T>

where T: Display + Ord,

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

Formats the value using the given formatter.

impl<T> Serialize for Dag<T>

where T: Serialize + Ord,

fn serialize<__S>(&self, __serializer: __S) -> Result<__S::Ok, __S::Error>

where __S: Serializer,

Serialize this value into the given Serde serializer.