Crate daggy

daggy is a directed acyclic graph data structure library.

The most prominent type is Dag - a wrapper around petgraph’s Graph data structure, exposing a refined API targeted towards directed acyclic graph related functionality.

The Walker trait defines a variety of useful methods for traversing any graph type. Its methods behave similarly to iterator types, however Walkers do not require borrowing the graph. This means that we can still safely mutably borrow from the graph whilst we traverse it.

Usage

Use daggy in your project by adding it to your Cargo.toml dependencies:

[dependencies]
daggy = "0.9.0"

# Enables the `StableDag` type.
daggy = { version = "0.9.0", features = ["stable_dag"] }

# Allows the `Dag` to be serialized and deserialized.
daggy = { version = "0.9.0", features = ["serde-1"] }

Examples

Please see the tests directory for some basic usage examples.

Transitive reduction:

use daggy::Dag;

let mut dag = Dag::<&str, &str>::new();

// Reduce edges:
//
// ```text
// # Before:          | # After:
//                    |
// a -> b ----.       | a -> b ----.
//  |         |       |  |         |
//  |-> c ----|----.  |  '-> c     |
//  |    \    |    |  |       \    |
//  |     \   v    |  |        \   v
//  |------>> d    |  |         '> d
//  |          \   v  |             \
//  '----------->> e  |              '> e
// ```

let a = dag.add_node("a");

let (_, b) = dag.add_child(a, "a->b", "b");
let (_, c) = dag.add_child(a, "a->c", "c");
let (_, d) = dag.add_child(a, "a->d", "d");
let (_, e) = dag.add_child(a, "a->e", "e");

dag.add_edge(b, d, "b->d").unwrap();

dag.add_edge(c, d, "c->d").unwrap();
dag.add_edge(c, e, "c->e").unwrap();

dag.add_edge(d, e, "d->e").unwrap();

assert_eq!(dag.edge_count(), 8);

dag.transitive_reduce(vec![a]);

let mut edges = dag.graph().edge_weights().copied().collect::<Vec<_>>();
edges.sort();
assert_eq!(dag.edge_count(), 5);
assert_eq!(&edges, &["a->b", "a->c", "b->d", "c->d", "d->e"]);

Re-exports

pub use petgraph;

Modules

stable_dag

This module includes the implementation of the StableDag data structure. The StableDag has a similar functionality to the Dag data structure, but it does not invalidate node indices when a node is removed.

walker

Walker is a trait providing a variety of useful methods for traversing graph types.

Structs

Children

A Walker type that can be used to step through the children of some parent node.

Dag

A Directed acyclic graph (DAG) data structure.

EdgeIndex

Edge identifier.

EdgeIndices

An iterator yielding multiple EdgeIndexs, returned by the Graph::add_edges method.

EdgeWeightsMut

Iterator yielding mutable access to all edge weights.

NodeIndex

Node identifier.

NodeWeightsMut

Iterator yielding mutable access to all node weights.

Parents

A Walker type that can be used to step through the parents of some child node.

WouldCycle

An error returned by the Dag::add_edge method in the case that adding an edge would have caused the graph to cycle.

Traits

Walker

A walker is a traversal state, but where part of the traversal information is supplied manually to each next call.

Type Aliases

Edges

An iterator yielding all edges to/from some node.

RawEdges

Read only access into a Dag’s internal edge array.

RawNodes

Read only access into a Dag’s internal node array.

RecursiveWalk

An alias to simplify the Recursive Walker type returned by Dag.