use std::collections::HashMap;
pub type NodeId = String;
#[derive(Debug, Clone)]
pub struct LayerEdge {
pub source: NodeId,
pub target: NodeId,
}
pub fn minimize_crossings(layers: &[Vec<NodeId>], edges: &[LayerEdge]) -> Vec<Vec<NodeId>> {
if layers.is_empty() {
return Vec::new();
}
let n_layers = layers.len();
let mut appearance: HashMap<&NodeId, usize> = HashMap::new();
let mut seq = 0usize;
for layer in layers {
for id in layer {
if !appearance.contains_key(id) {
appearance.insert(id, seq);
seq += 1;
}
}
}
let mut cur: Vec<Vec<NodeId>> = layers.to_vec();
let rounds = 4;
for r in 0..rounds {
if r % 2 == 0 {
for i in 1..n_layers {
reorder_by_neighbors(&mut cur, i, i - 1, edges, &appearance);
}
} else {
for i in (0..n_layers - 1).rev() {
reorder_by_neighbors(&mut cur, i, i + 1, edges, &appearance);
}
}
}
cur
}
fn reorder_by_neighbors(
cur: &mut [Vec<NodeId>],
layer_idx: usize,
other_idx: usize,
edges: &[LayerEdge],
appearance: &HashMap<&NodeId, usize>,
) {
let n = cur[layer_idx].len();
if n <= 1 {
return;
}
let pos_in_layer: HashMap<&str, usize> = cur[layer_idx]
.iter()
.enumerate()
.map(|(i, id)| (id.as_str(), i))
.collect();
let pos_in_other: HashMap<&str, usize> = cur[other_idx]
.iter()
.enumerate()
.map(|(i, id)| (id.as_str(), i))
.collect();
let mut nb: HashMap<usize, Vec<usize>> = HashMap::new();
for e in edges {
let s = e.source.as_str();
let t = e.target.as_str();
if let (Some(&sp), Some(&tp)) = (pos_in_layer.get(s), pos_in_other.get(t)) {
nb.entry(sp).or_default().push(tp);
}
if let (Some(&sp), Some(&tp)) = (pos_in_other.get(s), pos_in_layer.get(t)) {
nb.entry(tp).or_default().push(sp);
}
}
let layer = &cur[layer_idx];
let mut bary: Vec<(usize, f64, usize)> = Vec::with_capacity(n);
for (pos, id) in layer.iter().enumerate() {
let mut sum = 0.0f64;
let mut cnt = 0usize;
if let Some(nbrs) = nb.get(&pos) {
for &np in nbrs {
sum += np as f64;
cnt += 1;
}
}
let b = if cnt > 0 {
sum / cnt as f64
} else {
pos as f64
};
let app = *appearance.get(id).unwrap_or(&pos);
bary.push((pos, b, app));
}
bary.sort_by(|a, b| {
a.1.partial_cmp(&b.1)
.unwrap_or(std::cmp::Ordering::Equal)
.then(a.2.cmp(&b.2))
});
let new_layer: Vec<NodeId> = bary
.into_iter()
.map(|(pos, _, _)| layer[pos].clone())
.collect();
cur[layer_idx] = new_layer;
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn reduces_a_simple_crossing() {
let layers = vec![
vec!["A".to_string(), "B".to_string()],
vec!["C".to_string(), "D".to_string()],
];
let edges = vec![
LayerEdge {
source: "A".to_string(),
target: "D".to_string(),
},
LayerEdge {
source: "B".to_string(),
target: "C".to_string(),
},
];
let out = minimize_crossings(&layers, &edges);
let crossings = count_crossings(&out, &edges);
assert_eq!(crossings, 0, "minimize_crossings 应消除该简单交叉");
}
#[test]
fn preserves_node_set() {
let layers = vec![
vec!["A".to_string(), "B".to_string(), "C".to_string()],
vec!["D".to_string(), "E".to_string()],
];
let edges = vec![
LayerEdge {
source: "A".to_string(),
target: "D".to_string(),
},
LayerEdge {
source: "B".to_string(),
target: "E".to_string(),
},
LayerEdge {
source: "C".to_string(),
target: "D".to_string(),
},
];
let out = minimize_crossings(&layers, &edges);
let mut flat: Vec<String> = out.iter().flat_map(|l| l.iter().cloned()).collect();
flat.sort();
let mut expect = ["A", "B", "C", "D", "E"]
.iter()
.map(|s| s.to_string())
.collect::<Vec<_>>();
expect.sort();
assert_eq!(flat, expect);
}
fn count_crossings(layers: &[Vec<NodeId>], edges: &[LayerEdge]) -> usize {
if layers.len() < 2 {
return 0;
}
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
}
}