pub fn lexicographical_topological_sort<F>(
        graph: &BTreeMap<EventId, BTreeSet<EventId>>,
        key_fn: F,
    ) -> Vec<EventId>
    where
        F: Fn(&EventId) -> (i64, MilliSecondsSinceUnixEpoch, EventId),
    {
        info!("starting lexicographical topological sort");
        // NOTE: an event that has no incoming edges happened most recently,
        // and an event that has no outgoing edges happened least recently.

        // NOTE: this is basically Kahn's algorithm except we look at nodes with no
        // outgoing edges, c.f.
        // https://en.wikipedia.org/wiki/Topological_sorting#Kahn's_algorithm

        // TODO make the BTreeSet conversion cleaner ??
        // outdegree_map is an event referring to the events before it, the
        // more outdegree's the more recent the event.
        let mut outdegree_map = graph.clone();

        // The number of events that depend on the given event (the eventId key)
        let mut reverse_graph = BTreeMap::new();

        // Vec of nodes that have zero out degree, least recent events.
        let mut zero_outdegree = vec![];

        for (node, edges) in graph.iter() {
            if edges.is_empty() {
                // The `Reverse` is because rusts `BinaryHeap` sorts largest -> smallest we need
                // smallest -> largest
                zero_outdegree.push(Reverse((key_fn(node), node)));
            }

            reverse_graph.entry(node).or_insert(btreeset![]);
            for edge in edges {
                reverse_graph.entry(edge).or_insert(btreeset![]).insert(node);
            }
        }

        let mut heap = BinaryHeap::from(zero_outdegree);

        // We remove the oldest node (most incoming edges) and check against all other
        let mut sorted = vec![];
        // Destructure the `Reverse` and take the smallest `node` each time
        while let Some(Reverse((_, node))) = heap.pop() {
            let node: &EventId = node;
            for parent in reverse_graph.get(node).unwrap() {
                // The number of outgoing edges this node has
                let out = outdegree_map.get_mut(parent).unwrap();

                // Only push on the heap once older events have been cleared
                out.remove(node);
                if out.is_empty() {
                    heap.push(Reverse((key_fn(parent), parent)));
                }
            }

            // synapse yields we push then return the vec
            sorted.push(node.clone());
        }

        sorted
    }
/// Sorts the event graph based on number of outgoing/incoming edges, where
/// `key_fn` is used as a tie breaker. The tie breaker happens based on
/// power level, age, and event_id.
Sorts the event graph based on number of outgoing/incoming edges, where
`key_fn` is used as a tie breaker. The tie breaker happens based on
power level, age, and event_id.
Sorts the event graph based on number of outgoing / incoming edges where ` key_fn ` is used as a tie breaker . The tie breaker happens based on power level age and event_id .
pub fn lexicographical_topological_sort<F>(
        graph: &BTreeMap<EventId, BTreeSet<EventId>>,
        key_fn: F,
    ) -> Vec<EventId>
    where
        F: Fn(&EventId) -> (i64, MilliSecondsSinceUnixEpoch, EventId),
    {
        info!("starting lexicographical topological sort");
        // NOTE: an event that has no incoming edges happened most recently,
        // and an event that has no outgoing edges happened least recently.
        // NOTE: this is basically Kahn's algorithm except we look at nodes with no
        // outgoing edges, c.f.
        // https://en.wikipedia.org/wiki/Topological_sorting#Kahn's_algorithm
        // TODO make the BTreeSet conversion cleaner ??
        // outdegree_map is an event referring to the events before it, the
        // more outdegree's the more recent the event.
        let mut outdegree_map = graph.clone();
        // The number of events that depend on the given event (the eventId key)
        let mut reverse_graph = BTreeMap::new();
        // Vec of nodes that have zero out degree, least recent events.
        let mut zero_outdegree = vec![];
        for (node, edges) in graph.iter() {
            if edges.is_empty() {
                // The `Reverse` is because rusts `BinaryHeap` sorts largest -> smallest we need
                // smallest -> largest
                zero_outdegree.push(Reverse((key_fn(node), node)));
            }
            reverse_graph.entry(node).or_insert(btreeset![]);
            for edge in edges {
                reverse_graph.entry(edge).or_insert(btreeset![]).insert(node);
            }
        }
        let mut heap = BinaryHeap::from(zero_outdegree);
        // We remove the oldest node (most incoming edges) and check against all other
        let mut sorted = vec![];
        // Destructure the `Reverse` and take the smallest `node` each time
        while let Some(Reverse((_, node))) = heap.pop() {
            let node: &EventId = node;
            for parent in reverse_graph.get(node).unwrap() {
                // The number of outgoing edges this node has
                let out = outdegree_map.get_mut(parent).unwrap();
                // Only push on the heap once older events have been cleared
                out.remove(node);
                if out.is_empty() {
                    heap.push(Reverse((key_fn(parent), parent)));
                }
            }
            // synapse yields we push then return the vec
            sorted.push(node.clone());
        }
        sorted
    }
pub fn lexicographical_topological_sort < F > ( graph : & BTreeMap < EventId , BTreeSet < EventId > > , key_fn : F , ) -> Vec < EventId > where F : Fn ( & EventId ) -> ( i64 , MilliSecondsSinceUnixEpoch , EventId ) , { info ! ( " " ) ; // NOTE: an event that has no incoming edges happened most recently, // and an event that has no outgoing edges happened least recently. // NOTE: this is basically Kahn's algorithm except we look at nodes with no // outgoing edges, c.f. // https://en.wikipedia.org/wiki/Topological_sorting#Kahn's_algorithm // TODO make the BTreeSet conversion cleaner ?? // outdegree_map is an event referring to the events before it, the // more outdegree's the more recent the event. let mut outdegree_map = graph . clone ( ) ; // The number of events that depend on the given event (the eventId key) let mut reverse_graph = BTreeMap :: new ( ) ; // Vec of nodes that have zero out degree, least recent events. let mut zero_outdegree = vec ! [ ] ; for ( node , edges ) in graph . iter ( ) { if edges . is_empty ( ) { // The `Reverse` is because rusts `BinaryHeap` sorts largest -> smallest we need // smallest -> largest zero_outdegree . push ( Reverse ( ( key_fn ( node ) , node ) ) ) ; } reverse_graph . entry ( node ) . or_insert ( btreeset ! [ ] ) ; for edge in edges { reverse_graph . entry ( edge ) . or_insert ( btreeset ! [ ] ) . insert ( node ) ; } } let mut heap = BinaryHeap :: from ( zero_outdegree ) ; // We remove the oldest node (most incoming edges) and check against all other let mut sorted = vec ! [ ] ; // Destructure the `Reverse` and take the smallest `node` each time while let Some ( Reverse ( ( _ , node ) ) ) = heap . pop ( ) { let node : & EventId = node ; for parent in reverse_graph . get ( node ) . unwrap ( ) { // The number of outgoing edges this node has let out = outdegree_map . get_mut ( parent ) . unwrap ( ) ; // Only push on the heap once older events have been cleared out . remove ( node ) ; if out . is_empty ( ) { heap . push ( Reverse ( ( key_fn ( parent ) , parent ) ) ) ; } } // synapse yields we push then return the vec sorted . push ( node . clone ( ) ) ; } sorted }
Sorts the event graph based on number of outgoing/incoming edges, where
`key_fn` is used as a tie breaker.
Sorts the event graph based on number of outgoing / incoming edges where ` key_fn ` is used as a tie breaker .
graph
&BTreeMap<EventId, BTreeSet<EventId>>
key_fn
F