Type Alias DiGraph

pub type DiGraph<N, S = FixedHasher> = Graph<true, N, S>;

A Graph with directed edges of some GraphNodeId N.

For example, an edge from 1 to 2 is distinct from an edge from 2 to 1.

Aliased Type

pub struct DiGraph<N, S = FixedHasher> { /* private fields */ }

Implementations

impl<N: GraphNodeId, S: BuildHasher> DiGraph<N, S>

pub fn toposort( &self, scratch: Vec<N>, ) -> Result<Vec<N>, DiGraphToposortError<N>>

Tries to topologically sort this directed graph.

If the graph is acyclic, returns [Ok] with the list of [GraphNodeId]s in a valid topological order. If the graph contains cycles, returns [Err] with the list of strongly-connected components that contain cycles (also in a valid topological order).

Errors

• If the graph contains a self-loop, returns [DiGraphToposortError::Loop].
• If the graph contains cycles, returns [DiGraphToposortError::Cycle].

pub fn simple_cycles_in_component(&self, scc: &[N]) -> Vec<Vec<N>>

Returns the simple cycles in a strongly-connected component of a directed graph.

The algorithm implemented comes from “Finding all the elementary circuits of a directed graph” by D. B. Johnson.