4 releases (2 breaking)
0.3.0 | Oct 21, 2024 |
---|---|
0.2.1 | Dec 28, 2023 |
0.2.0 | Nov 27, 2023 |
0.1.0 | Oct 9, 2023 |
#209 in Data structures
73,255 downloads per month
Used in 26 crates
(2 directly)
24KB
410 lines
prio-graph
A library for building a directed acyclic graph that is lazily evaluated as new transactions are added. Edges are only present for the next-highest priority conflict for a particular resource,.
The PrioGraph
structure keeps track of the nodes in the graph, the directed
edges between them, and a main queue. For example:
graph LR;
A((A)) --> B((B)) --> C((C)) & D((D));
E((E)) --> F((F));
A
and E
have no conflicts and are the highest priority items within their
prospective chains. These node's associated ids would be in the main queue.
If a transaction were added that conflicts with both chains, then these chains
would be joined.
graph LR;
A((A)) --> B((B)) --> C((C)) & D((D)) --> G((G));
E((E)) --> F((F)) --> G;
Dependencies
~0.7–1MB
~13K SLoC