Rust Sugiyama

Description

An implementation of Sugiyamas algorithm for displaying a layered graph.

This crate heavily uses the crate petgraph under the hood.

Cycle Removal is implemented by using the greedy_feedback_arc_set function of petgraph and then reversing the edges from the set.

The rank assignment algorithm is implemented according to the paper A Technique for Drawing Directed Graphs by Gansner et al. which can be found here. It first assigns a node a layer and creates an optimal feasible tree for rank assignment.

Crossing Reduction follows the weighted median heuristic which is also descriped in the above paper, it is also possible to use the barycenter heuristic for crossing reduction via configuration. In order to count crossings, the Bilayer Cross Count algorithm as described in the paper Simple and Efficient Bilayer Cross Counting by Wilhelm Barth and Petra Mutzel and Michael Juenger. It can also be found online.

Finally, the implementation for coordinate assignment follows the algorithm provided by Brandes and Koepf, which can be found in this paper.

Bugs or feature requests can be either submitted via a github issue or by contacting patrickbaumann579@gmail.com.

Usage

Currently, there are three options to create a layout:

1. from_edges, which takes a &[(u32, u32)]
2. from_vertices_and_edges, which takes a &[u32] and a &[(u32, u32)]
3. from_graph, which takes a petgraph::StableDiGraph<V, E>

They will divide the graph into its connected components and calculate the coordinates seperately for each component. The API is implemented via the builder pattern, where a user may specify values like the minimum spacing between vertices etc.

build_layout_from_edges

This takes a &[u32, u32] slice and calculates the x and y coordinates, the height of the graph, and the width.

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}");
}

build_layout_from_graph

Takes as input a &StableDiGraph<V, E> and calculates the x and y coordinates, the height and width of the graph. NodeIndices are preserved between layouts and map directly to the input graph.

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}");
}

configuration via envs

It is also possible to configure the algorithm via environment variables, using the method configure_from_env().

Environment variables that can be set are: