### 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

## 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

function of petgraph and then reversing the edges from the set.`greedy_feedback_arc_set`

The rank assignment algorithm is implemented according to the paper

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.`A Technique for Drawing Directed Graphs`

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

by Wilhelm Barth and Petra Mutzel and Michael Juenger. It can also be found online.`Simple and Efficient Bilayer Cross Counting`

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:

, which takes a`from_edges``&``[``(``u32``,``u32``)``]`

, which takes a`from_vertices_and_edges`

and a`&``[``u32``]``&``[``(``u32``,``u32``)``]`

, which takes a`from_graph``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

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

`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

and calculates the x and y coordinates, the height and width of the graph.
`&``StableDiGraph <V, E>`

`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