dagre_rust/layout/order/
sort_subgraph.rs

1use graphlib_rust::Graph;
2use ordered_hashmap::OrderedHashMap;
3use crate::{GraphConfig, GraphEdge, GraphNode};
4use crate::layout::order::barycenter::{barycenter, Barycenter};
5use crate::layout::order::resolve_conflicts::{resolve_conflicts, ResolvedBaryEntry};
6use crate::layout::order::sort::sort;
7
8#[derive(Debug, Clone, Default)]
9pub struct SubgraphResult {
10  pub vs: Vec<String>,
11  pub barycenter: f32,
12  pub weight: f32
13}
14
15pub fn sort_subgraph(
16  g: &Graph<GraphConfig, GraphNode, GraphEdge>,
17  v: &String,
18  cg: &Graph<GraphConfig, GraphNode,GraphEdge>,
19  bias_right: &bool
20) -> SubgraphResult {
21  let mut movable = g.children(v);
22  let node = g.node(v);
23  let bl = if node.is_some() {
24    node.unwrap().border_left_.clone()
25  } else {
26    None
27  };
28  let br = if node.is_some() {
29    node.unwrap().border_right_.clone()
30  } else {
31    None
32  };
33  let mut subgraphs: OrderedHashMap<String, SubgraphResult> = OrderedHashMap::new();
34
35  if br.is_some() {
36    movable = movable.into_iter().filter(|w| {
37      w != &bl.clone().unwrap() && w != &br.clone().unwrap()
38    }).collect();
39  }
40
41  let mut barycenters = barycenter(g, &movable);
42  barycenters.iter_mut().for_each(|entry| {
43    if g.children(&entry.v).len() > 0 {
44      let subgraph_result = sort_subgraph(g, &entry.v, cg, bias_right);
45      subgraphs.insert(entry.v.clone(), subgraph_result.clone());
46      merge_barycenters(entry, &subgraph_result);
47    }
48  });
49
50  let mut entries = resolve_conflicts(&barycenters, cg);
51  expand_subgraphs(&mut entries, &subgraphs);
52
53  let mut result = sort(&entries, bias_right);
54  if bl.is_some() {
55    let bl_ = bl.clone().unwrap();
56    let br_ = br.clone().unwrap();
57    result.vs = vec![vec![bl_.clone()], result.vs.clone(), vec![br_.clone()]].concat();
58    let bl_preds = g.predecessors(&bl_).unwrap_or(vec![]);
59    if bl_preds.len() > 0 {
60      let bl_pred = g.node(bl_preds.first().unwrap()).unwrap();
61      let br_pred = g.node(g.predecessors(&br_).unwrap_or(vec![]).first().unwrap()).unwrap();
62      // not required as it was handled by structs' default
63      /*
64      if (!_.has(result, "barycenter")) {
65        result.barycenter = 0;
66        result.weight = 0;
67      }
68      */
69      let bl_pred_order = bl_pred.order.clone().unwrap_or(0) as f32;
70      let br_pred_order = br_pred.order.clone().unwrap_or(0) as f32;
71      result.barycenter =
72        ( result.barycenter * result.weight + bl_pred_order + br_pred_order ) / (result.weight + 2.0);
73      result.weight += 2.0;
74    }
75  }
76
77  return result;
78}
79
80fn expand_subgraphs(entries: &mut Vec<ResolvedBaryEntry>, subgraphs: &OrderedHashMap<String, SubgraphResult>) {
81  entries.iter_mut().for_each(|entry| {
82    let mut vs: Vec<String> = vec![];
83    entry.vs.iter().for_each(|v| {
84      if subgraphs.contains_key(v) {
85        let subgraph = subgraphs.get(v).unwrap();
86        subgraph.vs.iter().for_each(|v_| {
87          vs.push(v_.clone());
88        });
89        return ();
90      }
91      vs.push(v.clone());
92    });
93
94    entry.vs = vs;
95  });
96}
97
98fn merge_barycenters(target: &mut Barycenter, other: &SubgraphResult) {
99  let target_barycenter = target.barycenter.clone().unwrap_or(0.0);
100  if target.barycenter.is_some() && target_barycenter > 0.0 {
101    let target_weight = target.weight.clone().unwrap_or(0.0);
102
103    target.barycenter = Some(
104      (target_barycenter * target_weight + other.barycenter * other.weight)
105        / (target_weight + other.weight)
106    );
107    target.weight = Some(target_weight + other.weight.clone());
108  } else {
109    target.barycenter = Some(other.barycenter.clone());
110    target.weight = Some(other.weight.clone());
111  }
112}
dagre_rust/layout/order/sort_subgraph.rs

dagre_rust/layout/order/
sort_subgraph.rs
