viz: finished decycle algorithm

1 files changed, 308 insertions, 0 deletions

diff --git a/viz/src/decycle.rs b/viz/src/decycle.rs
new file mode 100644
index 0000000..7bda958
--- /dev/null
+++ b/viz/src/decycle.rs
@@ -0,0 +1,308 @@
+//! 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(())
+    }
+}