mini-graph

mini-graph is a small Rust library for building directed graphs and freezing them into a compact CSR (Compressed Sparse Row) representation.

The library was written to support Markov chains built from text, but it is not limited to that specific use case.

The main goal is to make graph construction simple and safe in Rust, avoiding pointer-heavy designs and lifetime complexity.

---

Motivation

Building graphs with pointers in Rust is difficult due to ownership and lifetime constraints. This library avoids that problem by:

• Referring to nodes by integer IDs instead of references
• Converting the graph into a read-only CSR representation for fast traversal
• Arena is used for a fast drop. Only worth it on big graphs

Once the graph is frozen, the arena can be dropped and the CSR graph can be used independently.

The existing graph libraries are just too much for my use case, so I wrote this library to provide a lightweight alternative to suit my needs.

---

Design overview

The library has two distinct phases:

1. Graph construction (Graph)

• Nodes are added sequentially and receive dense integer IDs (StateId)
• Edges are added by (from, to) ID pairs
• Edge weights are accumulated as counts
• Memory is allocated using a bump arena
• The graph is mutable only in this phase

2. Frozen graph (CsrGraph)

• The graph is converted into CSR format
• Topology is stored in flat arrays (row_ptr, col_idx, weights)
• Node data is stored separately and indexed by node ID
• The structure is immutable and does not depend on the arena
• Designed for fast iteration and random walks

---

Intended use

This library is intentionally minimal. It is designed for:

• Markov chains
• Situations where simplicity and memory locality matter more than flexibility

It is not designed for:

• Highly dynamic graphs
• Frequent node removal
• Pointer-based graph APIs
• General-purpose graph algorithms

---

Example

use bumpalo::Bump;
use mini_graph::Graph;

let arena = Bump::new();
let mut graph = Graph::new(&arena);

let a = graph.add_node("a");
let b = graph.add_node("b");

graph.add_edge(a, b);
graph.add_edge(a, b);

let csr = graph.freeze();

// arena can be dropped here

println!("{}", csr.node_data(a));