ruma_state_res

Function reverse_topological_power_sort

Source 
pub fn reverse_topological_power_sort<Id, F>(
    graph: &HashMap<Id, HashSet<Id>>,
    event_details_fn: F,
) -> Result<Vec<Id>>
where
    F: Fn(&EventId) -> Result<(Int, MilliSecondsSinceUnixEpoch)>,
    Id: Clone + Eq + Ord + Hash + Borrow<EventId>,
Expand description

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 auth events. The reverse topological power ordering is ordered from earliest event to latest. For comparing two 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 auth_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.

§Arguments

  • graph - The graph to sort. A map of event ID to its auth events that are in the full conflicted set.

  • event_details_fn - Function to obtain a (power level, origin_server_ts) of an event for breaking ties.

§Returns

Returns the ordered list of event IDs from earliest to latest.