# Effect Graph

> Build and analyze immutable graphs with Effect's Graph module — directed/undirected construction, scoped mutation (mutate/addNode/addEdge), node/edge queries, lazy DFS/BFS/topo walkers, algorithms (isAcyclic, stronglyConnectedComponents, dijkstra/astar/bellmanFord/floydWarshall), and GraphViz/Mermaid export. Use when modeling dependency graphs, ordering tasks topologically, detecting cycles, computing reachability or shortest paths, or rendering relationship diagrams.

- Skill: `mpsuesser/effect-graph` (Agent Skill)
- Install (CLI): `npx skillmds@latest add mpsuesser/effect-graph`
- Raw SKILL.md: https://api.skillmd.com/api/skills/mpsuesser/effect-graph/raw
- Safety review: pending
- Works with: Claude Code, Claude.ai, OpenAI Codex
- Category: Coding & Dev Tools
- Author: mpsuesser (https://skillmd.com/u/mpsuesser)
- Updated: 2026-09-17
- Page: https://skillmd.com/skills/mpsuesser/effect-graph

---


You are an Effect TypeScript expert specializing in the `Graph` module — building, querying, traversing, and running algorithms over immutable graphs.

## Effect Source Reference

The Effect v4 source is at `~/.local/share/opencode/repos/github.com/Effect-TS/effect@main/`. Read it directly when in doubt — the module is self-contained in a single file.

Key files:

- `packages/effect/src/Graph.ts` — the entire module: types, constructors, mutation scope, queries, walkers, traversals, algorithms, GraphViz/Mermaid export
- `packages/effect/test/Graph.test.ts` — edge-case semantics: multi-edges, self-loops, undefined node/edge data, negative-weight behavior, walker re-iteration, topo `initials`

## Core Model

A `Graph<N, E, T extends Kind = 'directed'>` is an **immutable** graph storing user data `N` on nodes and `E` on edges, where `T` is `'directed' | 'undirected'`. Writes only happen on a `MutableGraph<N, E, T>` inside an explicit mutation scope; everything else (queries, traversals, algorithms) accepts either form.

```ts
import { Graph, Option } from 'effect';
// or as a subpath module:
import * as Graph from 'effect/Graph';
```

The pieces:

- `Graph.NodeIndex` / `Graph.EdgeIndex` — plain `number` identifiers. They are allocated sequentially from `0` and **never reused after removal**; they are stable IDs, not array offsets.
- `Graph.Edge<E>` — a readonly structural interface with `{ source: NodeIndex; target: NodeIndex; data: E }`; edge reads return fresh plain records rather than exposing internal storage.
- `Graph.Snapshot<N, E, T>` — the active indexed wire shape `{ type, nodes, edges }`, with `IndexedNode` / `IndexedEdge` entries sorted by strictly increasing non-negative safe-integer indexes.
- `Graph.DirectedGraph<N, E>` / `Graph.UndirectedGraph<N, E>` — aliases for `Graph<N, E, 'directed' | 'undirected'>`; `MutableDirectedGraph` / `MutableUndirectedGraph` are the mutable counterparts.
- `Graph.GraphError` — a `Data.TaggedError('GraphError')<{ message: string }>`. The Graph API is fully **synchronous**: nothing returns `Effect`. Invalid operations **throw** `GraphError`; lookups return `Option`.
- `Graph.Walker<T, N>` — the lazy iterator wrapper returned by all traversal and listing APIs.

Call conventions:

- **Read APIs are dual** (data-first or pipeable data-last): `Graph.neighbors(graph, 0)` or `graph.pipe(Graph.neighbors(0))`.
- **Write APIs are data-first only** and take the `MutableGraph` as the first argument: `Graph.addNode(mutable, data)`.
- Graphs implement `Equal`, `Hash`, `Pipeable`, `Inspectable`, and are iterable over `[NodeIndex, N]` node entries. `Graph.isGraph` recognizes both immutable and mutable graphs; inspect `.mutable` and `.type` when that distinction matters.

## 1. Creating Graphs

`Graph.directed` and `Graph.undirected` create empty graphs, optionally running an initial mutation callback:

```ts
import { Graph } from 'effect';

const dag = Graph.directed<string, number>((mutable) => {
	const a = Graph.addNode(mutable, 'A'); // NodeIndex 0
	const b = Graph.addNode(mutable, 'B'); // NodeIndex 1
	const c = Graph.addNode(mutable, 'C'); // NodeIndex 2
	Graph.addEdge(mutable, a, b, 1); // EdgeIndex 0
	Graph.addEdge(mutable, b, c, 2); // EdgeIndex 1
});

const social = Graph.undirected<{ name: string }, string>((mutable) => {
	const alice = Graph.addNode(mutable, { name: 'Alice' });
	const bob = Graph.addNode(mutable, { name: 'Bob' });
	Graph.addEdge(mutable, alice, bob, 'friends');
});

Graph.isGraph(dag); // true — type guard for unknown values
```

Notes:

- The type parameters are `<NodeData, EdgeData>`; the kind is fixed by the constructor.
- Edge data can be `void`/`undefined` — pass `undefined` explicitly: `Graph.addEdge(m, a, b, undefined)`.
- Self-loops (`addEdge(m, a, a, data)`) and parallel edges between the same pair are allowed.
- For directed graphs, `source -> target` direction matters everywhere (traversal, topo, neighbors). For undirected graphs, the stored `source`/`target` are arbitrary endpoints; all queries and algorithms treat the edge symmetrically.

Use `Graph.make(kind)` when the graph kind is selected dynamically. Use snapshots when active identifiers must survive a boundary:

```ts
const restored = Graph.fromSnapshot({
	type: 'directed',
	nodes: [
		{ index: 2, data: 'A' },
		{ index: 5, data: 'B' }
	],
	edges: [{ index: 3, source: 2, target: 5, data: 1 }]
});

Graph.toSnapshot(restored); // newly allocated records; payload values are not cloned
```

`fromSnapshot` validates ordering, safe-integer indexes, and edge endpoints and throws `GraphError` on invalid input. Snapshots preserve active indexes and stored undirected edge orientation, but not removed-ID allocator history; future IDs continue after the highest active index. `graph.toJSON()` is only an inspection summary, not the snapshot wire format.

At a decoded boundary, use `Schema.toCodecJson(Schema.Graph(kind, nodeSchema, edgeSchema))` to validate and transform between the immutable graph and this snapshot representation.

## 2. Mutation: Scoped Writes

All writes go through a mutation scope. Prefer `Graph.mutate` (dual), which copies the graph, applies your function, and returns a new immutable graph:

```ts
const bigger = Graph.mutate(dag, (mutable) => {
	const d = Graph.addNode(mutable, 'D');
	Graph.addEdge(mutable, 2, d, 3);
});
// dag is unchanged; bigger is a new Graph
```

`beginMutation` / `endMutation` exist for manual control, but discard the `MutableGraph` after `endMutation`: finalization is terminal and later public mutations on that handle throw `GraphError`. `mutate` finalizes the handle whether its synchronous callback returns or throws, and rethrows the original callback failure. Each scope copies graph structure (payload objects remain shared), so batch related changes into one `mutate` call.

Write operations (all take the `MutableGraph` first; all return `void` except the two `add*`):

```ts
Graph.mutate(dag, (m) => {
	const idx = Graph.addNode(m, 'X'); // returns new NodeIndex
	const e = Graph.addEdge(m, 0, idx, 9); // returns new EdgeIndex; THROWS GraphError if either node is missing
	Graph.updateNode(m, idx, (data) => data.toLowerCase()); // silent no-op if index missing
	Graph.updateEdge(m, e, (w) => w * 2); // silent no-op if index missing
	Graph.removeEdge(m, e); // silent no-op if missing
	Graph.removeEdges(m, [e]); // bulk removal; missing/duplicate indexes ignored
	Graph.removeNode(m, idx); // removes the node AND all incident edges; no-op if missing
	Graph.removeNodes(m, [idx]); // bulk node + incident-edge removal
});
```

Mutation is forbidden while graph callbacks such as `mapNodes`, `filterMapEdges`, algorithm cost functions, and walker projections are evaluating against the same mutable graph. Such re-entrant writes throw `GraphError` and preserve graph invariants; querying from callbacks remains allowed.

## 3. Node & Edge Queries

Read APIs work on both `Graph` and `MutableGraph`, and are dual:

```ts
Graph.nodeCount(dag); // 3
Graph.edgeCount(dag); // 2
Graph.hasNode(dag, 0); // true
Graph.getNode(dag, 0); // Option.some('A')
Graph.getEdge(dag, 0); // Option.some({ source: 0, target: 1, data: 1 })
Graph.hasEdge(dag, 0, 1); // true — (graph, source, target); symmetric for undirected graphs

// Linear search by predicate (O(n) — keep your own Map<key, NodeIndex> for hot paths)
Graph.findNode(dag, (data) => data === 'B'); // Option.some(1)
Graph.findNodes(dag, (data) => data !== 'B'); // [0, 2]
Graph.findEdge(dag, (data, source, target) => data > 1); // Option.some(1)
Graph.findEdges(dag, (data) => data >= 1); // [0, 1]
```

Neighbors:

```ts
// Generic: outgoing targets for directed, all adjacent endpoints for undirected
Graph.neighbors(dag, 0); // [1]

// Directed-only (THROW GraphError on undirected graphs):
Graph.successors(dag, 0); // outgoing neighbors: [1]
Graph.predecessors(dag, 1); // incoming neighbors: [0]

// Edge-aware and degree queries
Graph.incidentEdges(dag, 1); // [0, 1], each incident edge once
Graph.outgoingEdges(dag, 1); // [1] — directed only
Graph.incomingEdges(dag, 1); // [0] — directed only
Graph.edgesBetween(dag, 0, 1); // [0], retaining parallel edge indexes
Graph.outDegree(dag, 1); // 1 — directed only
Graph.inDegree(dag, 1); // 1 — directed only
```

- `Graph.neighborsDirected(graph, node, direction)` still exists but is **deprecated** as of 4.0 — use `successors` / `predecessors`.
- `neighbors`, `successors`, and `predecessors` deduplicate parallel-edge neighbors and include a self-loop's node once. A missing node returns `[]` for these neighbor APIs.
- Degree APIs count edges, not unique neighbors: `degree` is undirected-only (parallel edges separately, self-loop twice); `outDegree` / `inDegree` are directed-only (self-loop once in each). Kind-specific edge and degree APIs throw `GraphError` when called on the wrong graph kind.

## 4. Bulk Transformations

These run inside a mutation scope and modify the `MutableGraph` in place. Indices are preserved by the `map*` variants; the `filter*` variants remove (node removal also drops incident edges):

```ts
const transformed = Graph.mutate(dag, (m) => {
	Graph.mapNodes(m, (data) => data.toUpperCase()); // transform every node's data
	Graph.mapEdges(m, (w) => w * 10); // transform every edge's data
	Graph.filterNodes(m, (data) => data !== 'C'); // drop non-matching nodes (+ their edges)
	Graph.filterEdges(m, (w) => w >= 10); // drop non-matching edges
});

// filterMap variants: Option.some(next) keeps + transforms, Option.none() removes
import { Option } from 'effect';
const pruned = Graph.mutate(dag, (m) => {
	Graph.filterMapNodes(m, (data) =>
		data.startsWith('A') ? Option.some(data.toLowerCase()) : Option.none()
	);
	Graph.filterMapEdges(m, (w) => (w > 1 ? Option.some(w * 2) : Option.none()));
});

// Reverse every edge (swap source/target). No-op for undirected graphs.
const reversed = Graph.mutate(dag, (m) => {
	Graph.reverse(m);
});
```

The transformation callback must not mutate or finalize the same graph. Bulk removals collect their input iterable before mutating, so `Graph.removeNodes(m, Graph.indices(Graph.nodes(m)))` is safe.

## 5. Set Operations and Derived Graphs

Graph composition APIs are dual and return immutable graphs:

- `compose`, `intersection`, `difference`, and `symmetricDifference` compare nodes and edges with Effect equality, optionally projected by `IdentityOptions.nodeIdentity` / `edgeIdentity`; graph kinds must match and results allocate fresh IDs.
- `sum` is a disjoint union that never merges equal nodes; `complement` creates absent non-self relationships.
- `neighborhood(graph, node, { radius, direction })` selects a reachable region and allocates fresh IDs; `inducedSubgraph(graph, indices)` selects exact nodes while preserving active node and retained edge indexes.
- `minimumSpanningForest` preserves indexes in undirected graphs; `transitiveReduction` preserves indexes in directed acyclic graphs.

Identity-based `compose`, `intersection`, and `symmetricDifference` coalesce parallel edges with the same endpoints and projected edge identity. `difference` preserves every left-side occurrence when that identity is absent from the right graph, but removes all such occurrences when the right graph contains the identity. Use `sum` or index-preserving selection when identifiers must remain distinct.

## 6. Walkers: Lazy Iterators

Every traversal and listing API returns a `Graph.Walker<Index, Data>` — a lazy iterable of `[index, data]` pairs. Aliases: `Graph.NodeWalker<N> = Walker<NodeIndex, N>` and `Graph.EdgeWalker<E> = Walker<EdgeIndex, Edge<E>>`.

```ts
const walker = Graph.dfs(dag, { start: [0] });

// Project with the module helpers:
Array.from(Graph.indices(walker)); // [0, 1, 2] — just NodeIndex values
Array.from(Graph.values(walker)); // ['A', 'B', 'C'] — just node data
Array.from(Graph.entries(walker)); // [[0, 'A'], [1, 'B'], [2, 'C']]

// Or map each element directly:
Array.from(walker.visit((index, data) => ({ id: index, name: data })));

// Iterating the walker itself yields [index, data] tuples:
for (const [index, data] of walker) {
	console.log(index, data);
}
```

Walker semantics:

- **Re-iterable with fresh state** — each `for...of` / `Array.from` restarts the traversal from scratch.
- **Lazy** — DFS/BFS/postorder/topological traversals of mutable graphs capture a snapshot when each iteration begins, and later mutations are not observed by that active iterator. Plain `nodes`, `edges`, and `externals` walkers do not snapshot mutable graphs, so mutations can affect remaining iteration.

Listing walkers:

```ts
Graph.nodes(dag); // NodeWalker over all nodes in insertion order
Graph.edges(dag); // EdgeWalker over all edges in insertion order (data is the full Edge<E>)

// Boundary nodes: nodes with NO edges in the given direction
Graph.externals(dag, { direction: 'outgoing' }); // sinks (+ isolated nodes)
Graph.externals(dag, { direction: 'incoming' }); // sources (+ isolated nodes)
// direction defaults to 'outgoing' (sinks)
```

- On **undirected** graphs every incident edge appears in both adjacency directions, so `externals` yields only **isolated nodes** regardless of `direction` — find leaves with `Graph.neighbors(g, n).length === 1` instead.

## 7. Traversals: DFS, BFS, Postorder, Topological

`dfs`, `bfs`, and `dfsPostOrder` take a `SearchConfig`: `{ start?: Array<NodeIndex>; direction?: 'outgoing' | 'incoming' | 'undirected'; radius?: number }`. All are dual and return a `NodeWalker<N>`:

```ts
// Preorder DFS from node 0, following outgoing edges (the default direction)
const down = Graph.dfs(dag, { start: [0] });

// Reverse traversal: everything that can REACH node 2
const up = Graph.dfs(dag, { start: [2], direction: 'incoming' });

// BFS: level order
const levels = Graph.bfs(dag, { start: [0] });

// Postorder: children emitted before parents (useful for bottom-up processing)
const bottomUp = Graph.dfsPostOrder(dag, { start: [0] });

// Traverse either edge direction up to two hops from the nearest start
const local = Graph.bfs(dag, {
	start: [0],
	direction: 'undirected',
	radius: 2
});
```

- Omitting `start` (or passing `[]`) yields an **empty iterator** — traversals do not default to all nodes; seed them explicitly (multiple start nodes cover disconnected components).
- Start arrays are copied and validated at walker creation; missing starts throw `GraphError`, and each fresh iteration revalidates them against its graph snapshot. Duplicate starts are ignored in supplied priority order.
- `radius` is shortest edge distance from the nearest start; it must be a non-negative integer or `Infinity`. `direction` is ignored for undirected graphs, whose edges always traverse both ways.
- Each node is visited at most once; cycles are safe.

Topological sort (`topo`) uses Kahn's algorithm and takes `TopoConfig`: `{ initials?: Array<NodeIndex> }`:

```ts
const order = Array.from(Graph.indices(Graph.topo(dag))); // [0, 1, 2]

// Prioritize specific zero in-degree nodes first; all nodes are still emitted
const prioritized = Graph.topo(dag, { initials: [0] });
```

`topo` **throws `GraphError`** when called on an undirected graph or a cyclic graph (`'Cannot perform topological sort on cyclic graph'`) — guard with `Graph.isAcyclic` first. An `initials` entry that has incoming edges throws `'Initial node N has incoming edges'` when iteration begins (not at creation).

## 8. Structure Analysis, Connectivity, Matching, and Flow

```ts
Graph.isAcyclic(dag); // true — works on directed and undirected graphs
Graph.findCycle(dag); // Option<CycleResult> with closed node path + edge indexes

// Undirected only (type-restricted):
Graph.isBipartite(social); // BFS 2-coloring; odd cycles => false
Graph.connectedComponents(social); // Array<Array<NodeIndex>>, e.g. [[0, 1], [2, 3]]
Graph.isConnected(social); // undirected only; empty graph is connected
Graph.isTree(social); // undirected only; empty graph is not a tree
Graph.bridges(social); // edge indexes whose removal disconnects a component
Graph.articulationPoints(social); // single-node failure points
Graph.biconnectedComponents(social); // maximal biconnected node regions
Graph.maximumBipartiteMatching(social); // [{ left, right, edge }], throws if not bipartite

// Directed only (THROWS GraphError on undirected):
Graph.stronglyConnectedComponents(dag); // Kosaraju's algorithm; Array<Array<NodeIndex>>
Graph.weaklyConnectedComponents(dag); // orientation ignored
Graph.isStronglyConnected(dag);
Graph.isWeaklyConnected(dag);
// In a DAG every node is its own SCC: three singleton components; output order is unspecified
```

`isAcyclic` is cached: fresh graphs are known-acyclic, the flag is invalidated when a mutation may change the answer (`addEdge` on a known-acyclic graph, removals on a known-cyclic graph) and unconditionally by `reverse`, and a computed result is memoized on the graph value. Repeated calls are cheap.

`unweightedDistances(graph, source, { direction })` returns hop counts to reachable nodes; `hasPath(graph, source, target, { direction })` is the allocation-light boolean query. Directed `maximumFlow` returns `{ value, flows, cut }`; `minimumCut` returns `{ value, edges, source, target }`. Flow capacities must be finite and non-negative, and source and target must be distinct.

## 9. Paths and Shortest Paths

Point-to-point algorithms return `Option.Option<Graph.PathResult<E>>` where `PathResult` is:

```ts
interface PathResult<E> {
	readonly path: Array<NodeIndex>; // ordered nodes, source first, target last
	readonly edges: Array<EdgeIndex>; // traversed edge indexes
	readonly distance: number; // total numeric cost
	readonly costs: Array<E>; // the EDGE DATA along the path — not numbers, unless E is number
}
```

The single-path algorithms below throw `GraphError` if `source` or `target` does not exist, and return `Option.none()` when the target is unreachable. A successful `source === target` result is `{ path: [source], edges: [], distance: 0, costs: [] }`, but validations still run: Dijkstra/A* validate edge costs, A* validates its heuristic, and Bellman-Ford still rejects a relevant negative cycle. Finite path arithmetic that overflows or underflows also throws `GraphError`: Dijkstra and A* reject distance overflow, A* also rejects priority overflow, and Bellman-Ford rejects distance overflow or underflow. Undirected graphs are traversed symmetrically regardless of stored edge orientation.

```ts
const weighted = Graph.directed<string, number>((m) => {
	const a = Graph.addNode(m, 'A');
	const b = Graph.addNode(m, 'B');
	const c = Graph.addNode(m, 'C');
	Graph.addEdge(m, a, b, 5);
	Graph.addEdge(m, a, c, 10);
	Graph.addEdge(m, b, c, 2);
});

// Dijkstra — non-negative weights only
const shortest = Graph.dijkstra(weighted, {
	source: 0,
	target: 2,
	cost: (edgeData) => edgeData
});
// Option.some({ path: [0, 1, 2], edges: [0, 2], distance: 7, costs: [5, 2] })

// A* — adds a heuristic over NODE data (estimate of remaining cost to target)
const grid = Graph.directed<{ x: number; y: number }, number>((m) => {
	const a = Graph.addNode(m, { x: 0, y: 0 });
	const b = Graph.addNode(m, { x: 1, y: 0 });
	const c = Graph.addNode(m, { x: 2, y: 0 });
	Graph.addEdge(m, a, b, 1);
	Graph.addEdge(m, b, c, 1);
});
const route = Graph.astar(grid, {
	source: 0,
	target: 2,
	cost: (edgeData) => edgeData,
	heuristic: (nodeData, targetData) =>
		Math.abs(nodeData.x - targetData.x) + Math.abs(nodeData.y - targetData.y)
});

// Bellman-Ford — negative weights allowed
const withNegatives = Graph.bellmanFord(weighted, {
	source: 0,
	target: 2,
	cost: (edgeData) => edgeData
});
// throws GraphError if a reachable negative cycle can affect the target

// Floyd-Warshall — ALL pairs; takes a bare cost FUNCTION, not a config object
const all = Graph.floydWarshall(weighted, (edgeData) => edgeData);
all.distances.get(0)?.get(2); // 7 (Infinity when unreachable)
all.paths.get(0)?.get(2); // [0, 1, 2] (null when unreachable, [i] when i === j)
all.edges.get(0)?.get(2); // [0, 2] — edge indexes along the path
all.costs.get(0)?.get(2); // [5, 2] — edge data along the path
```

Sharp edges (all verified in tests):

- `dijkstra` and `astar` validate **every edge weight in the graph eagerly** — any negative or `NaN` cost throws `GraphError` immediately, even when the offending edge is not on the path and even when `source === target`.
- In **undirected** graphs every edge is traversable in both directions, so a reachable negative edge forms a negative cycle: `bellmanFord` throws when that cycle can affect the target, and `floydWarshall` throws on any negative cycle.
- `floydWarshall` throws on any negative cycle in directed graphs too; it runs in O(V^3) — fine for hundreds of nodes, not tens of thousands.
- With parallel edges, `floydWarshall` uses the minimum weight between a pair.

`Graph.simplePaths(graph, { source, target, limit? })` lazily enumerates loop-free paths in DFS edge order with hop count as `distance`. `Graph.allShortestPaths(graph, { source, target, cost, limit? })` lazily enumerates every simple minimum-cost path; parallel edges remain distinct. Both return repeatable `PathWalker` values, can be exponentially large, and should normally receive a finite `limit`.

## 10. Equality, Hashing & Inspection

Graphs implement `Equal` and `Hash`. Equality compares kind, then active node and edge data **by index** using `Equal.equals` (works with `Data`/`Schema` classes and plain primitives, including `undefined` data):

```ts
import { Equal } from 'effect';

Equal.equals(graph1, graph2);
// true only if: same kind, same node indices with equal data,
// same edge indices with equal Edge values
```

Removed allocator history is ignored, and undirected edge endpoint orientation is ignored. Comparison is still index-keyed, so isomorphic graphs built with different active indexes are **not** equal; this is active indexed-structure equality, not graph isomorphism.

Inspection:

```ts
String(dag); // 'Graph(directed, 3, 2)'
dag.toJSON(); // { _id: 'Graph', nodeCount: 3, edgeCount: 2, type: 'directed' }

// The graph itself iterates node entries:
for (const [index, data] of dag) {
	console.log(index, data);
}
```

## 11. Visualization: GraphViz & Mermaid

Both exporters are dual, work on directed and undirected graphs, and return a `string`. All options are optional — `Graph.toMermaid(dag)` works as-is; labels default to `String(data)`, the GraphViz name to `'G'`, the Mermaid direction to `'TD'`, and shapes to rectangle:

```ts
// GraphViz DOT. Options: { nodeLabel?, edgeLabel?, graphName? }
const dot = Graph.toGraphViz(dag, {
	nodeLabel: (data) => `Task: ${data}`,
	edgeLabel: (w) => `w=${w}`,
	graphName: 'Pipeline' // default 'G'
});
// digraph for directed ('->'), graph for undirected ('--'); labels are quote-escaped

// Mermaid. Options: { nodeLabel?, edgeLabel?, diagramType?, direction?, nodeShape? }
const mermaid = Graph.toMermaid(dag, {
	nodeLabel: (data) => data,
	edgeLabel: (w) => String(w),
	direction: 'LR', // 'TB' | 'TD' (default) | 'BT' | 'RL' | 'LR'
	nodeShape: (data) => (data === 'A' ? 'stadium' : 'rectangle')
});
// diagramType auto-detects: 'flowchart' (directed, '-->') vs 'graph' (undirected, '---')
```

`MermaidNodeShape` values: `'rectangle' | 'rounded' | 'circle' | 'diamond' | 'hexagon' | 'stadium' | 'subroutine' | 'cylindrical'`. Mermaid labels are escaped for special characters automatically; empty edge labels render plain arrows.

## Key Patterns

### Dependency graph with task ordering

`findNode` is O(n), so keep your own key-to-index map while building:

```ts
import { Graph } from 'effect';

interface Task {
	readonly name: string;
}

const byName = new Map<string, Graph.NodeIndex>();

const tasks = Graph.directed<Task, void>((m) => {
	const add = (name: string) => {
		const index = Graph.addNode(m, { name });
		byName.set(name, index);
		return index;
	};
	const compile = add('compile');
	const test = add('test');
	const lint = add('lint');
	const release = add('release');
	// edge A -> B means "A must run before B"
	Graph.addEdge(m, compile, test, undefined);
	Graph.addEdge(m, compile, lint, undefined);
	Graph.addEdge(m, test, release, undefined);
	Graph.addEdge(m, lint, release, undefined);
});

if (!Graph.isAcyclic(tasks)) {
	// Diagnose: every SCC with more than one node is a dependency cycle
	const cycles = Graph.stronglyConnectedComponents(tasks).filter(
		(scc) => scc.length > 1
	);
	throw new Error(`Dependency cycles: ${JSON.stringify(cycles)}`);
}

const executionOrder = Array.from(
	Graph.topo(tasks).visit((_, task) => task.name)
);
// ['compile', 'test', 'lint', 'release'] (or another valid topological order)
```

### Reachability and impact analysis

```ts
// Everything DOWNSTREAM of a node (what breaks if it changes):
const impacted = new Set(
	Graph.indices(Graph.dfs(tasks, { start: [byName.get('compile')!] }))
);

// Everything UPSTREAM of a node (its transitive prerequisites):
const prerequisites = new Set(
	Graph.indices(
		Graph.dfs(tasks, { start: [byName.get('release')!], direction: 'incoming' })
	)
);

// Entry points and leaves:
const roots = Array.from(Graph.indices(Graph.externals(tasks, { direction: 'incoming' })));
const leaves = Array.from(Graph.indices(Graph.externals(tasks, { direction: 'outgoing' })));
```

### Weighted routing with fallback

```ts
import { Graph, Option } from 'effect';

interface Link {
	readonly latencyMs: number;
}

const route = (
	network: Graph.UndirectedGraph<string, Link>,
	from: Graph.NodeIndex,
	to: Graph.NodeIndex
): Array<Graph.NodeIndex> =>
	Graph.dijkstra(network, {
		source: from,
		target: to,
		cost: (link) => link.latencyMs
	}).pipe(
		Option.map((result) => result.path),
		Option.getOrElse(() => [])
	);
```

### Wrapping throwing operations in Effect

Graph operations throw `GraphError` synchronously. Inside effectful code, capture them with `Effect.try` (the thrown value already is a tagged error; see the effect-error-handling skill for the broader strategy):

```ts
import { Effect, Graph } from 'effect';

const topoOrder = (g: Graph.DirectedGraph<string, number>) =>
	Effect.try({
		try: () => Array.from(Graph.indices(Graph.topo(g))),
		catch: (error) => error as Graph.GraphError
	});
// Effect<Array<Graph.NodeIndex>, Graph.GraphError>
```

### Derive a filtered subgraph view

```ts
// Keep only the active subset; incident edges of removed nodes are dropped automatically
const activeOnly = Graph.mutate(deployments, (m) => {
	Graph.filterNodes(m, (service) => service.status === 'active');
});
const clusters = Graph.connectedComponents(activeOnly); // undirected graphs
```

## Common Mistakes

1. **Calling `addNode`/`addEdge` on an immutable `Graph`** — write APIs require a `MutableGraph`, obtained only via the constructor callback, `Graph.mutate`, or `beginMutation`. The types reject it; restructure into a `mutate` scope.
2. **Expecting Effect-returning APIs** — the whole module is synchronous. Failures **throw** `GraphError` (`addEdge` with a missing endpoint, `topo` on cyclic/undirected graphs, `dijkstra`/`astar` on negative weights, missing traversal start nodes); lookups return `Option`. Wrap with `Effect.try` when inside effectful code.
3. **Passing `{ cost }` to `floydWarshall`** — it takes a bare cost function: `Graph.floydWarshall(graph, (edgeData) => edgeData)`. Only `dijkstra`/`astar`/`bellmanFord` take a `{ source, target, cost }` config object.
4. **Consuming a Walker as if it yielded indices** — `dfs`/`bfs`/`topo`/`nodes` walkers yield `[index, data]` tuples. Use `Graph.indices(w)`, `Graph.values(w)`, `Graph.entries(w)`, or `w.visit((i, d) => ...)` to project.
5. **Expecting traversals to cover the whole graph by default** — omitting `start` yields an empty iterator. Seed every component explicitly (`start: [a, b]`), or use `Graph.nodes` for plain enumeration.
6. **Using `neighborsDirected`** — deprecated in 4.0. Use `Graph.successors` (outgoing) / `Graph.predecessors` (incoming); all three throw `GraphError` on undirected graphs — use `Graph.neighbors` there.
7. **Reusing a `MutableGraph` after `endMutation`** — finalization is terminal; later public writes throw `GraphError`. Use `Graph.mutate`, which scopes and finalizes the handle for you.
8. **Assuming a negative weight is fine if it is off the path** — `dijkstra` and `astar` validate every edge weight in the graph up front and throw `GraphError` for any negative/`NaN` cost, even when `source === target`. Use `bellmanFord` for negative weights.
9. **Negative edges in undirected graphs** — each undirected edge is traversable both ways, so a reachable negative edge forms a negative cycle: `bellmanFord` throws when it can affect the target, and `floydWarshall` throws.
10. **Treating `Equal.equals` as graph isomorphism** — equality is index-keyed. Same structure built in a different order (different indices) compares unequal.
11. **Reading `PathResult.costs` as numbers** — `costs` holds the original edge data `E` along the path, not the output of your cost function. `distance` is the numeric total.
12. **Treating `NodeIndex` as an array offset** — indices are stable identifiers; after removals they are sparse and never reused, so `nodeCount` is not `max index + 1`. Iterate via `Graph.nodes`/`Graph.indices` instead of counting up.
13. **Relying on `updateNode`/`removeNode` to signal missing indices** — `updateNode`, `updateEdge`, `removeNode`, and `removeEdge` are silent no-ops for nonexistent indices; use `hasNode` for node indexes and `getEdge` for edge indexes if absence is a bug (`hasEdge` checks a source-target pair, not an edge index).
14. **Passing `initials` with incoming edges to `topo`** — `initials` must be zero in-degree nodes; others throw `GraphError` when iteration starts. `initials` only prioritizes queue order — every node is still emitted exactly once.
15. **Using `graph.toJSON()` as persistence** — it only returns `{ _id, nodeCount, edgeCount, type }`. Use `Graph.toSnapshot` / `Graph.fromSnapshot`, or `Schema.Graph` at a decoded boundary.
16. **Mutating from a graph callback** — transformation callbacks, cost/capacity/heuristic functions, and walker projections may query but must not mutate or finalize the same mutable graph.