pub struct Dag<T: Ord> {
pub edges: BTreeMap<T, BTreeSet<T>>,
}
Expand description
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§
source§impl<T> Dag<T>
impl<T> Dag<T>
pub fn degree(&self, node: &T) -> usize
sourcepub fn adjacent(&self, from: &T, to: &T) -> bool
pub fn adjacent(&self, from: &T, to: &T) -> bool
Whether from
is directly adjacent to to
.
Directly means with via an edge.
sourcepub fn lhs_contains(&self, from: &T) -> bool
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.
sourcepub fn rhs_contains(&self, to: &T) -> bool
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
.
sourcepub fn dag_of(&self, from: T) -> 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_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>
sourcepub fn transitive_hull(&mut self)
pub fn transitive_hull(&mut self)
Calculate the transitive hull of self
.
sourcepub fn transitive_hull_in(&mut self, topology: &Self)
pub fn transitive_hull_in(&mut self, topology: &Self)
Calculate the transitive hull of self
while using the connectivity of topology
.
sourcepub fn into_transitive_hull(self) -> Self
pub fn into_transitive_hull(self) -> Self
Consume self
and return the transitive hull.
sourcepub fn into_transitive_hull_in(self, topology: &Self) -> Self
pub fn into_transitive_hull_in(self, topology: &Self) -> Self
Consume self
and return the transitive hull while using the connectivity of topology
.
sourcepub fn any_path<'a>(&'a self, from: &'a T, to: &T) -> Option<Path<'a, T>>
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
.
sourcepub fn reachable_predicate<'a>(
&'a self,
from: &'a T,
pred: impl Fn(&T) -> bool,
) -> Option<Path<'a, T>>
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 lhs_iter(&self) -> impl Iterator<Item = &T>
pub fn rhs_iter(&self) -> impl Iterator<Item = &T>
Trait Implementations§
source§impl<'de, T> Deserialize<'de> for Dag<T>where
T: Deserialize<'de> + Ord,
impl<'de, T> Deserialize<'de> for Dag<T>where
T: Deserialize<'de> + Ord,
source§fn deserialize<__D>(__deserializer: __D) -> Result<Self, __D::Error>where
__D: Deserializer<'de>,
fn deserialize<__D>(__deserializer: __D) -> Result<Self, __D::Error>where
__D: Deserializer<'de>,
Auto Trait Implementations§
impl<T> Freeze for Dag<T>
impl<T> RefUnwindSafe for Dag<T>where
T: RefUnwindSafe,
impl<T> Send for Dag<T>where
T: Send,
impl<T> Sync for Dag<T>where
T: Sync,
impl<T> Unpin for Dag<T>
impl<T> UnwindSafe for Dag<T>where
T: RefUnwindSafe,
Blanket Implementations§
source§impl<T> BorrowMut<T> for Twhere
T: ?Sized,
impl<T> BorrowMut<T> for Twhere
T: ?Sized,
source§fn borrow_mut(&mut self) -> &mut T
fn borrow_mut(&mut self) -> &mut T
source§impl<T> CloneToUninit for Twhere
T: Clone,
impl<T> CloneToUninit for Twhere
T: Clone,
source§default unsafe fn clone_to_uninit(&self, dst: *mut T)
default unsafe fn clone_to_uninit(&self, dst: *mut T)
clone_to_uninit
)source§impl<T> IntoEither for T
impl<T> IntoEither for T
source§fn into_either(self, into_left: bool) -> Either<Self, Self>
fn into_either(self, into_left: bool) -> Either<Self, Self>
self
into a Left
variant of Either<Self, Self>
if into_left
is true
.
Converts self
into a Right
variant of Either<Self, Self>
otherwise. Read moresource§fn into_either_with<F>(self, into_left: F) -> Either<Self, Self>
fn into_either_with<F>(self, into_left: F) -> Either<Self, Self>
self
into a Left
variant of Either<Self, Self>
if into_left(&self)
returns true
.
Converts self
into a Right
variant of Either<Self, Self>
otherwise. Read more