Crate dograph

source · [−]
Expand description

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

A create for working with DAGs where it is known upfront (i.e. statically) that graphs are directed and there are no cycles. 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: Cycles (an illegal state) are unrepresentable.
  • 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.

Modules

algorithm
traversal

Structs

DirectedAcyclicGraph

A mutable, single-threaded directed acyclic graph.

StrictlyUpperTriangularLogicalMatrix

A zero-indexed row-major packed matrix of booleans.

Functions

break_at

Break a DAG into two halves at the vertex vertex. Used as a shrinking strategy for DAGs in the quickcheck::Arbitrary impl.

to_dot

Outputs the DAG in the Graphviz DOT format.