0.8.3 |
|
---|---|
0.7.0 |
|
#19 in #vertices
39KB
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 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:
- 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: 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
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