use std::collections::HashMap;
use crate::ast::Direction;
use crate::builder::ir::{common::NodeId, unigraph::Unigraph};
use super::crossing::{LayerEdge, minimize_crossings};
#[allow(unused_imports)]
use crate::builder::ir::common::*;
fn detect_back_edges(ug: &Unigraph) -> std::collections::HashSet<(NodeId, NodeId)> {
let mut adj: std::collections::HashMap<NodeId, Vec<NodeId>> = std::collections::HashMap::new();
for n in &ug.nodes {
adj.entry(n.id.clone()).or_default();
}
for e in &ug.edges {
adj.entry(e.source.clone())
.or_default()
.push(e.target.clone());
}
let mut back: std::collections::HashSet<(NodeId, NodeId)> = std::collections::HashSet::new();
let mut color: std::collections::HashMap<NodeId, u8> = std::collections::HashMap::new();
for n in &ug.nodes {
color.insert(n.id.clone(), 0u8);
}
let mut stack: Vec<NodeId> = Vec::new();
let mut iter_idx: std::collections::HashMap<NodeId, usize> = std::collections::HashMap::new();
let ids: Vec<NodeId> = ug.nodes.iter().map(|n| n.id.clone()).collect();
for start in &ids {
if color.get(start).copied().unwrap_or(0) != 0 {
continue;
}
color.insert(start.clone(), 1);
stack.push(start.clone());
while let Some(top) = stack.last() {
let top_node = top.clone();
let idx = iter_idx.entry(top_node.clone()).or_insert(0);
let neighbors = adj.get(top).cloned().unwrap_or_default();
if *idx >= neighbors.len() {
color.insert(top_node.clone(), 2);
stack.pop();
continue;
}
let v = neighbors[*idx].clone();
*idx += 1;
match color.get(&v).copied().unwrap_or(0) {
1 => {
back.insert((top_node.clone(), v.clone()));
}
0 => {
color.insert(v.clone(), 1);
stack.push(v.clone());
}
_ => {} }
}
}
back
}
fn assign_layers(ug: &Unigraph) -> Vec<Vec<NodeId>> {
let ids: Vec<NodeId> = ug.nodes.iter().map(|n| n.id.clone()).collect();
let back_edges = detect_back_edges(ug);
let max_allowed = ids.len().saturating_sub(1).max(1);
let mut layer_of: HashMap<NodeId, usize> = HashMap::new();
for id in &ids {
layer_of.insert(id.clone(), 0);
}
let mut changed = true;
let mut guard = 0;
while changed && guard < ids.len() + 1 {
changed = false;
guard += 1;
for e in &ug.edges {
if back_edges.contains(&(e.source.clone(), e.target.clone())) {
continue;
}
let sl = *layer_of.get(&e.source).unwrap_or(&0);
let tl = *layer_of.get(&e.target).unwrap_or(&0);
if tl <= sl {
let new_tl = (sl + 1).min(max_allowed);
if new_tl > tl {
layer_of.insert(e.target.clone(), new_tl);
changed = true;
}
}
}
}
let max_layer = layer_of.values().cloned().max().unwrap_or(0);
let mut layers: Vec<Vec<NodeId>> = vec![Vec::new(); max_layer + 1];
for id in &ids {
let l = *layer_of.get(id).unwrap_or(&0);
layers[l].push(id.clone());
}
layers
}
pub fn sugiyama_layers(ug: &Unigraph) -> Vec<Vec<NodeId>> {
let layers = assign_layers(ug);
let layer_of: HashMap<&NodeId, usize> = layers
.iter()
.enumerate()
.flat_map(|(li, l)| l.iter().map(move |id| (id, li)))
.collect();
let mut layer_edges: Vec<LayerEdge> = Vec::new();
for e in &ug.edges {
let (Some(&si), Some(&ti)) = (layer_of.get(&e.source), layer_of.get(&e.target)) else {
continue;
};
if si + 1 == ti {
layer_edges.push(LayerEdge {
source: e.source.clone(),
target: e.target.clone(),
});
}
}
let mut optimized = minimize_crossings(&layers, &layer_edges);
match ug.direction {
Direction::BT | Direction::RL => {
optimized.reverse();
}
_ => {}
}
optimized
}
#[cfg(test)]
mod tests {
use super::*;
use crate::builder::ir::unigraph::{EdgeKind, UGEdge, UGNode};
fn mk_node(id: &str) -> UGNode {
UGNode {
id: id.to_string(),
kind: NodeKind::Atom,
role: NodeRole::Atom,
shape: crate::builder::ir::shape::ShapeKind::Rectangle,
label: LabelOrMeasured::Spec(LabelSpec {
text: id.to_string(),
spans: vec![],
}),
ports: PortSet::default(),
size_hint: SizeHint::default(),
style_ref: StyleRef::default(),
constraint: NodeConstraint::default(),
detail: NodeDetail::None,
}
}
fn mk_edge(s: &str, t: &str) -> UGEdge {
UGEdge {
id: format!("{}-{}", s, t),
source: s.to_string(),
target: t.to_string(),
source_port: PortHint::Bottom,
target_port: PortHint::Top,
kind: EdgeKind::Flow,
label_text: None,
label: None,
priority: EdgePriority::Primary,
routing_hint: RoutingHint::Orthogonal,
arrow: ArrowSpec {
start: ArrowKind::None,
end: ArrowKind::Arrow,
},
line_kind: LineKind::Solid,
repulsion: 1.0,
cardinality: (None, None),
cardinality_text: (None, None),
}
}
fn count_crossings_ug(layers: &[Vec<NodeId>], edges: &[UGEdge]) -> usize {
let pos =
|li: usize, id: &str| -> Option<usize> { layers[li].iter().position(|x| x == id) };
let mut count = 0;
for li in 0..layers.len() - 1 {
let mut segs: Vec<(usize, usize)> = Vec::new();
for e in edges {
if let (Some(sp), Some(tp)) = (pos(li, &e.source), pos(li + 1, &e.target)) {
segs.push((sp, tp));
}
}
for i in 0..segs.len() {
for j in i + 1..segs.len() {
let (s1, t1) = segs[i];
let (s2, t2) = segs[j];
if (s1 < s2 && t1 > t2) || (s1 > s2 && t1 < t2) {
count += 1;
}
}
}
}
count
}
#[test]
fn sugiyama_reduces_crossings_on_3_layers() {
let mut ug = Unigraph::default();
for id in ["A", "B", "C", "D", "E", "F"] {
ug.nodes.push(mk_node(id));
}
ug.edges.push(mk_edge("A", "C"));
ug.edges.push(mk_edge("B", "D"));
ug.edges.push(mk_edge("A", "D"));
ug.edges.push(mk_edge("B", "C"));
ug.edges.push(mk_edge("C", "E"));
ug.edges.push(mk_edge("D", "F"));
ug.edges.push(mk_edge("C", "F"));
ug.edges.push(mk_edge("D", "E"));
let baseline = vec![
vec!["A".to_string(), "B".to_string()],
vec!["C".to_string(), "D".to_string()],
vec!["E".to_string(), "F".to_string()],
];
let baseline_cross = count_crossings_ug(&baseline, &ug.edges);
assert!(baseline_cross > 0, "基线应存在交叉");
let out = sugiyama_layers(&ug);
let out_cross = count_crossings_ug(&out, &ug.edges);
assert!(
out_cross <= baseline_cross,
"Sugiyama 交叉({})应不高于基线({})",
out_cross,
baseline_cross
);
}
#[test]
fn sugiyama_reverses_layers_for_bt() {
let mut ug = Unigraph::default();
for id in ["A", "B", "C"] {
ug.nodes.push(mk_node(id));
}
ug.edges.push(mk_edge("A", "B"));
ug.edges.push(mk_edge("B", "C"));
ug.direction = Direction::TB;
let out = sugiyama_layers(&ug);
assert_eq!(out[0], vec!["A".to_string()]);
ug.direction = Direction::BT;
let out2 = sugiyama_layers(&ug);
assert_eq!(out2[0], vec!["C".to_string()]);
}
}