2 releases
0.8.4 | Mar 12, 2022 |
---|---|
0.8.3 | Feb 26, 2022 |
#16 in #vertices
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:
- 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. fromu
tov
iffu < v
. Otherwise we panic. - Vertices numbering starts at 0.
- 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
implementsquickcheck::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