Struct rove::Dag

pub struct Dag<Elem: Ord + Hash> { /* private fields */ }

Directed acyclic graph representation

DAGs are used to define dependencies and pipelines between QC tests in ROVE. Each node in the DAG represents a QC test, and edges between nodes encode dependencies, where the parent node is dependent on the child node.

The generic parameter Elem represents the data held by a node in the graph. For most use cases we expect &'static str to work here. Strings containing test names seem a reasonable way to represent QC tests, and these strings can be reasonably expected to be known at compile time, hence 'static

The following code sample shows how to construct a DAG:

use rove::Dag;

let dag = {
    // create empty dag
    let mut dag: Dag<&'static str> = Dag::new();

    // add free-standing node
    let test6 = dag.add_node("test6");

    // add a node with a dependency on the previously defined node
    let test4 = dag.add_node_with_children("test4", vec![test6]);
    let test5 = dag.add_node_with_children("test5", vec![test6]);

    let test2 = dag.add_node_with_children("test2", vec![test4]);
    let test3 = dag.add_node_with_children("test3", vec![test5]);

    let _test1 = dag.add_node_with_children("test1", vec![test2, test3]);

    dag
};

// Resulting dag should look like:
//
//   6
//   ^
//  / \
// 4   5
// ^   ^
// |   |
// 2   3
// ^   ^
//  \ /
//   1

Implementations

impl<Elem: Ord + Hash + Clone> Dag<Elem>

pub fn new() -> Self

Create a new (empty) DAG

pub fn add_node(&mut self, elem: Elem) -> usize

Add a free-standing node to a DAG

pub fn add_edge(&mut self, parent: usize, child: usize)

Add an edge to the DAG. This defines a dependency, where the parent is dependent on the child

pub fn add_node_with_children( &mut self, elem: Elem, children: Vec<usize> ) -> usize

Add a node to the DAG, along with edges representing its dependencies (children)

pub fn transitive_reduce(&mut self)

Performs a transitive reduction on the DAG

This essentially removes any redundant dependencies in the graph

pub fn cycle_check(&self) -> bool

Check for cycles in the DAG

This can be used to validate a DAG, as a DAG must not contain cycles. Returns true if a cycle is detected, false otherwise.

Trait Implementations

impl<Elem: Clone + Ord + Hash> Clone for Dag<Elem>

fn clone(&self) -> Dag<Elem>

Returns a copy of the value.

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

Performs copy-assignment from source.

impl<Elem: Debug + Ord + Hash> Debug for Dag<Elem>

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

Formats the value using the given formatter.

impl<Elem: Ord + Hash + Clone> Default for Dag<Elem>

fn default() -> Self

Returns the “default value” for a type.