Crate dep_graph

Library to perform operations over dependency graphs.

This library allow running iterative operations over a dependency graph in the correct evaluation order, or will fail if there are a circular dependencies.

To use this library, you create a list of Nodes containing dependency information (which node depends on which). You then create a DepGraph which will allow you to traverse the graph so that you will always get an item for which all dependencies have been processed.

Processing order

DepGraphs have two methods: one for sequential operations and one for parallel (multi-threaded) operations. In the first case, it's easy to know in which order nodes can be processed, as only one node will be processed at a time. However, in parallel operations, we need to know if a given node is done processing.

This leads to a situation where a given worker thread might not be able to pull a node temporarily, as it needs to wait for another worker to finish processing another node.

Let's look at the following case:

(A) <-|
      |-- [E] <-|-- [G]
(B) <-|         |
      |-- [F] <-|-- [H]
[C] <-|

In this case, the nodes E and F are dependent on A, B and C and G and H are dependent on both E and F. If we process the nodes with two workers, they might pick up nodes A and B first. Since these nodes don't have any dependencies, there is no problem right now.

[ ] <-|
      |-- [E] <-|-- [G]
[ ] <-|         |
      |-- [F] <-|-- [H]
(C) <-|

When one of the worker is done, it can immediately start working on node C, as it does not have any dependencies. However, when the second worker is done, there are no available nodes for processing: we need to wait until C is processed before we can start working on E or F. One of the worker will then stay idle until the other one is done.

[ ] <-|
      |-- (E) <-|-- [G]
[ ] <-|         |
      |-- (F) <-|-- [H]
[ ] <-|

Once that is done, both workers can work on E and F. However, if E takes only a fraction of the time compared to F, we will end up in the same situation, as there are no nodes without un-processed dependencies.

Parallel iterators

This library supports using rayon as an optional dependency. When using rayon, DepGraph supports a new method into_par_iter() that will process the dependency graph across multiple threads.

Under the hood, it works by creating a dispatcher thread and a series of crossbeam channels to dispatch nodes and notify the dispatcher when nodes are done processing.

Because of that, iterator functions receive a Wrapper instead of the item itself. The underlying item is available by using the dereference operator (*wrapper).

Basic usage

use dep_graph::{Node, DepGraph};
#[cfg(feature = "parallel")]
use rayon::prelude::*;

// Create a list of nodes
let mut root = Node::new("root");
let mut dep1 = Node::new("dep1");
let mut dep2 = Node::new("dep2");
let leaf = Node::new("leaf");

// Map their connections
root.add_dep(dep1.id());
root.add_dep(dep2.id());
dep1.add_dep(leaf.id());
dep2.add_dep(leaf.id());

// Create a graph
let nodes = vec![root, dep1, dep2, leaf];

// Print the name of all nodes in the dependency graph.
// This will parse the dependency graph sequentially
{
    let graph = DepGraph::new(&nodes);
    graph
        .into_iter()
        .for_each(|node| {
            println!("{:?}", node)
        });
}

// This is the same as the previous command, excepts it leverages rayon
// to process them in parallel as much as possible.
#[cfg(feature = "parallel")]
{
    let graph = DepGraph::new(&nodes);
    graph
        .into_par_iter()
        .for_each(|node| {
            // The node is a dep_graph::Wrapper object, not a String.
            // We need to use `*node` to get its value.
            println!("{:?}", *node)
        });
}

Modules

error

Structs

DepGraph	Dependency graph
Node	Single node in a dependency graph, which might have dependencies or be be used as a dependency by other nodes.
Wrapper	Wrapper for an item