Function topo_sort

fendermint/testing/materializer/src/testnet.rs:661–710

Sort some values in a topological order. Cycles can be allowed, in which case it will do its best to order the items with the least amount of dependencies first. This is so we can support nodes mutually be seeded by each other.

(
    items: &BTreeMap<K, V>,
    allow_cycles: bool,
    f: F,
)

/// with the least amount of dependencies first. This is so we can support nodes
/// mutually be seeded by each other.
fn topo_sort<K, V, F, I>(
    items: &BTreeMap<K, V>,
    allow_cycles: bool,
    f: F,
) -> anyhow::Result<Vec<(&K, &V)>>
where
    F: Fn(&V) -> I,
    K: Ord + Display + Clone,
    I: IntoIterator<Item = K>,
{
    let mut deps = items
        .iter()
        .map(|(k, v)| (k, BTreeSet::from_iter(f(v))))
        .collect::<BTreeMap<_, _>>();

    for (k, ds) in deps.iter() {
        for d in ds {
            if !deps.contains_key(d) {
                bail!("non-existing dependency: {d} <- {k}")
            }
        }
    }

    let mut sorted = Vec::new();

    while !deps.is_empty() {
        let leaf: K = match deps.iter().find(|(_, ds)| ds.is_empty()) {
            Some((leaf, _)) => (*leaf).clone(),
            None if allow_cycles => {
                let mut dcs = deps.iter().map(|(k, ds)| (k, ds.len())).collect::<Vec<_>>();
                dcs.sort_by_key(|(_, c)| *c);
                let leaf = dcs.first().unwrap().0;
                (*leaf).clone()
            }
            None => bail!("circular reference in dependencies"),
        };

        deps.remove(&leaf);

        for (_, ds) in deps.iter_mut() {
            ds.remove(&leaf);
        }

        if let Some(kv) = items.get_key_value(&leaf) {
            sorted.push(kv);
        }
    }

    Ok(sorted)
}

/// Sort nodes in a subnet in topological order, so we strive to first
/// start the ones others use as a seed node. However, do allow cycles