Module topological_sort 

Sorts the given event graph using reverse topological power ordering.

Definition in the specification:

The reverse topological power ordering of a set of events is the lexicographically smallest topological ordering based on the DAG formed by referenced events (prev or auth, determined by caller). The reverse topological power ordering is ordered from earliest event to latest. For comparing two equal topological orderings to determine which is the lexicographically smallest, the following comparison relation on events is used: for events x and y, x < y if

1. x’s sender has greater power level than y’s sender, when looking at their respective referenced events; or
2. the senders have the same power level, but x’s origin_server_ts is less than y’s origin_server_ts; or
3. the senders have the same power level and the events have the same origin_server_ts, but x’s event_id is less than y’s event_id.

The reverse topological power ordering can be found by sorting the events using Kahn’s algorithm for topological sorting, and at each step selecting, among all the candidate vertices, the smallest vertex using the above comparison relation.

Structs

TieBreaker 🔒

Functions

is_topologically_sorted

Tests whether the events in order are in reverse topological power ordering with respect to graph: each event appears after every event it references that is present in graph.

is_topologically_sorted_in_place

Whether items are already in reverse topological order, reading each item’s references in place instead of from a prebuilt graph. An item must follow every item it references that is also present among items; a reference to an absent item is a non-edge. id reads an item’s identifier, references its outgoing references.

kahn_sort 🔒

topological_sort

Sorts the given event graph using reverse topological power ordering.

Type Aliases

PduInfo 🔒

ReferencedIds