clm-kernel 0.0.16

Cubical Logic Model (CLM) sovereign execution engine, CPN-VM, and Cordis spatiotemporal substrate
Documentation
//! Tarjan's strongly connected components algorithm for Petri net place condensation.

use std::collections::{BTreeMap, BTreeSet};

/// Computes Tarjan's Strongly Connected Components in deterministic topological order.
pub fn tarjan_scc(nodes: &[String], adj: &BTreeMap<String, BTreeSet<String>>) -> Vec<Vec<String>> {
    struct TarjanState<'a> {
        index: usize,
        indices: BTreeMap<String, usize>,
        lowlink: BTreeMap<String, usize>,
        stack: Vec<String>,
        on_stack: BTreeSet<String>,
        sccs: Vec<Vec<String>>,
        adj: &'a BTreeMap<String, BTreeSet<String>>,
    }
    fn strongconnect(v: &str, st: &mut TarjanState<'_>) {
        let cur = st.index;
        st.indices.insert(v.to_string(), cur);
        st.lowlink.insert(v.to_string(), cur);
        st.index += 1;
        st.stack.push(v.to_string());
        st.on_stack.insert(v.to_string());
        if let Some(nbrs) = st.adj.get(v) {
            for w in nbrs {
                if !st.indices.contains_key(w) {
                    strongconnect(w, st);
                    let (lw, lv) = (st.lowlink[w], st.lowlink[v]);
                    if lw < lv { st.lowlink.insert(v.to_string(), lw); }
                } else if st.on_stack.contains(w) {
                    let (iw, lv) = (st.indices[w], st.lowlink[v]);
                    if iw < lv { st.lowlink.insert(v.to_string(), iw); }
                }
            }
        }
        if st.lowlink[v] == st.indices[v] {
            let mut comp = Vec::new();
            while let Some(w) = st.stack.pop() {
                st.on_stack.remove(&w);
                let done = w == v;
                comp.push(w);
                if done { break; }
            }
            comp.sort();
            st.sccs.push(comp);
        }
    }
    let mut sorted_nodes = nodes.to_vec();
    sorted_nodes.sort();
    let mut state = TarjanState {
        index: 0, indices: BTreeMap::new(), lowlink: BTreeMap::new(),
        stack: Vec::new(), on_stack: BTreeSet::new(), sccs: Vec::new(), adj,
    };
    for n in &sorted_nodes {
        if !state.indices.contains_key(n) { strongconnect(n, &mut state); }
    }
    state.sccs.reverse();
    state.sccs
}