prio-graph

Crates.ioprio-graph
lib.rsprio-graph
version0.3.0
sourcesrc
created_at2023-10-09 20:11:22.74898
updated_at2024-10-21 22:22:58.959443
descriptionA lazily populated directed acyclic graph with top-level priority ordering
homepagehttps://github.com/apfitzge/prio-graph
repositoryhttps://github.com/apfitzge/prio-graph
max_upload_size
id998432
size24,192
Andrew Fitzgerald (apfitzge)

documentation

README

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;
Commit count: 87

cargo fmt