Crate cinnabar

Cinnabar is a library of graph algorithms that work with any kind of data strcutre implementing several specific traits provided by the library. It also includes several predefined graphs that can be used as is, or can serve as an example on how to implement graph trait in your specific case.

The philosphy of this library is to only provide functionality related to graph topology, namely connection between vertices. Any associated data should be handled by the client through the use of lightweight indices.

Quick start

To get started quickly, pick and instantiate a suitable graph from the graphs module. You can associate graph vertices with your own data through vertex indices when constructing a garph.

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

// Associated each verte in a grid with its weight = row * column
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);
}

Modules

construct

The module is the home for the constructions traits that allows createion and modification of graphs.

graphs

This module is a home for predefined graphs of various kinds. Some of them are generic enough to be used as is, avoiding the need to roll out your own graph, and some are only useful in a very particular cases.

index

This modules houses definitions for index traits, as well as predefined implementations that can be used to avoid rolling out custom indices.

marker

This module contains marker structs that modify graph structure like directionality.

prelude

This module simplifiies the reexport of commonly-used members. Note that pre-made graphs are not included into the prelude. Addtional convenieice utils in the utils module are not provided and require a separate use statement as well.

providers

This modules defines tratis the provide topologies for a graph. In general, a graph implementation provides two topologie, one for edges and one for vertices. They are typically represented by separate structs implementing the Topology trait.

topology

This module is a home to the most important trait in this library - the Topology trait. It is used and inherited by many other traits in the library because it provides the minimal implementation necessary for the graph traversal.

traversal

This module is a home for graph traversals. It defines two fundamental traversal algorithms, DFS and BFS, that rely on provided topolgy to traverse the items.

utils

This module is home of various usefuls utils for graph manipulation.