#graph #persistent #tree #immutability

grapes

Persistent graph data structures: Tree, Graph, Arena & more

5 unstable releases

0.3.0 May 19, 2022
0.2.0 Apr 26, 2022
0.1.2 Apr 23, 2022
0.1.1 Apr 23, 2022
0.1.0 Apr 23, 2022

#99 in #persistent

MIT/Apache

120KB
2.5K SLoC

Grapes: Persistent Graph Data Structures

Persistent: Cheap to clone, so you can keep (and modify) older versions of the data structure easily.

Data Structures:

  • Tree: hierarchical, indexable collection with ordered children
  • MapTree: maintains a key-node mapping in addition to a tree
  • Graph: collection of nodes connected by edges
  • MapGraph: also maintains a key-node and key-edge mapping
  • Arena: for building arbitrary graph-like data structures

Alternatives

Unless you specifically need a persistent tree or a persistent graph, I recommend using these crates instead (these are more mature, and probably faster):

If you need simple persistent data structures (lists, maps), check out:

Status

This library only supports what I need it to support for my very specific use case.

There are no benchmarks; performance is probably nowhere near other libraries, and this is fine for me.

Use Cases

This library is only useful if you need graph structures that can be somewhat cheaply cloned and manipulated.

For example, if you're building an application that stores state in a graph structure, and needs efficient undo-redo functionality, you might want to store past copies of the graph in memory. To do this efficiently, those copies should share parts of the graph that didn't change.

Dependencies

~1MB
~29K SLoC