Crates.io | prio-graph |
lib.rs | prio-graph |
version | 0.2.1 |
source | src |
created_at | 2023-10-09 20:11:22.74898 |
updated_at | 2023-12-28 18:00:19.448169 |
description | A lazily populated directed acyclic graph with top-level priority ordering |
homepage | https://github.com/apfitzge/prio-graph |
repository | https://github.com/apfitzge/prio-graph |
max_upload_size | |
id | 998432 |
size | 24,851 |
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, with the caveat that insertion order takes precedence over priority.
The PrioGraph
structure keeps track of the nodes in the graph, the directed edges between them, a main queue, and
mappings for distinct "chains" of transaction. 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, and would have different chain ids.
If a transaction were added that conflicts with both chains, then these chains would be joined, and a mapping of joined
chains is tracked in the PrioGraph
.
graph LR;
A((A)) --> B((B)) --> C((C)) & D((D)) --> G((G));
E((E)) --> F((F)) --> G;