Rust Sugiyama

描述

用于显示层状图的Sugiyama算法的实现。

此crate底层大量使用petgraph crate。

通过petgraph的greedy_feedback_arc_set函数实现循环移除，然后反转集合中的边。

排名分配算法根据Gansner等人撰写的论文A Technique for Drawing Directed Graphs实现，该论文可在此处找到。它首先为节点分配一层，并创建一个排名分配的最优可行树。

交叉减少遵循上述论文中描述的加权中位数启发式方法，也可以通过配置使用重心启发式方法进行交叉减少。为了计算交叉，使用论文Simple and Efficient Bilayer Cross Counting中描述的Bilayer Cross Count算法，该论文由Wilhelm Barth、Petra Mutzel和Michael Juenger撰写，可在网上找到。

最后，坐标分配的实现遵循Brandes和Köpf提供的算法，该算法可在此论文中找到。

错误或功能请求可以通过github问题提交，或者通过联系[email protected]。

使用方法

目前，有三种方法来创建布局

1. from_edges，它接受一个&[(u32, u32)]
2. from_vertices_and_edges，它接受一个&[u32]和一个&[(u32, u32)]
3. from_graph，它接受一个petgraph::StableDiGraph<V, E>

它们会将图分解为其连通分量，并为每个分量分别计算坐标。API通过构建器模式实现，用户可以指定诸如顶点之间最小间距等值。

从边构建布局

该函数接收一个&[u32, u32]切片，并计算图的x和y坐标、高度和宽度。

use rust_sugiyama::from_edges;

let edges = [
    (0, 1), 
    (1, 2), 
    (1, 3), (1, 4), (1, 5), (1, 6), 
    (3, 7), (3, 8), (4, 7), (4, 8), 
    (5, 7), (5, 8), (6, 7), (6, 8), 
    (7, 9), (8, 9)
];
let 
let layouts = from_edges(&edges)
    .vertex_spacing(20)
    .build();

for (layout, width, height) in layouts {
    println!("Coordinates: {:?}", layouts);
    println!("width: {width}, height: {height}");
}

从图构建布局

接收输入一个&StableDiGraph<V, E>，并计算图的x和y坐标、高度和宽度。《code>NodeIndices在布局间保留，并直接映射到输入图中。

use rust_sugiuama::from_graph;
let mut g: StableDiGraph<String, usize> = StableDiGraph::new();

let rick = g.add_node("Rick".to_string());
let morty = g.add_node("Morty".to_string());
let beth = g.add_node("Beth".to_string());
let jerry = g.add_node("Jerry".to_string());
let summer = g.add_node("Summer".to_string());

g.add_edge(rick, beth, 1);
g.add_edge(rick, jerry, 1);
g.add_edge(beth, summer, 1);
g.add_edge(jerry, summer, 1);
g.add_edge(beth, morty, 1);
g.add_edge(jerry, morty, 1);

let layouts = from_graph(&g).build();
    .into_iter()
    .map(|(layout, width, height)| {
        let mut new_layout = HashMap::new();
        for (id, coords) in layout {
            new_layout.insert(g[NodeIndex::from(id)], coords);
        }
        (new_layout, width, height)
    })
    .collect::<Vec<_>>(); 

for (layout, width, height) in layouts {
    println!("Coordinates: {:?}", layout);
    println!("width: {width}, height: {height}");
}

通过环境变量进行配置

还可以通过环境变量使用configure_from_env()方法配置算法。

可以设置的环境变量有