viz: finished decycle algorithm

4 files changed, 637 insertions, 9 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(())
+    }
+}
diff --git a/viz/src/lib.rs b/viz/src/lib.rs
index b40c78a..9a15187 100644
--- a/viz/src/lib.rs
+++ b/viz/src/lib.rs
@@ -15,17 +15,53 @@
 
 extern crate graph;
 
-pub fn add(left: usize, right: usize) -> usize {
-    left + right
+use graph::Graph;
+
+use std::{error::Error, path::Path};
+
+pub mod strong_component;
+
+pub mod decycle;
+
+pub trait Action: Sized {
+    type Karmani: Graph;
+
+    type Error: Error;
+
+    fn perform(&self, obj: &mut Self::Karmani) -> Result<(), Self::Error>;
+
+    fn serialize(&self) -> Vec<u8>;
+    fn deserialize(bytes: impl AsRef<[u8]>) -> Result<Option<(Self, usize)>, Self::Error>;
 }
 
-#[cfg(test)]
-mod tests {
-    use super::*;
+#[allow(unused)]
+pub fn serialize<A: Action>(
+    actions: Vec<A>,
+    filename: &Path,
+    final_p: bool,
+) -> Result<(), <A as Action>::Error> {
+    Ok(())
+}
 
-    #[test]
-    fn it_works() {
-        let result = add(2, 2);
-        assert_eq!(result, 4);
+pub fn deserialize<A: Action>(
+    bytes: impl AsRef<[u8]>,
+) -> Result<(Vec<A>, <A as Action>::Karmani), <A as Action>::Error> {
+    let mut bytes = bytes.as_ref();
+
+    let mut result_actions = Vec::new();
+    let mut result_karmanayah = Default::default();
+
+    while let Some((action, offset)) = A::deserialize(bytes)? {
+        action.perform(&mut result_karmanayah)?;
+
+        result_actions.push(action);
+
+        bytes = &bytes[offset..];
     }
+
+    let result = (result_actions, result_karmanayah);
+
+    Ok(result)
 }
+
+// TODO: Figure out the parts to display graphs.
diff --git a/viz/src/plan.org b/viz/src/plan.org
new file mode 100644
index 0000000..dd7c9ab
--- /dev/null
+++ b/viz/src/plan.org
@@ -0,0 +1,27 @@
+#+TITLE: Plan of the package
+#+AUTHOR: Durand
+#+DATE: <2023-05-07 Dim 00:03>
+
+* Things to do [0/4]
+
+- [ ] Design an incremental format to encode forests [0/3]
+  + [ ] The format consists of a sequence of "actions".  Each action
+    modifies the graph as a unit.  For example, adding a vertex and
+    edges are actions, and cloning a node can be an action as well.
+  + [ ] The format has two functions that specific readers / writers
+    should implement.  For example, the forests for the chain-rule
+    machine can implement the two functions.  In the trait, the
+    implementer can choose which actions are availabel, and how each
+    action modifies the graph.
+  + [ ] Maybe each stored file can choose to include the final graph,
+    so that the displayer has the option to display only the final
+    graph without going through all modifications just to produce the
+    final graph.
+- [ ] Implement serialization
+- [ ] Implement de-serialization
+- [ ] Implement display of graphs
+  + [ ] Implement a graph display "server" that determines the
+    coordinates to be drawn on the canvas.
+  + [ ] Implement a graph display client, perhaps in Emacs, that
+    actually executes the display instructions.
+    
diff --git a/viz/src/strong_component.rs b/viz/src/strong_component.rs
new file mode 100644
index 0000000..37dcd39
--- /dev/null
+++ b/viz/src/strong_component.rs
@@ -0,0 +1,257 @@
+//! This module implements the Trajan's algorithm for finding strongly
+//! connected components of a directed graph with only one depth-first
+//! traversal.
+
+use graph::{error::Error, Graph};
+use std::borrow::Borrow;
+
+/// This function accepts a graph and returns a list of strongly
+/// connected components, represented as a list of nodes.
+pub fn tarjan<B, G>(g: B) -> Result<Vec<Vec<usize>>, Error>
+where
+    B: Borrow<G>,
+    G: Graph,
+{
+    let g = g.borrow();
+
+    // List of components
+    let mut components: Vec<Vec<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 simplify recursing
+
+    #[derive(Debug)]
+    enum StackElement {
+        Seen(usize, Vec<usize>),
+        Unseen(usize),
+    }
+
+    use StackElement::{Seen, Unseen};
+
+    // convenient macros
+
+    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 {
+                            *lowlinks.get_mut(node).unwrap() =
+                                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.
+                        *indices.get_mut(node).unwrap() = next_index;
+                        *lowlinks.get_mut(node).unwrap() = next_index;
+                        *waiting.get_mut(node).unwrap() = 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) => {
+                                    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() => {
+                                    *lowlinks.get_mut(node).unwrap() =
+                                        std::cmp::min(lowlink!(node), index!(child));
+                                }
+                                None => {
+                                    return Err(Error::IndexOutOfBounds(child, g.nodes_len()));
+                                }
+                                _ => {
+                                    // crossing edges are ignored
+                                }
+                            }
+                        }
+
+                        if node_index.is_some() {
+                            continue 'recursion;
+                        }
+                    }
+                }
+
+                if lowlink!(stack_node) == index!(stack_node) {
+                    let mut component: Vec<usize> = Vec::new();
+
+                    while let Some(top) = tarjan_stack.pop() {
+                        *waiting.get_mut(top).unwrap() = false;
+
+                        component.push(top);
+
+                        if top == stack_node {
+                            components.push(component);
+
+                            break;
+                        }
+                    }
+                }
+            }
+        }
+    }
+
+    Ok(components)
+}
+
+#[cfg(test)]
+mod tests {
+    use super::*;
+    use graph::adlist::{ALGBuilder, ALGraph};
+    use graph::builder::Builder;
+
+    use std::collections::BTreeSet as Set;
+
+    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())
+    }
+
+    #[test]
+    fn test_cycle() -> Result<(), Box<dyn std::error::Error>> {
+        let length = 10;
+
+        let cycle = make_cycle(length)?;
+
+        let components = tarjan::<_, ALGraph>(&cycle)?;
+
+        println!("components = {components:?}");
+
+        assert_eq!(components.len(), 1);
+
+        let set: Set<usize> = components.first().unwrap().into_iter().copied().collect();
+
+        let answer: Set<usize> = (0..length).collect();
+
+        assert_eq!(set, answer);
+
+        Ok(())
+    }
+
+    #[test]
+    fn test_two_components() -> Result<(), Box<dyn std::error::Error>> {
+        let half_length = 10;
+
+        let graph = make_two_cycles(half_length)?;
+
+        let components = tarjan::<_, ALGraph>(graph)?;
+
+        println!("components = {components:?}");
+
+        assert_eq!(components.len(), 2);
+
+        let first_set: Set<usize> = components.get(0).unwrap().into_iter().copied().collect();
+        let first_answer: Set<usize> = (half_length..(2 * half_length)).collect();
+
+        let second_set: Set<usize> = components.get(1).unwrap().into_iter().copied().collect();
+        let second_answer: Set<usize> = (0..half_length).collect();
+
+        assert_eq!(first_set, first_answer);
+        assert_eq!(second_set, second_answer);
+
+        Ok(())
+    }
+}