summaryrefslogtreecommitdiff
path: root/viz/src/decycle.rs
diff options
context:
space:
mode:
Diffstat (limited to 'viz/src/decycle.rs')
-rw-r--r--viz/src/decycle.rs308
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(())
+ }
+}
generated by cgit v1.2.3-18-g5258 (git 2.32.0) at 2024-11-09 23:04:59 +0000