dagre_rust 0.0.5

Dagre implementation in Rust
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83

use graphlib_rust::{Edge, Graph};
use ordered_hashmap::OrderedHashMap;
use crate::layout::{GraphConfig, GraphEdge, GraphNode};
use crate::layout::util::unique_id;

pub fn run(graph: &mut Graph<GraphConfig, GraphNode, GraphEdge>) {
  let mut fas: Option<Vec<Edge>> = None;
  let graph_config = graph.graph();
  if graph_config.acyclicer.is_some() && graph_config.acyclicer.clone().unwrap() == "greedy".to_string() {
    // TODO: need to implement this algorithm
    println!("greedy_fas");
    // greedyFAS
  } else {
    fas = Some(dfs_fas(graph));
    // println!("dfs_fas");
  }

  let _fas = fas.unwrap_or(vec![]);
  for edge in _fas {
    let _edge_label = graph.edge_with_obj(&edge);
    if _edge_label.is_none() {
      continue;
    }
    let mut edge_label = _edge_label.cloned().unwrap();
    graph.remove_edge_with_obj(&edge);
    edge_label.forward_name = edge.name.clone();
    edge_label.reversed = Some(true);
    let _ = graph.set_edge(&edge.w, &edge.v, Some(edge_label), Some(format!("rev{}", unique_id())));
  }
}

fn dfs_fas(graph: &mut Graph<GraphConfig, GraphNode, GraphEdge>) -> Vec<Edge> {
  let mut fas: Vec<Edge> = vec![];
  let mut stack: OrderedHashMap<String, bool> = OrderedHashMap::new();
  let mut visited: OrderedHashMap<String, bool> = OrderedHashMap::new();

  fn dfs(
    node_id: String,
    stack: &mut OrderedHashMap<String, bool>,
    visited: &mut OrderedHashMap<String, bool>,
    graph: &mut Graph<GraphConfig, GraphNode, GraphEdge>,
    fas: &mut Vec<Edge>
  ) {
    if visited.contains_key(&node_id) {
      return ();
    }

    visited.insert(node_id.clone(), true);
    stack.insert(node_id.clone(), true);
    let out_edges = graph.out_edges(&node_id, None).unwrap_or(vec![]);
    for edge in out_edges.into_iter() {
      if stack.contains_key(&edge.w) {
        fas.push(edge.clone());
      } else {
        dfs(edge.w.clone(), stack, visited, graph, fas);
      }
    }
    stack.remove(&node_id);
  }

  for node_id in graph.nodes() {
    dfs(node_id, &mut stack, &mut visited, graph, &mut fas);
  }
  return fas;
}

pub fn undo(g: &mut Graph<GraphConfig, GraphNode, GraphEdge>) {
  for e in g.edges() {
    let edge = g.edge_mut_with_obj(&e).unwrap();
    if edge.reversed.clone().unwrap_or(false) {
      let forward_name = edge.forward_name.clone().unwrap();
      let mut label = edge.clone();
      label.reversed = None;
      label.forward_name = None;
      let _ = g.set_edge(
        &e.w,
        &e.v,
        Some(label),
        Some(forward_name)
      );
    }
  }
}