#graph-algorithms #graph #algorithm

nightly cinnabar

Rust library of graph algorithms and data strctures

2 unstable releases

0.2.0 Nov 3, 2021
0.1.0 Oct 28, 2021

#2343 in Data structures

27 downloads per month

Custom license

34KB
673 lines

Cinnabar

Cinnabar is a pure-rust library of graph algorithms and data structures. It is designed to be fast and easy to use. Its defining feature is the decomposition of the multitude of graph-related functionality into several simple traits. No need to reinvent the algorithms from scratch for your specific case. After implementing a couple of traits, your will be able to tap into the power of graph and netork theory.

Quick start

Add cinnabar to the dependencies section of your project.

[dependencies]
cinnabar = "*"

To simplify development, you can use one of the pre-made graphs provided by the library.

use cinnabar::prelude::*;
use cinnabar::graphs::Grid;
use cinnabar::graphs::grid::Coords;
use std::collections::HashMap;

// Associated each vertexl in a grid with Manhattan distance to it.
let mut weights = HashMap::new();
let grid = Grid::with_inspector(2, 3, |id: Counter, row, col| {
    weights.insert(id, row + col);
});

// Traverse vertices by grid rows
for id in grid.traverse_by_rows() {
    let Coords(row, col) = grid.coords_of(id).unwrap();
    let weight = weights.get(&id).unwrap();
    println!("The weight of a vertex at {}, {} is {}", row, col, weight);
}

Features

This is a short list of features provided by the library. The list is not exhaustive, please consult the crate documentation for the detailed information.

Pre-made grahs

  • Grid
  • Adjacency list-based graph
  • Incidence matrix-based graph

Traversals

  • DFS
  • BFS
  • DFS-based
  • BFS-based
  • Dijkstra
  • A-star

Supported Rust versions

Cinnabar requires two features of Rust that are currently only provided in nightly builds:

Both proposals are moving quite fast and are close to stabilization. It is possible to implement the library without them, but at present it easier to focus the efforts on the functionality and not implementation. This can change if there is a sufficient interest in the community to have this library working in stable Rust, and the aforementioned features are not yet in stable Rust.

License

This project is licensed under the MIT license.

Dependencies

~405KB