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.

Example

This example creates a graph of dependencies in a hypothetical compiler or build tool, with edges from a dependency to the targets that use them.

use id_arena::Arena;
use id_arena::Id;
use toposort_scc::ArenaGraph;

// a target during compilation, having a name and dependencies
struct Target { name: &'static str, deps: Vec<Id<Target>> }
impl Target {
    fn new(name: &'static str) -> Self {
        Target { name, deps: Vec::new() }
    }
}

let mut arena: Arena<Target> = Arena::new();

let program = arena.alloc(Target::new("program"));
let main_c = arena.alloc(Target::new("main.c"));
let util_c = arena.alloc(Target::new("util.c"));
let util_h = arena.alloc(Target::new("util.h"));
let libfoo_so = arena.alloc(Target::new("libfoo_so"));

arena[program].deps.extend_from_slice(&[main_c, util_c, libfoo_so]);
arena[main_c].deps.push(util_h);
arena[util_c].deps.push(util_h);

let g = ArenaGraph::from_graph(&arena, |mut builder, target| {
    for &dep in &target.deps {
        builder.add_in_edge(dep);
    }
});

To get a graph with edges in the other direction, use .add_out_edge() or the .transpose() method of the graph.

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 try_toposort(self) -> Result<Vec<A::Id>, ArenaGraph<'a, T, A>>

Try to perform topological sort on the graph

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, returns the graph as Err(self).

The difference between this function and IndexGraph::try_toposort() is that this function returns id-arena ids instead of indices.

For examples, see IndexGraph::toposort()

pub fn toposort(self) -> Option<Vec<A::Id>>

Perform topological sort on the graph

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

If the graph contains cycles, returns None.

The difference between this function and IndexGraph::toposort() is that this function returns id-arena ids instead of indices.

For examples, see IndexGraph::toposort()

pub fn scc(self) -> Vec<Vec<A::Id>>

Find strongly connected components

Finds the strongly connected components of this graph using Kosaraju's algorithm and returns them.

The difference between this function and IndexGraph::scc() is that this function returns id-arena ids instead of indices.

For examples, see IndexGraph::toposort_or_scc()

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).

The difference between this function and IndexGraph::toposort_or_scc() is that this function returns id-arena ids instead of indices.

For examples, see IndexGraph::toposort_or_scc()

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.