pub struct Partition<G: Graph + ?Sized> { /* private fields */ }
Expand description
A partition of a the nodes of a graph.
Tarjan’s algorithm decomposes a directed graph into strongly connected components. Moreover, those components are ordered topologically.
Implementations§
Trait Implementations§
Source§impl<G: Graph + ?Sized> Graph for Partition<G>
impl<G: Graph + ?Sized> Graph for Partition<G>
type Node = usize
type Edge = usize
fn nodes<'a>(&'a self) -> Box<dyn Iterator<Item = usize>>
fn out_edges<'a>(&'a self, u: &usize) -> Box<dyn Iterator<Item = usize> + 'a>
fn in_edges<'a>(&'a self, u: &usize) -> Box<dyn Iterator<Item = usize> + 'a>
fn out_neighbors<'a>( &'a self, u: &Self::Node, ) -> Map<Box<dyn Iterator<Item = Self::Edge> + 'a>, fn(Self::Edge) -> Self::Node>
fn in_neighbors<'a>( &'a self, u: &Self::Node, ) -> Map<Box<dyn Iterator<Item = Self::Edge> + 'a>, fn(Self::Edge) -> Self::Node>
fn dfs<'a>(&'a self) -> Dfs<'a, Self> ⓘ
fn dfs_from<'a>(&'a self, root: &Self::Node) -> Dfs<'a, Self> ⓘ
fn has_path(&self, u: &Self::Node, v: &Self::Node) -> bool
fn tarjan(&self) -> Partition<Self>
fn weak_components(&self) -> Partition<Self>
Source§fn doubled<'a>(&'a self) -> Doubled<'a, Self>
fn doubled<'a>(&'a self) -> Doubled<'a, Self>
Returns the graph that has edges in both directions for every edge that this graph has in
one direction.
Source§fn node_filtered<'a, F>(&'a self, predicate: F) -> NodeFiltered<'a, Self, F>
fn node_filtered<'a, F>(&'a self, predicate: F) -> NodeFiltered<'a, Self, F>
Returns the subgraph of this graph that is induced by the set of nodes for which
predicate
returns true
.Source§fn edge_filtered<'a, F>(&'a self, predicate: F) -> EdgeFiltered<'a, Self, F>
fn edge_filtered<'a, F>(&'a self, predicate: F) -> EdgeFiltered<'a, Self, F>
Returns the subgraph of this graph containing all the edges for which the predicate returns
true.
Source§fn top_sort<'a>(&'a self) -> Option<Vec<Self::Node>>
fn top_sort<'a>(&'a self) -> Option<Vec<Self::Node>>
If this graph is acyclic, returns a topological sort of the vertices. Otherwise, returns
None
.fn linear_order<'a>(&'a self) -> Option<Vec<Self::Node>>
Auto Trait Implementations§
impl<G> Freeze for Partition<G>where
G: ?Sized,
impl<G> RefUnwindSafe for Partition<G>
impl<G> Send for Partition<G>
impl<G> Sync for Partition<G>
impl<G> Unpin for Partition<G>
impl<G> UnwindSafe for Partition<G>
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
Mutably borrows from an owned value. Read more
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>
Converts
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>
Converts
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