heapless_graphs

Heapless graphs in Rust

Heapless graphs library. Please see crate documentation for detailed usage.

This crate provides composable building blocks for graph structures, all with statically sized memory allocation.

The main aim is to provide very flexible and optionally compact memory storage of graphs, suitable for using in no_std environments, specifically microcontrollers.

Three types of graphs are implemented: adjacency lists, edge lists, and adjacency matrices, all implementing the same shared trait for a graph.

Code example with a simple graph:

   // Make a graph from edges and nodes
   let graph = EdgeNodeList::new(
     [(1_usize, 5), (5, 3), (7, 7)],
     [7, 4, 3, 1, 5]).unwrap();
   // Visited array tracker
   let mut visited = [false; 10];
   // Do a depth first traversal, starting from node 5
   dfs_recursive(&graph, 5, visited.as_mut_slice(), &mut |x| {
     println!("node: {}",x)
   });
   # Prints: node: 5, 3

A code golf version, with only edges:

    dfs_recursive_unchecked(
        &EdgeList::<3, _, _>::new([(1, 5), (5, 3), (7, 7)]).unwrap(),
        5,
        [false; 10].as_mut_slice(),
        &mut |x| println!("node: {}", x),
    );
   # Prints: node: 5, 3

This is still quite a raw draft, with APIs subject to change, see TODO for a long list of things that may change.

Note: This is mostly a Rust learning exercise. If you are looking for production quality graph implementations, see petgraph or various other graph libraries.

Contributing

Constructive criticism, suggestions and better design ideas very welcome !

See DESIGN for some design notes.

See CONTRIBUTING.md for details.

License

Apache 2.0; see LICENSE for details.

Disclaimer

This project is not an official Google project. It is not supported by Google and Google specifically disclaims all warranties as to its quality, merchantability, or fitness for a particular purpose.