Struct toposort_scc::ArenaGraph

pub struct ArenaGraph<'a, T, A: ArenaBehavior> { /* fields omitted */ }

An adjacency-list-based graph data structure wrapping an Arena from the id-arena crate.

Stores graph vertices as lists of incoming and outgoing edges by their Id in the graph.

Implementations

impl<'a, T, A: ArenaBehavior> ArenaGraph<'a, T, A>

pub fn from_graph<F>(g: &'a Arena<T, A>, f: F) -> ArenaGraph<'a, T, A> where
    F: FnMut(ArenaGraphBuilder<'_, 'a, T, A>, &T), 

Create a new graph from an existing Arena-based graph-like data structure

The given closure will be called once for every element of g, with an ArenaGraphBuilder instance so that edges can be easily added.

pub fn arena_id(&self) -> u32

Returns the id of the arena this graph belongs to

pub fn as_index_graph(&self) -> &IndexGraph

Returns a reference to the underlying IndexGraph

pub fn into_index_graph(self) -> IndexGraph

Returns the underlying IndexGraph

pub fn toposort_or_scc(self) -> Result<Vec<A::Id>, Vec<Vec<A::Id>>>

Perform topological sort or find strongly connected components

If the graph contains no cycles, finds the topological ordering of this graph using Kahn's algorithm and returns it as Ok(sorted).

If the graph contains cycles, finds the strongly connected components of this graph using Kosaraju's algorithm and returns them as Err(cycles).

Trait Implementations

impl<'a, T: Clone, A: Clone + ArenaBehavior> Clone for ArenaGraph<'a, T, A>

fn clone(&self) -> ArenaGraph<'a, T, A>

Returns a copy of the value.

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

Performs copy-assignment from source.

impl<'a, T: Debug, A: Debug + ArenaBehavior> Debug for ArenaGraph<'a, T, A>

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

Formats the value using the given formatter.

impl<'_, T, A: ArenaBehavior> Index<<A as ArenaBehavior>::Id> for ArenaGraph<'_, T, A>

type Output = Vertex

The returned type after indexing.

fn index(&self, id: A::Id) -> &Vertex

Performs the indexing (container[index]) operation.