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

kahn_sort 🔒

topological_sort

Sorts the given event graph using reverse topological power ordering.

Type Aliases

PduInfo 🔒

ReferencedIds