path: root/viz/src/decycle.rs

//! This module implements a preprocessing of graphs that get rid of
//! the loops in the graph.  This step is needed because we want to
//! assign ranks to the nodes.

// REVIEW: Maybe we need no heuristic to break cycles here.  We can
// simply reverse all backward edges.  These are already found through
// Tarjan's algorithm.
//
// We need to experiment with this approach before determining whether
// or not to adapt a heuristic to reverse less edges.

use graph::{error::Error, Graph};
use std::borrow::Borrow;

// REFACTOR: Replace the use of 0 as the initial unused index by an
// Optional usize.  The compiler is almost surely going to compile the
// extra usage away, and the replaced code will be much more readable.

/// This function accepts a graph and returns a list of edges whose
/// direction should be reversed, in order to "break cycles".  That
/// is, this function returns a list of edges, and if we view the
/// edges on the list as reversed, then the graph would contain no
/// cycles.
///
/// This is adapted from Tarjan's algorithm for finding strongly
/// connected components, which is also implemented in the module
/// [strong_component][crate::strong_component].
pub fn decycle<B, G>(g: B) -> Result<Vec<(usize, usize)>, Error>
where
    B: Borrow<G>,
    G: Graph,
{
    let g = g.borrow();

    // List of edges to reverse
    let mut edges: Vec<(usize, usize)> = Vec::new();

    // List of depth levels of nodes
    let mut indices: Vec<usize> = vec![0; g.nodes_len()];

    indices.shrink_to_fit();

    // List of low link numbers of nodes
    let mut lowlinks: Vec<usize> = indices.clone();

    // The stack used in Trajan's algorithm
    let mut tarjan_stack: Vec<usize> = Vec::new();

    // The list of booleans to indicate whether a node is waiting on
    // the stack
    let mut waiting: Vec<bool> = vec![false; g.nodes_len()];

    waiting.shrink_to_fit();

    // a struct to help recursing

    #[derive(Debug)]
    enum StackElement {
        Seen(usize, Vec<usize>),
        Unseen(usize),
    }

    use StackElement::{Seen, Unseen};

    // convenient macros

    macro_rules! get_mut {
        ($arr:ident, $index:ident) => {
            *$arr.get_mut($index).unwrap()
        };
    }

    macro_rules! index {
        ($num: ident) => {
            indices.get($num).copied().unwrap()
        };
    }

    macro_rules! lowlink {
        ($num: ident) => {
            lowlinks.get($num).copied().unwrap()
        };
    }

    // The stack used to replace recursive function calls
    let mut recursive_stack: Vec<StackElement> = Vec::new();

    // The next index to assign
    let mut next_index: usize = 1;

    for node in g.nodes() {
        if indices.get(node).copied() == Some(0) {
            recursive_stack.push(Unseen(node));

            'recursion: while let Some(stack_element) = recursive_stack.pop() {
                let stack_node: usize;

                match stack_element {
                    Seen(node, children) => {
                        stack_node = node;

                        for child in children {
                            get_mut!(lowlinks, node) =
                                std::cmp::min(lowlink!(node), lowlink!(child));
                        }
                    }

                    Unseen(node) => {
                        stack_node = node;

                        tarjan_stack.push(node);

                        // It is safe to unwrap here since the
                        // condition of the if clause already serves
                        // as a guard.
                        get_mut!(indices, node) = next_index;
                        get_mut!(lowlinks, node) = next_index;
                        get_mut!(waiting, node) = true;

                        next_index += 1;

                        let mut node_index: Option<usize> = None;

                        for child in g.children_of(node)? {
                            // Ignore self-loops
                            if node == child {
                                continue;
                            }

                            match indices.get(child).copied() {
                                Some(0) => {
                                    // forward edge

                                    match node_index {
                                        Some(index) => match recursive_stack.get_mut(index) {
                                            Some(Seen(_, children)) => {
                                                children.push(child);
                                            }
                                            Some(_) => {
                                                unreachable!("wrong index: {index}");
                                            }
                                            None => {
                                                unreachable!("index {index} out of bounds");
                                            }
                                        },
                                        None => {
                                            node_index = Some(recursive_stack.len());

                                            let mut children = Vec::with_capacity(g.degree(node)?);
                                            children.push(child);

                                            recursive_stack.push(Seen(node, children));
                                        }
                                    }

                                    recursive_stack.push(Unseen(child));
                                }
                                Some(_) if waiting.get(child).copied().unwrap() => {
                                    // backward edge

                                    edges.push((node, child));

                                    get_mut!(lowlinks, node) =
                                        std::cmp::min(lowlink!(node), index!(child));
                                }
                                None => {
                                    return Err(Error::IndexOutOfBounds(child, g.nodes_len()));
                                }
                                _ => {
                                    // crossing edge
                                }
                            }
                        }

                        if node_index.is_some() {
                            continue 'recursion;
                        }
                    }
                }

                if lowlink!(stack_node) == index!(stack_node) {
                    while let Some(top) = tarjan_stack.pop() {
                        get_mut!(waiting, top) = false;

                        if top == stack_node {
                            break;
                        }
                    }
                }
            }
        }
    }

    Ok(edges)
}

#[cfg(test)]
mod test_decycle {
    use super::*;
    use graph::adlist::{ALGBuilder, ALGraph};
    use graph::builder::Builder;

    fn make_cycle(n: usize) -> Result<ALGraph, graph::error::Error> {
        let mut builder = ALGBuilder::default();

        builder.add_vertices(n);

        for i in 0..(n - 1) {
            builder.add_edge(i, i + 1, ())?;
        }

        builder.add_edge(n - 1, 0, ())?;

        Ok(builder.build())
    }

    fn make_two_cycles(n: usize) -> Result<ALGraph, graph::error::Error> {
        let mut builder = ALGBuilder::default();

        builder.add_vertices(2 * n);

        for i in 0..(2 * n - 1) {
            builder.add_edge(i, i + 1, ())?;
        }

        builder.add_edge(n - 1, 0, ())?;
        builder.add_edge(n - 2, 0, ())?; // random noise
        builder.add_edge(0, n - 1, ())?; // random noise
        builder.add_edge(0, 2 * n - 1, ())?; // random noise
        builder.add_edge(2 * n - 1, n, ())?;

        Ok(builder.build())
    }

    fn make_chain(n: usize) -> Result<ALGraph, graph::error::Error> {
        let mut builder = ALGBuilder::default();

        builder.add_vertices(n);

        for i in 0..(n - 1) {
            builder.add_edge(i, i + 1, ())?;
        }

        Ok(builder.build())
    }

    #[test]
    fn test_dechain() -> Result<(), Box<dyn std::error::Error>> {
        let length = 20;

        let chain = make_chain(length)?;

        // chain.print_viz("chain.gv")?;

        let edges = decycle::<_, ALGraph>(chain)?;

        println!("edges = {edges:?}");

        assert!(edges.is_empty());

        Ok(())
    }

    #[test]
    fn test_decycle() -> Result<(), Box<dyn std::error::Error>> {
        let length = 20;

        let cycle = make_cycle(length)?;

        // cycle.print_viz("cycle.gv")?;

        let edges = decycle::<_, ALGraph>(cycle)?;

        println!("edges = {edges:?}");

        assert_eq!(edges.len(), 1);
        assert_eq!(edges.first().copied(), Some((length - 1, 0)));

        Ok(())
    }

    #[test]
    fn test_de_two_components() -> Result<(), Box<dyn std::error::Error>> {
        let half_length = 10;

        let graph = make_two_cycles(half_length)?;

        // graph.print_viz("two cycles.gv")?;

        let edges = decycle::<_, ALGraph>(graph)?;

        println!("edges = {edges:?}");

        assert_eq!(edges.len(), 4);
        assert_eq!(
            edges.get(0).copied(),
            Some((2 * half_length - 2, 2 * half_length - 1))
        );
        assert_eq!(edges.get(1).copied(), Some((half_length - 1, 0)));
        assert_eq!(
            edges.get(2).copied(),
            Some((half_length - 2, half_length - 1))
        );
        assert_eq!(edges.get(3).copied(), Some((half_length - 2, 0)));

        Ok(())
    }
}