Directed Acyclic Graphs (DAGs) represented as Strictly Upper Triangular matrices.

See crate docs for more information.

lib.rs:

Directed Acyclic Graphs (DAGs) represented as Strictly Upper Triangular matrices.

A create for working with DAGs where it is known upfront that graphs are directed and there are no cycles. This crate is not a good fit if you need to e.g. build a graph and check if there cycles in it. There are several assumptions imposed on your code:

1. DAG vertices are integer numbers (usize) which is used to trivially test whether adding an edge would form a cycle: edges are only allowed to go "forward", i.e. from u to v iff u < v. Otherwise we panic.
2. Vertices numbering starts at 0.
3. The number of vertices is determined at construction time and growing/shrinking generally requires a new graph to be constructed.

In exchange for these assumptions you get these useful properties:

• Correctness: It's not possible to have cycles by construction!
• Compactness: Edges are just bits in a bit set. The implementation uses just (|V|*|V|-|V|)/2 bits of memory + a constant.
• CPU cache locality: Edges are stored in a row-major packed representation so that iteration over the neighbours of a vertex is just an iteration over consecutive bits in a bit set.
• Low cognitive overhead: No need to deal with type-level shenenigans to get basic tasks done.
• Asymptotic complexity reduction: Generating a random DAG is a O(|E|) operation. That was actually the original motivation for writing this crate. It can be used with quickcheck efficiently. In fact, DirectedAcyclicGraph implements quickcheck::Arbitrary (with meaningful shrinking).

Anti-features

• No support for storing anything in the vertices.
• No support for assigning weights to either edges or vertices.
• No support for enumerating incoming edges of a vertex, only outgoing ones.
• No serde impls. Simply serialize/deserialize the list of edges with a library of your choosing.

Entry points

See either DirectedAcyclicGraph::empty, DirectedAcyclicGraph::from_edges_iter, or DirectedAcyclicGraph::from_adjacency_matrix for the "entry point" to this crate.