#directed-acyclic-graph #graph #dag #bit-set #matrix #vertices #edge

dograph

Directed Acyclic Graphs with integer vertices represented as a Strictly Upper Triangular Matrix stored in a bit set

2 releases

0.8.4 Mar 12, 2022
0.8.3 Feb 26, 2022

#15 in #vertices

GPL-3.0 license

38KB
836 lines

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 (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.

Dependencies

~1.5MB
~28K SLoC