cairo-lang-utils 2.18.0

//! Logic for computing the strongly connected component of a node in a graph.

use super::graph_node::GraphNode;
use crate::unordered_hash_map::UnorderedHashMap;

#[cfg(test)]
#[path = "strongly_connected_components_test.rs"]
mod strongly_connected_components_test;

/// A trait for a type that can compute its strongly-connected-component.
pub trait ComputeScc: GraphNode {
    fn compute_scc(&self) -> Vec<Self::NodeId>;
}

/// A wrapper node to a GraphNode, to be used in the SCC algorithm. Contains the GraphNode
/// additional state for the algorithm.
#[derive(Default, PartialEq, Eq, Hash, Clone)]
struct SccAlgoNode<Node: GraphNode> {
    /// The wrapped GraphNode.
    node: Node,
    /// The index of the node in the algorithm. The smaller the index, the earlier the node was
    /// reached.
    index: u32,
    /// The smallest index of a node that's reachable from this node (so far).
    lowlink: u32,
    /// Whether the node is currently on the DFS stack.
    on_stack: bool,
}

/// The context of the SCC algorithm.
struct SccAlgoContext<Node: GraphNode> {
    /// The next index to allocate to a first-seen node.
    next_index: u32,
    /// The stack of the nodes in the DFS.
    stack: Vec<Node::NodeId>,
    /// All visited nodes. If a graph node is not in the map, it hasn't yet been visited.
    known_nodes: UnorderedHashMap<Node::NodeId, SccAlgoNode<Node>>,
    /// The ID of the node we want to find the SCC of.
    target_node_id: Node::NodeId,
    /// The SCC of the `target_node_id`. Populated only at the end of the algorithm.
    result: Vec<Node::NodeId>,
}
impl<Node: GraphNode> SccAlgoContext<Node> {
    fn new(target_node_id: Node::NodeId) -> Self {
        SccAlgoContext::<Node> {
            next_index: 0,
            stack: Vec::new(),
            known_nodes: UnorderedHashMap::default(),
            target_node_id,
            result: Vec::new(),
        }
    }
}

/// Computes the SCC (Strongly Connected Component) of the given node in its graph.
pub fn compute_scc<Node: GraphNode>(root: &Node) -> Vec<Node::NodeId> {
    let mut ctx = SccAlgoContext::new(root.get_id());
    compute_scc_recursive(&mut ctx, root);
    ctx.result
}

/// The recursive call to compute the SCC of a given node.
fn compute_scc_recursive<Node: GraphNode>(ctx: &mut SccAlgoContext<Node>, current_node: &Node) {
    let mut current_lowlink = ctx.next_index;
    let current_node_id = current_node.get_id();
    ctx.known_nodes.insert(
        current_node_id.clone(),
        SccAlgoNode {
            node: current_node.clone(),
            index: ctx.next_index,
            lowlink: current_lowlink,
            on_stack: true,
        },
    );
    ctx.next_index += 1;
    ctx.stack.push(current_node_id.clone());

    let mut is_scc_root = true;
    for neighbor in current_node.get_neighbors() {
        let neighbor_id = neighbor.get_id();
        let lowlink_candidate = match ctx.known_nodes.get(&neighbor_id) {
            None => {
                // neighbor was not visited yet. Visit it and maybe apply its lowlink to root.
                compute_scc_recursive(ctx, &neighbor);
                // Now neighbor should be in known_nodes.
                ctx.known_nodes[&neighbor_id].lowlink
            }
            Some(neighbor_node) => {
                // If neighbor is known but not on stack, it's in a concluded dropped SCC.
                // Ignore it.
                if !neighbor_node.on_stack {
                    continue;
                }
                // This is a back edge, meaning neighbor is in current_node's SCC.
                neighbor_node.index
            }
        };
        if lowlink_candidate < current_lowlink {
            current_lowlink = lowlink_candidate;
            ctx.known_nodes.get_mut(&current_node_id).unwrap().lowlink = current_lowlink;
            is_scc_root = false;
        }
    }

    if !is_scc_root {
        // `current_node` is not a root of an SCC. We only conclude SCCs when we reach their roots.
        return;
    }

    // `current_node` is a root of an SCC. Conclude this SCC.
    // Push the nodes from the latest to earliest in the call hierarchy, so that the reverse of the
    // SCC vector would form a valid path on the graph.
    let mut scc = Vec::new();
    while let Some(other_node_id) = ctx.stack.pop() {
        let other_node = ctx.known_nodes.get_mut(&other_node_id).unwrap();
        other_node.on_stack = false;
        let is_root = other_node_id == current_node_id;
        scc.push(other_node_id);

        // Stop once the popped node is the current node which is the root of the SCC.
        if is_root {
            break;
        }
    }

    // If this SCC is the one we are looking for, update it in ctx. Otherwise, throw this
    // SCC away.
    if current_node_id == ctx.target_node_id {
        ctx.result = scc;
    }
}