Struct Dag 

pub struct Dag<N, S = FixedHasher>
where
    N: GraphNodeId,
    S: BuildHasher,
{ /* private fields */ }

A directed acyclic graph structure.

Implementations

impl<N, S> Dag<N, S>

where N: GraphNodeId, S: BuildHasher,

pub fn new() -> Dag<N, S>

where S: Default,

Creates a new directed acyclic graph.

pub fn graph(&self) -> &Graph<true, N, S>

Read-only access to the underlying directed graph.

pub fn graph_mut(&mut self) -> &mut Graph<true, N, S>

Mutable access to the underlying directed graph. Marks the graph as dirty.

pub fn is_dirty(&self) -> bool

Returns whether the graph is dirty (i.e., has been modified since the last topological sort).

pub fn is_toposorted(&self) -> bool

Returns whether the graph is topologically sorted (i.e., not dirty).

pub fn ensure_toposorted(&mut self) -> Result<(), DiGraphToposortError<N>>

Ensures the graph is topologically sorted, recomputing the toposort if the graph is dirty.

Errors

Returns DiGraphToposortError if the DAG is dirty and cannot be topologically sorted.

pub fn get_toposort(&self) -> Option<&[N]>

Returns the cached toposort if the graph is not dirty, otherwise returns None.

pub fn toposort(&mut self) -> Result<&[N], DiGraphToposortError<N>>

Returns a topological ordering of the graph, computing it if the graph is dirty.

Errors

Returns DiGraphToposortError if the DAG is dirty and cannot be topologically sorted.

pub fn toposort_and_graph( &mut self, ) -> Result<(&[N], &Graph<true, N, S>), DiGraphToposortError<N>>

Returns both the topological ordering and the underlying graph, computing the toposort if the graph is dirty.

This function is useful to avoid multiple borrow issues when both the graph and the toposort are needed.

Errors

Returns DiGraphToposortError if the DAG is dirty and cannot be topologically sorted.

pub fn analyze(&mut self) -> Result<DagAnalysis<N, S>, DiGraphToposortError<N>>

where S: Default,

Processes a DAG and computes various properties about it.

See DagAnalysis::new for details on what is computed.

Note

If the DAG is dirty, this method will first attempt to topologically sort it.

Errors

Returns DiGraphToposortError if the DAG is dirty and cannot be topologically sorted.

pub fn remove_redundant_edges(&mut self, analysis: &DagAnalysis<N, S>)

where S: Clone,

Replaces the current graph with its transitive reduction based on the provided analysis.

Note

The given DagAnalysis must have been generated from this DAG.

pub fn group_by_key<K, V>( &mut self, num_groups: usize, ) -> Result<DagGroups<K, V, S>, DiGraphToposortError<N>>

where N: TryInto<K, Error = V>, K: Eq + Hash, V: Clone + Eq + Hash, S: BuildHasher + Default,

Groups nodes in this DAG by a key type K, collecting value nodes V under all of their ancestor key nodes. num_groups hints at the expected number of groups, for memory allocation optimization.

The node type N must be convertible into either a key type K or a value type V via the TryInto trait.

Errors

Returns DiGraphToposortError if the DAG is dirty and cannot be topologically sorted.

pub fn try_convert<T>(self) -> Result<Dag<T, S>, <N as TryInto<T>>::Error>

where N: TryInto<T>, T: GraphNodeId, S: Default,

Converts from one GraphNodeId type to another. If the conversion fails, it returns the error from the target type’s TryFrom implementation.

Nodes must uniquely convert from N to T (i.e. no two N can convert to the same T). The resulting DAG must be re-topologically sorted.

Errors

If the conversion fails, it returns an error of type N::Error.

Trait Implementations

impl<N, S> Clone for Dag<N, S>

where N: Clone + GraphNodeId, S: Clone + BuildHasher,

fn clone(&self) -> Dag<N, S>

Returns a duplicate of the value.

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

Performs copy-assignment from source.

impl<N, S> Debug for Dag<N, S>

where N: GraphNodeId, S: BuildHasher,

fn fmt(&self, f: &mut Formatter<'_>) -> Result<(), Error>

Formats the value using the given formatter.

impl<N, S> Default for Dag<N, S>

where N: GraphNodeId, S: BuildHasher + Default,

fn default() -> Dag<N, S>

Returns the “default value” for a type.

impl<N, S> Deref for Dag<N, S>

where N: GraphNodeId, S: BuildHasher,

type Target = Graph<true, N, S>

The resulting type after dereferencing.

fn deref(&self) -> &<Dag<N, S> as Deref>::Target

Dereferences the value.

impl<N, S> DerefMut for Dag<N, S>

where N: GraphNodeId, S: BuildHasher,

fn deref_mut(&mut self) -> &mut <Dag<N, S> as Deref>::Target

Mutably dereferences the value.