From 1455da10f943e2aa1bdf26fb2697dafccc61e073 Mon Sep 17 00:00:00 2001 From: JSDurand 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(g: B) -> Result, Error> +where + B: Borrow, + 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 = vec![0; g.nodes_len()]; + + indices.shrink_to_fit(); + + // List of low link numbers of nodes + let mut lowlinks: Vec = indices.clone(); + + // The stack used in Trajan's algorithm + let mut tarjan_stack: Vec = Vec::new(); + + // The list of booleans to indicate whether a node is waiting on + // the stack + let mut waiting: Vec = vec![false; g.nodes_len()]; + + waiting.shrink_to_fit(); + + // a struct to help recursing + + #[derive(Debug)] + enum StackElement { + Seen(usize, Vec), + 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 = 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 = 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 { + 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 { + 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 { + 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> { + 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> { + 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> { + 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; + fn deserialize(bytes: impl AsRef<[u8]>) -> Result, Self::Error>; } -#[cfg(test)] -mod tests { - use super::*; +#[allow(unused)] +pub fn serialize( + actions: Vec, + filename: &Path, + final_p: bool, +) -> Result<(), ::Error> { + Ok(()) +} - #[test] - fn it_works() { - let result = add(2, 2); - assert_eq!(result, 4); +pub fn deserialize( + bytes: impl AsRef<[u8]>, +) -> Result<(Vec, ::Karmani), ::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(g: B) -> Result>, Error> +where + B: Borrow, + G: Graph, +{ + let g = g.borrow(); + + // List of components + let mut components: Vec> = Vec::new(); + + // List of depth levels of nodes + let mut indices: Vec = vec![0; g.nodes_len()]; + + indices.shrink_to_fit(); + + // List of low link numbers of nodes + let mut lowlinks: Vec = indices.clone(); + + // The stack used in Trajan's algorithm + let mut tarjan_stack: Vec = Vec::new(); + + // The list of booleans to indicate whether a node is waiting on + // the stack + let mut waiting: Vec = vec![false; g.nodes_len()]; + + waiting.shrink_to_fit(); + + // a struct to simplify recursing + + #[derive(Debug)] + enum StackElement { + Seen(usize, Vec), + 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 = 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 = 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 = 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 { + 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 { + 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> { + let length = 10; + + let cycle = make_cycle(length)?; + + let components = tarjan::<_, ALGraph>(&cycle)?; + + println!("components = {components:?}"); + + assert_eq!(components.len(), 1); + + let set: Set = components.first().unwrap().into_iter().copied().collect(); + + let answer: Set = (0..length).collect(); + + assert_eq!(set, answer); + + Ok(()) + } + + #[test] + fn test_two_components() -> Result<(), Box> { + 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 = components.get(0).unwrap().into_iter().copied().collect(); + let first_answer: Set = (half_length..(2 * half_length)).collect(); + + let second_set: Set = components.get(1).unwrap().into_iter().copied().collect(); + let second_answer: Set = (0..half_length).collect(); + + assert_eq!(first_set, first_answer); + assert_eq!(second_set, second_answer); + + Ok(()) + } +} -- cgit v1.2.3-18-g5258