Skip to content
Skills Library
Programming · Analysis

effect-graph

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

Licence
MIT
Last repository change
02.11.2026

Assessment and security

95/ 100Class: good
Format25 / 25
Frontmatter with name and description, valid name, description up to 1,024 characters, name matching the folder.
Discoverability25 / 25
Description explains when to use the skill, has a reasonable length and uses third person.
Content30 / 35
At least 150 words and at most 500 lines, headings, step lists, examples or code.
Hygiene15 / 15
No placeholders such as TODO, no Windows paths, with a licence.
Riskno signals detected in the scan
Files in this package
1
Scripts
0
HTML comments
4
URLs in SKILL.md
0
Deprecation

No signals detected. Repository changed on 02.11.2026, without references to retired models or APIs.

Licence

MIT, open: use and modify while retaining author attribution.

What to check before installing
  • SKILL.md zawiera komentarze HTML (4). Nie widać ich w podglądzie Markdown, a model je czyta.

What it does and when to use it

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.

Original author description

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.

How it works

  1. Effect Source Reference
  2. Core Model
  3. 1. Creating Graphs
  4. 2. Mutation: Scoped Writes
  5. 3. Node & Edge Queries
  6. 4. Bulk Transformations
  7. 5. Set Operations and Derived Graphs
  8. 6. Walkers: Lazy Iterators
  9. 7. Traversals: DFS, BFS, Postorder, Topological
  10. 8. Structure Analysis, Connectivity, Matching, and Flow
Original SKILL.md headings · 596 lines, 4,216 words
SKILL.md preview
---
name: effect-graph
description: 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.
---

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

## Effect Source Reference

Baseline: **Effect 4.1.0**. The source checkout is at
`~/.local/share/opencode/repos/github.com/Effect-TS/effect@main/`.
Read exact-tag files with `git show effect@4.1.0:<path>`; main may be newer.

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:

<!-- typecheck -->
```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. Distance
  computation is O(V³); immutable path witnesses can require O(V³) working
  storage, in addition to reconstructed paths. It is not a quadratic-storage
  algorithm. Reconstruction removes repeated nodes and no longer loops on
  zero-cost cycles after floating-point rounding.
- 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:

<!-- typecheck -->
```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 multi-node cycles; check self-loops separately if allowed.
	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

Continue with `tasks` and `byName` from the example above:

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

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

// Everything UPSTREAM of a node (its transitive prerequisites):
const prerequisites = new Set(
	Graph.indices(
		Graph.dfs(tasks, {
			start: Option.toArray(Option.fromNullishOr(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' })));
```

These lookups intentionally yield an empty traversal when a name is absent.
If a missing task is an error, handle the `None` branch with a typed failure
before constructing the traversal instead.

### Weighted routing with fallback

<!-- typecheck -->
```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):

<!-- typecheck -->
```ts
import { Effect, Graph } from 'effect';

const topoOrder = Effect.fn('Graph.topoOrder')((g: Graph.DirectedGraph<string, number>) =>
	Effect.try({
		try: () => Array.from(Graph.indices(Graph.topo(g))),
		catch: (error) => error
	}).pipe(
		Effect.catch((error) => error instanceof Graph.GraphError
			? Effect.fail(error)
			: Effect.die(error))
	)
);
// 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.

Versions

RepositoryScoreLicence
This page · mpsuesser/opencode-effect-enforcer95MIT
mpsuesser/opencode-effect-enforcer95MIT

Database snapshot: 13.11.2026 · package version 2fbfbef49e90 (SHA-256 digest of the entire package)

Downloads in the last 30 days: 0 · ranking

Report a problem with this skill: harmful content, incorrect descriptions or an author’s removal request.

Similar skills

  • 100graph-algorithms
    Reference patterns for graph algorithm problems including BFS, DFS, Dijkstra, topological sort, union-find, MST, Bellman-Ford, and bipartite checking. Provides recognition signals, Python templates, edge cases, and common mistakes for each technique. Use when solving problems…
  • 100dsa-graphs-bfs-dfs-topological-sort
    Use this skill when traversing network graphs, finding shortest paths in unweighted graphs, detecting cycles, or determining build orders.
  • 100graph-algorithms-interviewer
    A mid-level software engineering interviewer specializing in graph algorithms. Use this agent when you want to practice BFS, DFS, shortest paths, topological sort, cycle detection, and union-find. It provides progressive hints, ASCII graph visualizations, and structured feedback…
  • 100graph-algorithms
    Use when working with graph problems including traversal, shortest paths, minimum spanning trees, topological sorting, and connectivity analysis. Covers BFS, DFS, Dijkstra, Bellman-Ford, Floyd-Warshall, Prim, Kruskal, Tarjan, Kosaraju, A*, and Union-Find. Based on Knuth's TAOCP.…
  • 80role-algorithms:graph-algorithms
    Implements graph algorithms — BFS/DFS traversal, shortest paths (Dijkstra, Bellman-Ford, Floyd-Warshall, A*, Johnson's), minimum spanning trees (Kruskal, Prim), topological sort, strongly connected components (Tarjan, Kosaraju), maximum flow (Ford-Fulkerson, Dinic), and…
  • 100dsa-graphs-dijkstra-shortest-path-union-find
    Use this skill when computing shortest paths in weighted non-negative graphs and managing dynamic connectivity with Union-Find.

Feedback and reports

Your message goes to Bartosz Sokoliński. An email address is needed only for a reply. See the privacy policy.