@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

$3

``ts
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]]
`

$3

`ts
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]]
`

$3

`ts
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.

$3

| Name | Description |
| ----------------------- | ---------------------------------------------------------------------------------------- |
| Graph | Type‑invariant immutable graph interface. |
| Graph.NonEmpty | Non‑empty refinement of Graph with a non‑empty stream of graph elements. |
| Graph.Context | Factory/context for creating Graph instances and builders for an upper node type UN. |
| VariantGraph | Type‑variant graph interface with covariant node type. |
| VariantGraph.NonEmpty | Non‑empty refinement of VariantGraph with a non‑empty stream of graph elements. |

$3

| Name | Description |
| ------------------------ | ----------------------------------------------------------------------------------------------------- |
| ArrowGraph | Type‑invariant directed graph. |
| ArrowGraph.NonEmpty | Non‑empty directed graph; stream() yields either [N] (isolated node) or [from, to] connections. |
| ArrowGraph.Context | Context for ArrowGraph instances (generic over an upper node type UN). |
| ArrowGraph.Builder | Mutable builder for efficiently constructing or mutating an ArrowGraph before freezing it. |
| ArrowGraphHashed | Directed graph whose connections are internally stored in hashed collections. |
| ArrowGraphSorted | Directed graph whose connections are internally stored in sorted collections. |

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

- ArrowGraphHashed.NonEmpty
- ArrowGraphHashed.Context
- ArrowGraphSorted.NonEmpty
- ArrowGraphSorted.Context

$3

| Name | Description |
| ----------------------- | ------------------------------------------------------------------------------- |
| EdgeGraph | Type‑invariant undirected graph. |
| EdgeGraph.NonEmpty | Non‑empty undirected graph; stream() yields [N] or [N, N] graph elements. |
| EdgeGraph.Context | Context for EdgeGraph instances. |
| EdgeGraph.Builder | Mutable builder for EdgeGraph. |
| EdgeGraphHashed | Undirected graph backed by hashed collections. |
| EdgeGraphSorted | Undirected graph backed by sorted collections. |

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:

`ts
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.).

$3

| Name | Description |
| ----------------------------- | ------------------------------------------------------------------------------ |
| ValuedGraph | Type‑invariant graph where each connection has a value of type V. |
| ValuedGraph.NonEmpty | Non‑empty valued graph; stream() yields ValuedGraphElement elements. |
| VariantValuedGraph | Type‑variant valued graph. |
| VariantValuedGraph.NonEmpty | Non‑empty variant valued graph. |

$3

| Name | Description |
| ------------------------------ | --------------------------------------------------------- |
| ArrowValuedGraph | Directed valued graph interface. |
| ArrowValuedGraphHashed | Directed valued graph backed by HashMap structures. |
| ArrowValuedGraphSorted | Directed valued graph backed by SortedMap structures. |
| EdgeValuedGraph | Undirected valued graph interface. |
| EdgeValuedGraphHashed | Undirected valued graph backed by HashMap structures. |
| EdgeValuedGraphSorted | Undirected valued graph backed by SortedMap structures. |

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]

`ts
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:

`ts
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

$3

`sh
npm install @rimbu/graph


or

yarn add @rimbu/graph

or

bun add @rimbu/graph

or

deno add npm:@rimbu/graph
`

Then:

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

$3

@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.