@rimbu/graph

Fast, immutable graph data structures for TypeScript & JavaScript.

@rimbu/graph provides a rich family of directed and undirected graph implementations, with optional edge values, and both hashed and sorted internal representations. All graphs are immutable & persistent, giving you predictable behaviour and structural sharing while still feeling ergonomic to use.

Use it whenever you need to model networks, dependencies, state machines, hierarchical links, or arbitrary relationships between entities.

Table of Contents

1. Why @rimbu/graph?
2. Feature Highlights
3. Quick Start
4. Core Concepts & Types
5. Directed vs Undirected Graphs
6. Valued Graphs
7. Traversal Helpers (Traverse)
8. Performance Notes
9. Installation
10. FAQ
11. Ecosystem & Integration
12. Contributing
13. License

Why @rimbu/graph?

Graphs are everywhere:

• Domain models – users ↔ groups, services ↔ dependencies, resources ↔ references.
• Algorithms – path finding, reachability, connectivity, topological ordering.
• Config & state – workflows, finite state machines, dependency graphs.

@rimbu/graph focuses on:

• Clear semantics – separate types for directed (ArrowGraph) and undirected (EdgeGraph) graphs.
• Valued edges – attach weights, metadata, or labels via valued graphs (e.g. ArrowValuedGraphHashed).
• Immutable operations – updates always return new instances, sharing structure internally.
• Strong typing – generics for node and value types, plus non‑empty refinements.
• Consistent API – graph families share common operations and higher‑kinded Context / Builder types.

Feature Highlights

• Directed & undirected graphs – choose between arrow (directed) and edge (undirected) graphs.
• Valued edges – store extra data per connection (weights, labels, costs, metadata).
• Hashed & sorted variants – pick between hashed (*Hashed) or sorted (*Sorted) internal collections.
• Immutable & persistent – safe sharing across components, snapshots, and undo/redo flows.
• Context & builders – use Context and Builder types for efficient, batched updates.
• Traversal utilities – breadth‑first and depth‑first traversal helpers via the exported Traverse namespace.

Try Rimbu (including @rimbu/graph) live in the browser using the Rimbu Sandbox on CodeSandbox.

Quick Start

Basic undirected graph

import { EdgeGraphHashed } from '@rimbu/graph';

// Create from node/connection tuples
const g = EdgeGraphHashed.of(
  [1, 2],
  [2, 3],
  [3, 4],
  [5] // isolated node
);

g.hasNode(2); // true
g.hasConnection(1, 2); // true

// Get all connections from a node as a nested map
const neighbors = g.getConnectionsFrom(2);
console.log(neighbors.toArray()); // e.g. [[1], [3]]

// Iterate graph elements as a stream
g.stream().toArray();
// => [[1, 2], [2, 3], [3, 4], [5]]

Basic directed graph

import { ArrowGraphHashed } from '@rimbu/graph';

const g = ArrowGraphHashed.of([1, 2], [2, 3], [3, 1]);

g.hasConnection(1, 2); // true
g.hasConnection(2, 1); // false

g.getConnectionsFrom(1).toArray();
// => [[2]]

Valued graph (weighted edges)

import { ArrowValuedGraphHashed } from '@rimbu/graph';

// [from, to, weight]
const wg = ArrowValuedGraphHashed.of([1, 2, 5], [2, 3, 3]);

wg.getValue(1, 2); // 5

wg.stream().toArray();
// => [[1, 2, 5], [2, 3, 3]]

Core Concepts & Types

The main public surface of @rimbu/graph is exported from src/main/index.mts.

Common graph interfaces

Directed (arrow) graphs

Each of the hashed/sorted variants has its own NonEmpty, Builder, and Context types, such as:

• ArrowGraphHashed.NonEmpty<N>
• ArrowGraphHashed.Context<UN>
• ArrowGraphSorted.NonEmpty<N>
• ArrowGraphSorted.Context<UN>

Undirected (edge) graphs

Again, hashed/sorted variants include corresponding NonEmpty, Builder, and Context types.

Directed vs Undirected Graphs

• Arrow graphs (ArrowGraph*) represent directed edges.
  A connection [1, 2] means “an edge from 1 to 2”, but not necessarily from 2 to 1.
• Edge graphs (EdgeGraph*) represent undirected edges.
  A connection [1, 2] is symmetric: hasConnection(1, 2) and hasConnection(2, 1) both hold.

All graph variants share core APIs, such as:

g.hasNode(node);
g.hasConnection(node1, node2);
g.getConnectionsFrom(node); // returns a map / set of neighbors
g.stream(); // stream of graph elements

Use *Hashed variants when you care about fast hashed lookups, and *Sorted variants when you want deterministic, ordered traversal.

Valued Graphs

Valued graphs let you store an extra value per edge (weight, label, capacity, etc.).

Generic valued interfaces

Concrete valued graph families

Each of these has matching NonEmpty, Builder, and Context types, and exposes a stream() that yields graph elements:

• Isolated node: [node]
• Valued connection: [from, to, value]

import { EdgeValuedGraphHashed } from '@rimbu/graph';

const g = EdgeValuedGraphHashed.of([1, 2, 'a'], [2, 3, 'b']);

g.getValue(1, 2); // 'a'
g.stream().toArray();
// => [[1, 2, 'a'], [2, 3, 'b']]

Traversal Helpers (Traverse)

The main index exports a Traverse namespace that groups traversal utilities:

import { Traverse, EdgeGraphHashed } from '@rimbu/graph';

const g = EdgeGraphHashed.of([1, 2], [2, 3], [1, 3], [3, 4]);

// Breadth‑first traversal
const bfs = Traverse.traverseBreadthFirstHashed(g, 1);
console.log(bfs.toArray());
// => [[1, 2], [1, 3], [2, 3], [3, 4]]

// Depth‑first traversal
const dfs = Traverse.traverseDepthFirstHashed(g, 1);
console.log(dfs.toArray());
// => [[1, 2], [2, 3], [1, 3], [3, 4]]

Available helpers include:

• traverseBreadthFirstCustom
• traverseBreadthFirstHashed
• traverseBreadthFirstSorted
• traverseDepthFirstCustom
• traverseDepthFirstHashed
• traverseDepthFirstSorted

All of them work with any non‑empty VariantGraphBase‑compatible graph from this package.

Performance Notes

• Graphs in Rimbu are built on persistent data structures – updates are typically \(O(\log n)\) and share most of their structure.
• Hashed vs sorted variants differ mainly in the underlying maps/sets (HashMap / HashSet vs SortedMap / SortedSet).
• Many operations accept generic StreamSource inputs (from @rimbu/stream), allowing efficient construction and transformation from arrays, iterables, or streams.

For more details, see the main Rimbu documentation at rimbu.org.

Installation

Node / Bun / npm / Yarn

npm install @rimbu/graph
# or
yarn add @rimbu/graph
# or
bun add @rimbu/graph
# or
deno add npm:@rimbu/graph

Then:

import { EdgeGraphHashed } from '@rimbu/graph/mod.ts';

Browser / ESM

@rimbu/graph ships both ESM and CJS builds. Use it with any modern bundler (Vite, Webpack, esbuild, Bun, etc.) or directly in Node ESM projects.

FAQ

Q: What is the difference between Graph, ArrowGraph, and EdgeGraph?
Graph and VariantGraph are general graph interfaces, while ArrowGraph* and EdgeGraph* are concrete families for directed and undirected graphs, respectively, with hashed/sorted variants and context/builder support.

Q: When should I use valued graphs?
Whenever edges carry additional information (weights, labels, capacities, timestamps, etc.), use ArrowValuedGraph* or EdgeValuedGraph* to keep that data close to the topology.

Q: Are these graphs mutable?
No. All operations return new graph instances; existing ones remain unchanged and can be freely shared.

Q: Can I build graphs incrementally?
Yes. Use the Builder types (e.g. ArrowGraphHashed.Builder, EdgeValuedGraphSorted.Builder) exposed via their Context or via helpers like toBuilder().

Ecosystem & Integration

• Part of the broader Rimbu collection ecosystem – interoperates with @rimbu/hashed, @rimbu/sorted, @rimbu/collection-types, and @rimbu/stream.
• Well‑suited for domain modelling, compilers/interpreters, schedulers, routing, and more.
• Works seamlessly with Rimbu streams and other collections for building rich, immutable data models.

Explore more at the Rimbu Graph docs and the Graph API reference.

Contributing

We welcome contributions! See the Contributing guide for details.

Made with contributors-img.

License

MIT © Rimbu contributors. See LICENSE for details.