#directed-graph #graph #heuristics #graph-display

rust-sugiyama

Implementation of Sugiyama's algorithm to calculate coordinates of a directed graph

3 releases (breaking)

new 0.3.0 Jun 17, 2024
0.2.0 Apr 4, 2024
0.1.0 Mar 14, 2024

#258 in Algorithms

MIT license

155KB
4K SLoC

Rust Sugiyama

example worklfow

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:

ENV values default description
RUST_GRAPH_MIN_LEN integer, > 0 1 minimum edge length between layers
RUST_GRAPH_V_SPACING integer, > 0 10 minimum spacing between vertices on the same layer
RUST_GRAPH_DUMMIES (y|n) y if dummy vertices are included in the final layout
RUST_GRAPH_R_TYPE (original|minimize|up|down) minimize defines how vertices are places vertically
RUST_GRAPH_CROSS_MIN (barycenter|median) barycenter which heuristic to use for crossing reduction
RUST_GRAPH_TRANSPOSE (y|n) y if transpose function is used to further try to reduce crossings (may increase runtime significally for large graphs)
RUST_GRAPH_DUMMY_SIZE float, > 0, <= 1 1.0 size of dummy vertices in final layout, if dummy vertices are included. this will squish the graph horizontally

Dependencies

~2MB
~31K SLoC