| Crates.io | prio-graph |
| lib.rs | prio-graph |
| version | 0.3.0 |
| created_at | 2023-10-09 20:11:22.74898+00 |
| updated_at | 2024-10-21 22:22:58.959443+00 |
| 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,192 |
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;