From 1455da10f943e2aa1bdf26fb2697dafccc61e073 Mon Sep 17 00:00:00 2001
From: JSDurand <mmemmew@gmail.com>
Date: Fri, 2 Jun 2023 14:51:25 +0800
Subject: viz: finished decycle algorithm
---
viz/src/decycle.rs | 308 ++++++++++++++++++++++++++++++++++++++++++++
viz/src/lib.rs | 54 ++++++--
viz/src/plan.org | 27 ++++
viz/src/strong_component.rs | 257 ++++++++++++++++++++++++++++++++++++
4 files changed, 637 insertions(+), 9 deletions(-)
create mode 100644 viz/src/decycle.rs
create mode 100644 viz/src/plan.org
create mode 100644 viz/src/strong_component.rs
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(())
+ }
+}
--
cgit v1.2.3-18-g5258