mapgraph 0.12.0

//! Contains an implementation of the Tarjan's SCC algorithm.
//!
//! This algorithm expects the graph to be connected. In case the graph is disjoint, only nodes belonging to the same
//! component as the start node will be marked.
//!
//! # Marking SCCs
//!
//! Strongly-Connected Components are represented by user-provided types. The implementation interacts with the types
//! using the [`Scc`] and [`WithScc`] traits.
//!
//! The [`Scc`] trait should be implemented by the type representing an SCC. The type is expected to be easily clonable
//! and the only required method is `with_entry` that constructs the type from an index of an arbitrary node belonging
//! to the SCC. See docs for the [`Scc`] trait for more information.
//!
//! The [`WithScc`] trait is used to actually mark graph nodes with an SCC. It should be implemented on the graph's node
//! weight type.
//!
//! This design allows to only reserve place for information about SCCs in graphs that actually use this algorithm.
//!
//! # Secondary maps
//!
//! The algorithm expects a secondary map that maps node indices to tuples containing two `u32`
//! values to be provided as its last argument. This is only useful when you have strict performance
//! requirements. When in doubt you should use a [`HashMap`] or a [`BTreeMap`]. In some cases,
//! however, it might affect performance of the  algorithm, especially for large graphs. If this is
//! your case, continue reading.
//!
//! Choosing a map is a concern mostly for graphs based on [`SlotMap`]-like node maps which provide
//! secondary maps that can be accessed faster than [`HashMap`]s. These maps are backed by vectors
//! so the usage of memory will be inefficient when you only visit a small number of node slots:
//!
//! 1. When the node slots are densely located but the component the start node belongs to happens
//!    to be a small part of the graph;
//! 2. When the node slots are located sparsely.
//!
//! Otherwise using these secondary maps is OK and will give you a performance boost when compared
//! to other kinds of maps.
//!
//! [`HashMap`]: std::collections::HashMap
//! [`BTreeMap`]: std::collections::BTreeMap
//! [`SlotMap`]: slotmap::SlotMap

use crate::{
    graph::{iter::Walker, Edge, Node},
    map::{ExtKeyMap, IntKeyMap, Map},
    FrozenGraph,
};
use alloc::vec::Vec;
use core::{cmp, fmt::Debug, marker::PhantomData};

/// A trait for a type that represents a strongly-connected component of a graph.
///
/// # Requirements
///
/// It is expected that two instances of a type implementing this trait that are produced by a call
/// to the [`Scc::with_entry`] method and exist at the same time are never equal. An instance
/// produced by cloning another instance should always be equal to the original instance. This may
/// be easily achieved by wrapping an `Rc` or an `Arc` with a newtype and implementing `PartialEq`
/// using their `ptr_eq` methods.
///
/// Violating these requirements won't cause UB or even affect the implementation of the Tarjan's
/// SCC algorithm, but will probably break your own code.
pub trait Scc<I>: Clone + Eq {
    /// Constructs the type representing an SCC with an index of a node that belongs to this SCC.
    ///
    /// Which exact node is specified isn't important since any other node in the SCC can be found
    /// with a DFS pass starting from any other node.
    fn with_entry(entry: I) -> Self;
}

/// A trait for a node weight that stores information about the SCC it belongs to.
pub trait WithScc<I> {
    /// The type that represents a strongly-connected component.
    type Ty: Scc<I>;

    /// Returns a reference to the SCC the node belongs to.
    fn scc(&self) -> Option<&Self::Ty>;

    /// Sets the SCC of the weight.
    fn set_scc(&mut self, scc: Self::Ty);
}

struct State<NI, E, EF>
where
    EF: for<'a> FnMut(&'a E) -> bool,
{
    stack: Vec<NI>,
    index: u32,
    edge_filter: EF,
    _marker: PhantomData<E>,
}

fn recurse<N, E, NI, EI, NM, EM, SM, EF>(
    graph: &mut FrozenGraph<N, E, NI, EI, NM, EM>,
    block: NI,
    indices: &mut SM,
    state: &mut State<NI, E, EF>,
) -> (u32, u32)
where
    N: WithScc<NI>,
    NI: Copy + Eq + Debug + 'static,
    EI: Copy + Eq + Debug + 'static,
    NM: Map<Node<N, EI>, Key = NI>,
    EM: IntKeyMap<Edge<E, NI, EI>, Key = EI>,
    SM: ExtKeyMap<(u32, u32), Key = NI>,
    EF: FnMut(&E) -> bool,
{
    let cur_index = state.index;
    let mut low_link = cur_index;
    state.index = cur_index + 1;

    // Indices shouldn't be set when this function is called.
    indices
        .try_insert(block, (cur_index, low_link))
        .expect("index for block shouldn't be set");
    state.stack.push(block);

    let mut walker = graph.walk_outputs(block);
    while let Some((_, edge)) = walker.walk_next(graph) {
        if !(state.edge_filter)(edge.weight()) {
            continue;
        }

        let succ = edge.to();
        match indices.get(succ) {
            None => {
                let (_, succ_low_link) = recurse(graph, succ, indices, state);
                low_link = cmp::min(low_link, succ_low_link);

                if let Some((_, v)) = indices.get_mut(block) {
                    *v = low_link;
                }
            }
            Some(&(succ_index, _)) if state.stack.contains(&succ) => {
                low_link = cmp::min(low_link, succ_index);

                if let Some((_, v)) = indices.get_mut(block) {
                    *v = low_link;
                }
            }
            _ => (),
        }
    }

    if low_link == cur_index {
        let mut cur_block_opt = state.stack.pop();

        // Entry isn't really required to even be a point where the loop is entered. This is any
        // valid block belonging to a loop so use the one we already have
        if let Some(entry) = cur_block_opt {
            // Do not create a loop for an scc subgraph consisting of one node that isn't connected
            // to itself.
            if entry != block
                || graph
                    .successors(entry)
                    .any(|(succ_idx, _)| succ_idx == entry)
            {
                let scc = N::Ty::with_entry(entry);
                while let Some(cur_block) = cur_block_opt {
                    graph
                        .node_weight_mut(cur_block)
                        .expect("invalid node index in stack")
                        .set_scc(scc.clone());

                    if cur_block == block {
                        break;
                    }

                    cur_block_opt = state.stack.pop();
                }
            }
        }
    }

    (cur_index, low_link)
}

/// Runs Tarjan's SCC detection algorithm on a graph and marks weights with SCCs they belong to.
pub fn mark_sccs<N, E, NI, EI, NM, EM, SM>(
    graph: &mut FrozenGraph<N, E, NI, EI, NM, EM>,
    start_node_index: NI,
    secondary_map: &mut SM,
) where
    N: WithScc<NI>,
    NI: Copy + Eq + Debug + 'static,
    EI: Copy + Eq + Debug + 'static,
    NM: Map<Node<N, EI>, Key = NI>,
    EM: IntKeyMap<Edge<E, NI, EI>, Key = EI>,
    SM: ExtKeyMap<(u32, u32), Key = NI>,
{
    let mut state = State {
        stack: Vec::new(),
        index: 0,
        edge_filter: |_| true,
        _marker: PhantomData,
    };

    secondary_map.clear();

    recurse(graph, start_node_index, secondary_map, &mut state);
}

/// Runs Tarjan's SCC detection algorithm on a graph while ignoring certain edges and marks weights with SCCs they
/// belong to.
pub fn mark_sccs_with_filter<N, E, NI, EI, NM, EM, SM, EF>(
    graph: &mut FrozenGraph<N, E, NI, EI, NM, EM>,
    start_node_index: NI,
    secondary_map: &mut SM,
    edge_filter: EF,
) where
    N: WithScc<NI>,
    NI: Copy + Eq + Debug + 'static,
    EI: Copy + Eq + Debug + 'static,
    NM: Map<Node<N, EI>, Key = NI>,
    EM: IntKeyMap<Edge<E, NI, EI>, Key = EI>,
    SM: ExtKeyMap<(u32, u32), Key = NI>,
    EF: FnMut(&E) -> bool,
{
    let mut state = State {
        stack: Vec::new(),
        index: 0,
        edge_filter,
        _marker: PhantomData,
    };

    secondary_map.clear();

    recurse(graph, start_node_index, secondary_map, &mut state);
}

#[cfg(all(test, feature = "slotmap"))]
mod tests {
    use super::*;
    use crate::{
        aliases::{SecondarySlotMap, SlotMapGraph},
        map::slotmap::NodeIndex,
    };
    use alloc::rc::Rc;

    #[derive(Clone, Eq, Debug)]
    struct TestScc(Rc<NodeIndex>);

    impl PartialEq for TestScc {
        fn eq(&self, other: &Self) -> bool {
            Rc::ptr_eq(&self.0, &other.0)
        }
    }

    impl Scc<NodeIndex> for TestScc {
        fn with_entry(entry: NodeIndex) -> Self {
            Self(Rc::new(entry))
        }
    }

    #[derive(Default, Debug)]
    struct TestNodeWeight(Option<TestScc>);

    impl WithScc<NodeIndex> for TestNodeWeight {
        type Ty = TestScc;

        fn scc(&self) -> Option<&Self::Ty> {
            self.0.as_ref()
        }

        fn set_scc(&mut self, scc: Self::Ty) {
            self.0 = Some(scc);
        }
    }

    #[test]
    fn test_simple_loop() {
        let mut graph = SlotMapGraph::<TestNodeWeight, ()>::default();

        let entry_node = graph.add_default_node();
        let node1 = graph.add_default_node();
        let node2 = graph.add_default_node();
        let exit_node = graph.add_default_node();

        graph.add_edge((), entry_node, node1).unwrap();
        graph.add_edge((), node1, node2).unwrap();
        graph.add_edge((), node2, exit_node).unwrap();
        graph.add_edge((), node2, entry_node).unwrap();

        let mut secondary_map = SecondarySlotMap::default();
        mark_sccs(&mut graph, entry_node, &mut secondary_map);

        let scc = graph.node_weight(entry_node).unwrap().scc().unwrap();
        assert_eq!(scc, graph.node_weight(node1).unwrap().scc().unwrap());
        assert_eq!(scc, graph.node_weight(node2).unwrap().scc().unwrap());
        assert!(graph.node_weight(exit_node).unwrap().scc().is_none());
    }

    #[test]
    fn test_two_loops() {
        // This test creates two identical two-block loops and checks if the loop detector is able
        // to detect these correctly. The graph looks roughly as follows:
        //
        //            < entry >
        //      |---------|---------|
        //     \|/                 \|/
        //   < L1 > <-         -> < R1 >
        //      |    |         |    |
        //   < L2 > -|         |- < R2 >
        //      |                   |
        //      |----> < exit > <---|

        let mut graph = SlotMapGraph::<TestNodeWeight, ()>::default();
        let entry_node = graph.add_default_node();
        let left_node1 = graph.add_default_node();
        let left_node2 = graph.add_default_node();
        let right_node1 = graph.add_default_node();
        let right_node2 = graph.add_default_node();
        let exit_node = graph.add_default_node();

        graph.add_edge((), entry_node, left_node1).unwrap();
        graph.add_edge((), left_node1, left_node2).unwrap();
        graph.add_edge((), left_node2, left_node1).unwrap();
        graph.add_edge((), left_node2, exit_node).unwrap();

        graph.add_edge((), entry_node, right_node1).unwrap();
        graph.add_edge((), right_node1, right_node2).unwrap();
        graph.add_edge((), right_node2, right_node1).unwrap();
        graph.add_edge((), right_node2, exit_node).unwrap();

        let mut secondary_map = SecondarySlotMap::default();
        mark_sccs(&mut graph, entry_node, &mut secondary_map);

        let left_scc = graph.node_weight(left_node1).unwrap().scc().unwrap();
        let right_scc = graph.node_weight(right_node1).unwrap().scc().unwrap();

        assert!(graph.node_weight(exit_node).unwrap().scc().is_none());
        assert_eq!(
            left_scc,
            graph.node_weight(left_node2).unwrap().scc().unwrap()
        );
        assert_eq!(
            right_scc,
            graph.node_weight(right_node2).unwrap().scc().unwrap()
        );
        assert_ne!(left_scc, right_scc);
        assert!(graph.node_weight(exit_node).unwrap().scc().is_none());
    }

    /// Constructs a simple irreducible graph and tests whether loop detector can handle this.
    #[test]
    fn test_irreducible() {
        let mut graph = SlotMapGraph::<TestNodeWeight, ()>::default();
        let entry_node = graph.add_default_node();
        let cond_node = graph.add_default_node();
        let node1 = graph.add_default_node();
        let node2 = graph.add_default_node();
        let node3 = graph.add_default_node();

        graph.add_edge((), entry_node, cond_node).unwrap();
        graph.add_edge((), cond_node, node1).unwrap();
        graph.add_edge((), cond_node, node2).unwrap();
        graph.add_edge((), node1, node2).unwrap();
        graph.add_edge((), node2, node3).unwrap();
        graph.add_edge((), node3, node1).unwrap();

        let mut secondary_map = SecondarySlotMap::default();
        mark_sccs(&mut graph, entry_node, &mut secondary_map);

        let scc = graph.node_weight(node1).unwrap().scc().unwrap();

        assert!(graph.node_weight(entry_node).unwrap().scc().is_none());
        assert!(graph.node_weight(cond_node).unwrap().scc().is_none());
        assert_eq!(scc, graph.node_weight(node2).unwrap().scc().unwrap());
        assert_eq!(scc, graph.node_weight(node3).unwrap().scc().unwrap());
    }
}