dagre 0.1.1

A Rust port of dagre - directed graph layout using the Sugiyama method
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
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139

//! Recursive subgraph sorting for crossing reduction.
//!
//! Sorts the children of a compound node by computing barycenters,
//! resolving constraint conflicts, and recursively handling nested subgraphs.

use crate::graph::Graph;
use crate::layout::types::{EdgeLabel, NodeLabel};

use super::barycenter::{self, BarycenterEntry};
use super::resolve_conflicts;
use super::sort;

/// Result of sorting a subgraph: the ordered node list and optional
/// aggregate barycenter/weight.
#[derive(Debug, Clone)]
pub(crate) struct SubgraphResult {
    pub vs: Vec<String>,
    pub barycenter: Option<f64>,
    pub weight: Option<i32>,
}

/// Recursively sort the children of node `v` in the layer graph `g`.
///
/// - `g`: the layer graph (compound)
/// - `v`: the subgraph/root node whose children we're sorting
/// - `cg`: the constraint graph (edges encode "must come before" relationships)
/// - `bias_right`: if true, break ties by favoring right placement
pub(crate) fn sort_subgraph(
    g: &Graph<NodeLabel, EdgeLabel>,
    v: &str,
    cg: &Graph<(), ()>,
    bias_right: bool,
) -> SubgraphResult {
    let mut movable: Vec<String> = g.children(Some(v));
    let node = g.node(v);
    let bl: Option<String> = node.and_then(|n| n.border_left.first().cloned());
    let br: Option<String> = node.and_then(|n| n.border_right.first().cloned());

    // Exclude border nodes from the movable set
    if bl.is_some() {
        movable.retain(|w| Some(w.as_str()) != bl.as_deref() && Some(w.as_str()) != br.as_deref());
    }

    // Compute barycenters for the movable nodes
    let mut barycenters = barycenter::barycenter(g, &movable);

    // For each entry that is itself a subgraph, recursively sort it and merge
    let mut subgraph_results: std::collections::BTreeMap<String, SubgraphResult> =
        std::collections::BTreeMap::new();

    for entry in &mut barycenters {
        let children = g.children(Some(&entry.v));
        if !children.is_empty() {
            // This node is a subgraph; recursively sort it
            let sub_result = sort_subgraph(g, &entry.v, cg, bias_right);
            subgraph_results.insert(entry.v.clone(), sub_result.clone());

            // Merge the sub-result's barycenter into this entry
            if sub_result.barycenter.is_some() {
                merge_barycenters(entry, &sub_result);
            }
        }
    }

    // Resolve conflicts between barycenters and constraint graph
    let mut entries = resolve_conflicts::resolve_conflicts(&barycenters, cg);

    // Expand any subgraph entries: replace the subgraph node with its sorted children
    for entry in &mut entries {
        entry.vs = entry
            .vs
            .iter()
            .flat_map(|node_v| {
                if let Some(sub) = subgraph_results.get(node_v) {
                    sub.vs.clone()
                } else {
                    vec![node_v.clone()]
                }
            })
            .collect();
    }

    // Final sort by barycenter
    let mut result = sort::sort(&entries, bias_right);

    // If there are border nodes, sandwich them around the result
    if let (Some(bl_v), Some(br_v)) = (&bl, &br) {
        // Insert border left at the beginning, border right at the end
        let mut final_vs = vec![bl_v.clone()];
        final_vs.extend(result.vs);
        final_vs.push(br_v.clone());
        result.vs = final_vs;

        // Adjust barycenter to include border predecessors
        let bl_preds = g.predecessors(bl_v).unwrap_or_default();
        if !bl_preds.is_empty() {
            let bl_pred_order = g.node(&bl_preds[0]).and_then(|n| n.order).unwrap_or(0) as f64;
            let br_preds = g.predecessors(br_v).unwrap_or_default();
            let br_pred_order = if !br_preds.is_empty() {
                g.node(&br_preds[0]).and_then(|n| n.order).unwrap_or(0) as f64
            } else {
                0.0
            };

            if result.barycenter.is_none() {
                result.barycenter = Some(0.0);
                result.weight = Some(0);
            }

            let bc = result.barycenter.unwrap();
            let w = result.weight.unwrap();
            result.barycenter =
                Some((bc * w as f64 + bl_pred_order + br_pred_order) / (w + 2) as f64);
            result.weight = Some(w + 2);
        }
    }

    SubgraphResult {
        vs: result.vs,
        barycenter: result.barycenter,
        weight: result.weight,
    }
}

/// Merge a subgraph result's barycenter into a parent barycenter entry.
fn merge_barycenters(target: &mut BarycenterEntry, other: &SubgraphResult) {
    if let (Some(t_bc), Some(t_w)) = (target.barycenter, target.weight) {
        let o_bc = other.barycenter.unwrap_or(0.0);
        let o_w = other.weight.unwrap_or(0);
        let total_w = t_w + o_w;
        if total_w > 0 {
            target.barycenter = Some((t_bc * t_w as f64 + o_bc * o_w as f64) / total_w as f64);
            target.weight = Some(total_w);
        }
    } else {
        target.barycenter = other.barycenter;
        target.weight = other.weight;
    }
}