#directed-acyclic-graph #directed-graph #priority #priority-queue #transaction #node #conflict

prio-graph

A lazily populated directed acyclic graph with top-level priority ordering

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

#190 in Data structures

Download history 14452/week @ 2024-07-17 16543/week @ 2024-07-24 15189/week @ 2024-07-31 15946/week @ 2024-08-07 14393/week @ 2024-08-14 14726/week @ 2024-08-21 13337/week @ 2024-08-28 15390/week @ 2024-09-04 10065/week @ 2024-09-11 5720/week @ 2024-09-18 12894/week @ 2024-09-25 13396/week @ 2024-10-02 14978/week @ 2024-10-09 16678/week @ 2024-10-16 18503/week @ 2024-10-23 17745/week @ 2024-10-30

70,334 downloads per month
Used in 26 crates (2 directly)

Custom license

24KB
410 lines

prio-graph example workflow

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