Graph

The Graph module models relationships between indexed nodes and edges. A graph can be directed or undirected, stores user-defined data on both nodes (N) and edges (E), and ships with traversals, structural analysis, shortest-path algorithms, and diagram export.

The mental model:

• Nodes and edges are addressed by stable numeric identifiers: NodeIndex and EdgeIndex.
• A Graph value is an immutable snapshot. To change it you open a MutableGraph inside a mutation scope (mutate, or beginMutation / endMutation, or a constructor callback), batch your edits, then read the new immutable graph back out.
• Directed graphs follow edge direction for neighbors and traversals; undirected graphs treat each edge as connecting both endpoints.
• Missing lookups return Option. Structurally invalid operations (adding an edge to a missing node, a negative weight under Dijkstra, sorting a cyclic graph) throw a GraphError.

Common case: build a graph, then read it

directed (and undirected) accept an optional callback that receives a MutableGraph. Add nodes with addNode — each returns its NodeIndex — then connect them with addEdge. When the callback returns you get back an immutable graph.

import { Graph } from "effect"

// A directed dependency graph: each edge "X -> Y" means X depends on Y.
const deps = Graph.directed<string, string>((mutable) => {
  const app = Graph.addNode(mutable, "app")
  const ui = Graph.addNode(mutable, "ui")
  const core = Graph.addNode(mutable, "core")
  const utils = Graph.addNode(mutable, "utils")

  Graph.addEdge(mutable, app, ui, "imports")
  Graph.addEdge(mutable, app, core, "imports")
  Graph.addEdge(mutable, ui, core, "imports")
  Graph.addEdge(mutable, core, utils, "imports")
})

console.log(Graph.nodeCount(deps)) // => 4
console.log(Graph.edgeCount(deps)) // => 4

Topological order (a build order)

topo yields nodes in topological order using Kahn’s algorithm. Wrap it with values (or indices / entries) to choose what each step produces.

import { Graph } from "effect"

const deps = Graph.directed<string, string>((mutable) => {
  const app = Graph.addNode(mutable, "app")
  const ui = Graph.addNode(mutable, "ui")
  const core = Graph.addNode(mutable, "core")
  const utils = Graph.addNode(mutable, "utils")
  Graph.addEdge(mutable, app, ui, "imports")
  Graph.addEdge(mutable, app, core, "imports")
  Graph.addEdge(mutable, ui, core, "imports")
  Graph.addEdge(mutable, core, utils, "imports")
})

// Dependents come before their dependencies in this orientation.
const order = Array.from(Graph.values(Graph.topo(deps)))
console.log(order) // => ["app", "ui", "core", "utils"]

Because Graph is immutable, you can also mutate an existing graph without disturbing the original. mutate opens a scope, applies your edits to a copy, and returns a fresh immutable graph:

import { Graph } from "effect"

const base = Graph.directed<string, string>((m) => {
  Graph.addNode(m, "app")
})

const extended = Graph.mutate(base, (m) => {
  const lib = Graph.addNode(m, "lib")
  Graph.addEdge(m, 0, lib, "imports")
})

console.log(Graph.nodeCount(base)) // => 1 (unchanged)
console.log(Graph.nodeCount(extended)) // => 2

Shortest path with Dijkstra

Shortest-path algorithms take a cost function mapping each edge’s data to a numeric weight. dijkstra requires non-negative weights and returns an Option<PathResult> (none when the target is unreachable).

import { Graph, Option } from "effect"

const roads = 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) // A -> B costs 5
  Graph.addEdge(m, a, c, 10) // A -> C costs 10
  Graph.addEdge(m, b, c, 2) // B -> C costs 2
})

const result = Graph.dijkstra(roads, {
  source: 0,
  target: 2,
  cost: (weight) => weight
})

if (Option.isSome(result)) {
  console.log(result.value.path) // => [0, 1, 2]  (A -> B -> C)
  console.log(result.value.distance) // => 7
  console.log(result.value.costs) // => [5, 2]   (edge data along the path)
}

Visualizing a graph

toMermaid and toGraphViz render a graph as diagram-as-code text. Mermaid output can be embedded directly in Markdown:

import { Graph } from "effect"

const deps = Graph.directed<string, string>((m) => {
  const app = Graph.addNode(m, "App")
  const db = Graph.addNode(m, "Database")
  const cache = Graph.addNode(m, "Cache")
  Graph.addEdge(m, app, db, "reads")
  Graph.addEdge(m, app, cache, "reads")
})

console.log(Graph.toMermaid(deps))

produces:

flowchart TD
  0["App"]
  1["Database"]
  2["Cache"]
  0 -->|"reads"| 1
  0 -->|"reads"| 2

---

Reference

Every algorithm-flavored example below reuses one tiny graph so the indices stay predictable:

import { Graph } from "effect"

// Nodes: 0=A 1=B 2=C ; Edges: A->B (1), B->C (2), A->C (4)
const g = 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, 1)
  Graph.addEdge(m, b, c, 2)
  Graph.addEdge(m, a, c, 4)
})

Types & errors

NodeIndex

A number identifying a node. Allocated by addNode; identifiers are not reused after removals (so a NodeIndex is an identity, not an array offset).

import { Graph } from "effect"

let id!: Graph.NodeIndex
Graph.directed<string, never>((m) => {
  id = Graph.addNode(m, "A")
})
console.log(id) // => 0

EdgeIndex

A number identifying an edge. Allocated by addEdge; like node identifiers, edge identifiers are never reused after a removal.

import { Graph } from "effect"

let edge!: Graph.EdgeIndex
Graph.directed<string, number>((m) => {
  const a = Graph.addNode(m, "A")
  const b = Graph.addNode(m, "B")
  edge = Graph.addEdge(m, a, b, 1)
})
console.log(edge) // => 0

Edge

The value returned for an edge: a Data.Class carrying source, target, and data. Returned by getEdge and as the value of an EdgeWalker.

import { Graph, Option } from "effect"

const edge = Graph.getEdge(g, 0)
console.log(Option.isSome(edge) && edge.value.source) // => 0
console.log(Option.isSome(edge) && edge.value.target) // => 1
console.log(Option.isSome(edge) && edge.value.data) // => 1

Kind

The string literal union "directed" | "undirected" used as the third type parameter of Graph / MutableGraph to preserve directedness in graph-generic code.

import type { Graph } from "effect"

type K = Graph.Kind // "directed" | "undirected"

Graph

The immutable graph interface, Graph<N, E, T extends Kind = "directed">. Read, traverse, and analyze through it; it is never mutated directly.

import type { Graph } from "effect"

declare const value: Graph.Graph<string, number> // immutable, directed by default

MutableGraph

The mutable graph interface, MutableGraph<N, E, T>. You only ever hold one inside a mutation scope; all mutating operations (addNode, addEdge, removeNode, updateNode, …) require it.

import { Graph } from "effect"

Graph.directed<string, number>((mutable: Graph.MutableDirectedGraph<string, number>) => {
  Graph.addNode(mutable, "A")
})

DirectedGraph

Alias for Graph<N, E, "directed">. Use when edge direction is part of the model.

import type { Graph } from "effect"

declare const dag: Graph.DirectedGraph<string, number>

UndirectedGraph

Alias for Graph<N, E, "undirected">. Each edge connects both endpoints with no source-to-target direction.

import type { Graph } from "effect"

declare const social: Graph.UndirectedGraph<string, string>

MutableDirectedGraph

Alias for MutableGraph<N, E, "directed"> — the mutable counterpart of DirectedGraph.

import type { Graph } from "effect"

declare const m: Graph.MutableDirectedGraph<string, number>

MutableUndirectedGraph

Alias for MutableGraph<N, E, "undirected"> — the mutable counterpart of UndirectedGraph.

import type { Graph } from "effect"

declare const m: Graph.MutableUndirectedGraph<string, string>

Direction

"outgoing" | "incoming". Selects which edges to follow during traversal and in neighborsDirected / externals.

import { Graph } from "effect"

console.log(Graph.neighborsDirected(g, 2, "incoming")) // => [1, 0]  (predecessors of C)

GraphError

A Data.TaggedError (tag "GraphError") thrown by operations that hit invalid structure: referencing a missing node, sorting a cyclic graph, negative weights under Dijkstra/A*, or negative cycles in Floyd-Warshall.

import { Graph } from "effect"

try {
  Graph.mutate(g, (m) => {
    Graph.addEdge(m, 0, 999, 1) // node 999 does not exist
  })
} catch (e) {
  console.log((e as Graph.GraphError)._tag) // => "GraphError"
}

isGraph

Type guard narrowing an unknown value to Graph. It checks the shared runtime identifier and does not distinguish immutable from mutable graphs.

import { Graph } from "effect"

console.log(Graph.isGraph(g)) // => true
console.log(Graph.isGraph({})) // => false

Construction & mutation

directed

Creates a directed graph. With no argument you get an empty immutable graph; pass a callback to seed it with nodes and edges.

import { Graph } from "effect"

const empty = Graph.directed<string, number>()
console.log(Graph.nodeCount(empty)) // => 0

undirected

Creates an undirected graph. Each addEdge registers the connection for both endpoints, so neighbors sees the edge from either side.

import { Graph } from "effect"

const u = Graph.undirected<string, string>((m) => {
  const a = Graph.addNode(m, "A")
  const b = Graph.addNode(m, "B")
  Graph.addEdge(m, a, b, "A-B")
})
console.log(Graph.neighbors(u, 1)) // => [0]  (B sees A even though edge was A->B)

beginMutation

Opens a mutation scope by copying the graph into a MutableGraph. Pair it with endMutation. Use this when you need control over the scope boundaries; for the common case prefer mutate.

import { Graph } from "effect"

const mutable = Graph.beginMutation(g)
Graph.addNode(mutable, "D")
const next = Graph.endMutation(mutable)
console.log(Graph.nodeCount(next)) // => 4

endMutation

Closes a mutation scope, producing a fresh immutable graph from a MutableGraph.

import { Graph } from "effect"

const mutable = Graph.beginMutation(Graph.directed<string, never>())
Graph.addNode(mutable, "only")
console.log(Graph.nodeCount(Graph.endMutation(mutable))) // => 1

mutate

Runs a callback in a fresh mutation scope and returns the resulting immutable graph. The original is untouched. Both data-first and data-last (pipeable) forms exist.

import { Graph } from "effect"

const bigger = Graph.mutate(g, (m) => {
  const d = Graph.addNode(m, "D")
  Graph.addEdge(m, 2, d, 1)
})
console.log(Graph.nodeCount(bigger)) // => 4
console.log(Graph.nodeCount(g)) // => 3 (unchanged)

Nodes

addNode

Adds a node to a mutable graph and returns its freshly allocated NodeIndex.

import { Graph } from "effect"

Graph.directed<string, never>((m) => {
  console.log(Graph.addNode(m, "first")) // => 0
  console.log(Graph.addNode(m, "second")) // => 1
})

getNode

Reads a node’s data by index, returning Option<N>.

import { Graph } from "effect"

console.log(Graph.getNode(g, 1)) // => Option.some("B")
console.log(Graph.getNode(g, 99)) // => Option.none()

hasNode

Returns whether a node index exists in the graph.

import { Graph } from "effect"

console.log(Graph.hasNode(g, 0)) // => true
console.log(Graph.hasNode(g, 99)) // => false

nodeCount

The number of nodes in the graph.

import { Graph } from "effect"

console.log(Graph.nodeCount(g)) // => 3

updateNode

Transforms a single node’s data in place (mutable graph only). A no-op if the index is missing.

import { Graph } from "effect"

const upper = Graph.mutate(g, (m) => {
  Graph.updateNode(m, 0, (data) => data.toLowerCase())
})
console.log(Graph.getNode(upper, 0)) // => Option.some("a")

removeNode

Removes a node and all of its incident edges (mutable graph only).

import { Graph } from "effect"

const without = Graph.mutate(g, (m) => {
  Graph.removeNode(m, 1) // drops B and edges A->B, B->C
})
console.log(Graph.nodeCount(without)) // => 2
console.log(Graph.edgeCount(without)) // => 1  (only A->C remains)

findNode

Returns the NodeIndex of the first node whose data matches a predicate, or Option.none().

import { Graph } from "effect"

console.log(Graph.findNode(g, (d) => d === "C")) // => Option.some(2)
console.log(Graph.findNode(g, (d) => d === "Z")) // => Option.none()

findNodes

Returns every NodeIndex whose data matches a predicate.

import { Graph } from "effect"

console.log(Graph.findNodes(g, (d) => d !== "A")) // => [1, 2]

mapNodes

Replaces every node’s data via a mapping function (mutable graph only). Indices and edges are preserved.

import { Graph } from "effect"

const lower = Graph.mutate(g, (m) => Graph.mapNodes(m, (d) => d.toLowerCase()))
console.log(Array.from(Graph.values(Graph.nodes(lower)))) // => ["a", "b", "c"]

filterNodes

Removes nodes that fail the predicate (mutable graph only); their incident edges are removed too.

import { Graph } from "effect"

const kept = Graph.mutate(g, (m) => Graph.filterNodes(m, (d) => d !== "B"))
console.log(Graph.nodeCount(kept)) // => 2
console.log(Graph.edgeCount(kept)) // => 1  (A->C survives; A->B and B->C removed)

filterMapNodes

Filters and transforms in one pass: nodes mapped to Option.none() are removed (with their edges), Option.some(value) updates the data (mutable graph only).

import { Graph, Option } from "effect"

const result = Graph.mutate(g, (m) =>
  Graph.filterMapNodes(m, (d) =>
    d === "A" ? Option.none() : Option.some(`${d}!`)
  )
)
console.log(Array.from(Graph.values(Graph.nodes(result)))) // => ["B!", "C!"]

Edges

addEdge

Connects two existing nodes in a mutable graph, stores edge data, and returns the new EdgeIndex. Throws GraphError if either endpoint is missing. In undirected graphs the edge is registered for both endpoints.

import { Graph } from "effect"

Graph.directed<string, number>((m) => {
  const a = Graph.addNode(m, "A")
  const b = Graph.addNode(m, "B")
  console.log(Graph.addEdge(m, a, b, 42)) // => 0
})

getEdge

Reads an edge by index, returning Option<Edge<E>>.

import { Graph, Option } from "effect"

const e = Graph.getEdge(g, 1)
console.log(Option.isSome(e) && e.value.data) // => 2  (the B->C edge)

hasEdge

Returns whether a directed edge exists from source to target.

import { Graph } from "effect"

console.log(Graph.hasEdge(g, 0, 1)) // => true   (A->B)
console.log(Graph.hasEdge(g, 1, 0)) // => false  (no B->A)

edgeCount

The number of edges in the graph.

import { Graph } from "effect"

console.log(Graph.edgeCount(g)) // => 3

updateEdge

Transforms a single edge’s data in place (mutable graph only). A no-op if the index is missing.

import { Graph, Option } from "effect"

const doubled = Graph.mutate(g, (m) => Graph.updateEdge(m, 0, (d) => d * 10))
const e = Graph.getEdge(doubled, 0)
console.log(Option.isSome(e) && e.value.data) // => 10

removeEdge

Removes an edge by index (mutable graph only). Endpoints remain.

import { Graph } from "effect"

const fewer = Graph.mutate(g, (m) => Graph.removeEdge(m, 2)) // drop A->C
console.log(Graph.edgeCount(fewer)) // => 2

findEdge

Returns the EdgeIndex of the first edge whose (data, source, target) matches a predicate.

import { Graph } from "effect"

console.log(Graph.findEdge(g, (data) => data >= 2)) // => Option.some(1)

findEdges

Returns every matching EdgeIndex.

import { Graph } from "effect"

console.log(Graph.findEdges(g, (data) => data >= 2)) // => [1, 2]

mapEdges

Replaces every edge’s data via a mapping function (mutable graph only).

import { Graph, Option } from "effect"

const negated = Graph.mutate(g, (m) => Graph.mapEdges(m, (d) => -d))
const e = Graph.getEdge(negated, 0)
console.log(Option.isSome(e) && e.value.data) // => -1

filterEdges

Removes edges that fail the predicate (mutable graph only); nodes are untouched.

import { Graph } from "effect"

const heavy = Graph.mutate(g, (m) => Graph.filterEdges(m, (d) => d >= 2))
console.log(Graph.edgeCount(heavy)) // => 2  (edge with data 1 removed)

filterMapEdges

Filters and transforms edges in one pass: Option.none() removes the edge, Option.some(value) updates its data (mutable graph only).

import { Graph, Option } from "effect"

const result = Graph.mutate(g, (m) =>
  Graph.filterMapEdges(m, (d) => (d >= 2 ? Option.some(d * 100) : Option.none()))
)
console.log(Graph.edgeCount(result)) // => 2
console.log(
  Array.from(Graph.values(Graph.edges(result))).map((e) => e.data)
) // => [200, 400]

Structure & queries

reverse

Swaps source/target on every edge and rebuilds adjacency (mutable graph only), reversing all directions.

import { Graph } from "effect"

const flipped = Graph.mutate(g, (m) => Graph.reverse(m))
console.log(Graph.hasEdge(flipped, 1, 0)) // => true   (was A->B, now B->A)
console.log(Graph.hasEdge(flipped, 0, 1)) // => false

neighbors

Returns the neighboring node indices. For directed graphs these are the targets of outgoing edges; for undirected graphs, the other endpoint of every incident edge.

import { Graph } from "effect"

console.log(Graph.neighbors(g, 0)) // => [1, 2]  (A -> B, A -> C)
console.log(Graph.neighbors(g, 2)) // => []      (C has no outgoing edges)

neighborsDirected

Like neighbors but you pick the Direction: "outgoing" follows edge targets, "incoming" returns predecessors.

import { Graph } from "effect"

console.log(Graph.neighborsDirected(g, 2, "incoming")) // => [1, 0]  (B, A point to C)
console.log(Graph.neighborsDirected(g, 0, "outgoing")) // => [1, 2]

externals

A NodeWalker over boundary nodes. With direction: "outgoing" (default) it yields nodes with no outgoing edges (sinks + isolated); with "incoming", nodes with no incoming edges (sources + isolated). See ExternalsConfig.

import { Graph } from "effect"

console.log(Array.from(Graph.indices(Graph.externals(g)))) // => [2]  (C is the only sink)
console.log(
  Array.from(Graph.indices(Graph.externals(g, { direction: "incoming" })))
) // => [0]  (A is the only source)

ExternalsConfig

{ direction?: Direction }. Configures which missing edge direction makes a node “external”. Defaults to "outgoing".

import type { Graph } from "effect"

const sources: Graph.ExternalsConfig = { direction: "incoming" }

nodes

A NodeWalker over all nodes in insertion order, regardless of connectivity.

import { Graph } from "effect"

console.log(Array.from(Graph.entries(Graph.nodes(g)))) // => [[0, "A"], [1, "B"], [2, "C"]]

edges

An EdgeWalker over all edges in insertion order. Each value is an Edge.

import { Graph } from "effect"

console.log(Array.from(Graph.indices(Graph.edges(g)))) // => [0, 1, 2]

Traversal

Traversal and listing APIs return a lazy Walker. You decide what each step yields by wrapping it with indices, values, or entries, or by calling walker.visit(...).

Walker

A lazy Iterable<[index, data]> wrapper with a visit method that maps each (index, data) pair, skipping elements that no longer exist in the graph.

import { Graph } from "effect"

const walker = Graph.dfs(g, { start: [0] })
const labels = Array.from(walker.visit((index, data) => `${index}:${data}`))
console.log(labels) // => ["0:A", "1:B", "2:C"]

NodeWalker

Walker<NodeIndex, N> — returned by dfs, bfs, dfsPostOrder, topo, nodes, and externals.

import type { Graph } from "effect"

const w: Graph.NodeWalker<string> = Graph.nodes(g)

EdgeWalker

Walker<EdgeIndex, Edge<E>> — returned by edges. Each value carries the full Edge.

import { Graph } from "effect"

const w: Graph.EdgeWalker<number> = Graph.edges(g)
console.log(Array.from(Graph.values(w)).map((e) => e.data)) // => [1, 2, 4]

indices

Iterates just the indices of a walker.

import { Graph } from "effect"

console.log(Array.from(Graph.indices(Graph.dfs(g, { start: [0] })))) // => [0, 1, 2]

values

Iterates just the data of a walker.

import { Graph } from "effect"

console.log(Array.from(Graph.values(Graph.dfs(g, { start: [0] })))) // => ["A", "B", "C"]

entries

Iterates [index, data] pairs of a walker.

import { Graph } from "effect"

console.log(Array.from(Graph.entries(Graph.bfs(g, { start: [0] }))))
// => [[0, "A"], [1, "B"], [2, "C"]]

dfs

A lazy depth-first NodeWalker from the configured start nodes (see SearchConfig). With no start the walker is empty. Throws GraphError if a start node is missing.

import { Graph } from "effect"

console.log(Array.from(Graph.indices(Graph.dfs(g, { start: [0] })))) // => [0, 1, 2]

bfs

A lazy breadth-first NodeWalker from the configured start nodes.

import { Graph } from "effect"

console.log(Array.from(Graph.indices(Graph.bfs(g, { start: [0] })))) // => [0, 1, 2]

dfsPostOrder

A depth-first postorder NodeWalker: a node is emitted only after its reachable descendants.

import { Graph } from "effect"

// From A: descendants emitted before A itself.
console.log(Array.from(Graph.indices(Graph.dfsPostOrder(g, { start: [0] })))) // => [2, 1, 0]

topo

A topological-order NodeWalker via Kahn’s algorithm. Throws GraphError if the graph is cyclic. See TopoConfig to seed specific initials.

import { Graph } from "effect"

console.log(Array.from(Graph.indices(Graph.topo(g)))) // => [0, 1, 2]

SearchConfig

{ start?: Array<NodeIndex>; direction?: Direction }. Configures dfs, bfs, and dfsPostOrder. direction defaults to "outgoing"; following "incoming" walks edges backwards.

import { Graph } from "effect"

const cfg: Graph.SearchConfig = { start: [2], direction: "incoming" }
console.log(Array.from(Graph.indices(Graph.dfs(g, cfg)))) // => [2, 1, 0]

TopoConfig

{ initials?: Array<NodeIndex> }. Seeds the topological sort with specific starting nodes instead of every zero in-degree node.

import type { Graph } from "effect"

const cfg: Graph.TopoConfig = { initials: [0] }

Algorithms

isAcyclic

Returns whether the graph contains no cycles (uses DFS back-edge detection; the result is cached on the graph).

import { Graph } from "effect"

console.log(Graph.isAcyclic(g)) // => true

const cyclic = Graph.directed<string, number>((m) => {
  const a = Graph.addNode(m, "A")
  const b = Graph.addNode(m, "B")
  Graph.addEdge(m, a, b, 1)
  Graph.addEdge(m, b, a, 1)
})
console.log(Graph.isAcyclic(cyclic)) // => false

isBipartite

Returns whether an undirected graph can be 2-colored (BFS coloring). Odd cycles are not bipartite.

import { Graph } from "effect"

const path = Graph.undirected<string, string>((m) => {
  const a = Graph.addNode(m, "A")
  const b = Graph.addNode(m, "B")
  const c = Graph.addNode(m, "C")
  Graph.addEdge(m, a, b, "e")
  Graph.addEdge(m, b, c, "e")
})
console.log(Graph.isBipartite(path)) // => true

const triangle = Graph.undirected<string, string>((m) => {
  const a = Graph.addNode(m, "A")
  const b = Graph.addNode(m, "B")
  const c = Graph.addNode(m, "C")
  Graph.addEdge(m, a, b, "e")
  Graph.addEdge(m, b, c, "e")
  Graph.addEdge(m, c, a, "e")
})
console.log(Graph.isBipartite(triangle)) // => false

connectedComponents

For an undirected graph, returns the node indices grouped by connected component.

import { Graph } from "effect"

const forest = Graph.undirected<string, string>((m) => {
  const a = Graph.addNode(m, "A")
  const b = Graph.addNode(m, "B")
  const c = Graph.addNode(m, "C")
  const d = Graph.addNode(m, "D")
  Graph.addEdge(m, a, b, "e") // component {A, B}
  Graph.addEdge(m, c, d, "e") // component {C, D}
})
console.log(Graph.connectedComponents(forest)) // => [[0, 1], [2, 3]]

stronglyConnectedComponents

For a directed graph, returns SCCs via Kosaraju’s algorithm. Nodes in the same SCC can all reach each other.

import { Graph } from "effect"

const cyclic = Graph.directed<string, string>((m) => {
  const a = Graph.addNode(m, "A")
  const b = Graph.addNode(m, "B")
  const c = Graph.addNode(m, "C")
  Graph.addEdge(m, a, b, "e")
  Graph.addEdge(m, b, c, "e")
  Graph.addEdge(m, c, a, "e") // A, B, C form one SCC
})
console.log(Graph.stronglyConnectedComponents(cyclic)) // => [[0, 1, 2]]

dijkstra

Single-source shortest path with non-negative edge costs. Returns Option<PathResult> (none if unreachable). Throws GraphError on a missing endpoint or a negative weight. See DijkstraConfig.

import { Graph, Option } from "effect"

const result = Graph.dijkstra(g, { source: 0, target: 2, cost: (w) => w })
console.log(Option.isSome(result) && result.value.distance) // => 3  (A->B->C beats A->C=4)
console.log(Option.isSome(result) && result.value.path) // => [0, 1, 2]

DijkstraConfig

{ source: NodeIndex; target: NodeIndex; cost: (edgeData: E) => number }.

import type { Graph } from "effect"

const cfg: Graph.DijkstraConfig<number> = {
  source: 0,
  target: 2,
  cost: (w) => w
}

PathResult

The success shape for dijkstra / astar / bellmanFord: { path: Array<NodeIndex>; distance: number; costs: Array<E> }. costs holds the original edge data along the path, not the numeric cost.

import { Graph, Option } from "effect"

const r = Graph.dijkstra(g, { source: 0, target: 2, cost: (w) => w })
if (Option.isSome(r)) {
  const result: Graph.PathResult<number> = r.value
  console.log(result.costs) // => [1, 2]
}

floydWarshall

All-pairs shortest paths in O(V³). Negative weights are allowed; a GraphError is thrown if a negative cycle is detected. Returns AllPairsResult.

import { Graph } from "effect"

const all = Graph.floydWarshall(g, (w) => w)
console.log(all.distances.get(0)?.get(2)) // => 3   (A->B->C)
console.log(all.paths.get(0)?.get(2)) // => [0, 1, 2]

AllPairsResult

The floydWarshall output: distances, paths, and costs, each a nested Map keyed by source then target node index. Unreachable pairs have a null path.

import type { Graph } from "effect"

declare const r: Graph.AllPairsResult<number>
// r.distances.get(source)?.get(target)  => number | undefined
// r.paths.get(source)?.get(target)      => Array<NodeIndex> | null | undefined

astar

Heuristic single-source shortest path. Needs a non-negative cost plus an admissible heuristic estimating remaining cost from a node to the target. Returns Option<PathResult>. See AstarConfig.

import { Graph, Option } from "effect"

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 r = Graph.astar(grid, {
  source: 0,
  target: 2,
  cost: (w) => w,
  heuristic: (node, target) =>
    Math.abs(node.x - target.x) + Math.abs(node.y - target.y)
})
console.log(Option.isSome(r) && r.value.path) // => [0, 1, 2]
console.log(Option.isSome(r) && r.value.distance) // => 2

AstarConfig

{ source: NodeIndex; target: NodeIndex; cost: (edgeData: E) => number; heuristic: (sourceNodeData: N, targetNodeData: N) => number }.

import type { Graph } from "effect"

const cfg: Graph.AstarConfig<number, { x: number; y: number }> = {
  source: 0,
  target: 2,
  cost: (w) => w,
  heuristic: (n, t) => Math.abs(n.x - t.x) + Math.abs(n.y - t.y)
}

bellmanFord

Single-source shortest path that tolerates negative edge weights. Returns Option<PathResult> (none if unreachable or a negative cycle reaches the target). Throws GraphError only on a missing endpoint. See BellmanFordConfig.

import { Graph, Option } from "effect"

const withNegative = 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, -1) // negative weight allowed
  Graph.addEdge(m, b, c, 3)
  Graph.addEdge(m, a, c, 5)
})

const r = Graph.bellmanFord(withNegative, { source: 0, target: 2, cost: (w) => w })
console.log(Option.isSome(r) && r.value.path) // => [0, 1, 2]
console.log(Option.isSome(r) && r.value.distance) // => 2  (-1 + 3)

BellmanFordConfig

{ source: NodeIndex; target: NodeIndex; cost: (edgeData: E) => number }.

import type { Graph } from "effect"

const cfg: Graph.BellmanFordConfig<number> = {
  source: 0,
  target: 2,
  cost: (w) => w
}

Export

toGraphViz

Renders the graph as GraphViz DOT text. Directed graphs become digraph with ->; undirected graphs become graph with --. Configurable via GraphVizOptions.

import { Graph } from "effect"

console.log(Graph.toGraphViz(g))
// => digraph G {
// =>   "0" [label="A"];
// =>   "1" [label="B"];
// =>   "2" [label="C"];
// =>   "0" -> "1" [label="1"];
// =>   "1" -> "2" [label="2"];
// =>   "0" -> "2" [label="4"];
// => }

GraphVizOptions

{ nodeLabel?: (data: N) => string; edgeLabel?: (data: E) => string; graphName?: string }. Labels default to String(data); graphName defaults to "G".

import { Graph } from "effect"

const dot = Graph.toGraphViz(g, {
  nodeLabel: (d) => `Node ${d}`,
  edgeLabel: (w) => `w=${w}`,
  graphName: "Deps"
})
console.log(dot.startsWith("digraph Deps {")) // => true

toMermaid

Renders the graph as Mermaid diagram text. Auto-selects flowchart (directed) or graph (undirected), with -->/--- edge operators. Configurable via MermaidOptions.

import { Graph } from "effect"

console.log(Graph.toMermaid(g))
// => flowchart TD
// =>   0["A"]
// =>   1["B"]
// =>   2["C"]
// =>   0 -->|"1"| 1
// =>   1 -->|"2"| 2
// =>   0 -->|"4"| 2

MermaidOptions

{ nodeLabel?; edgeLabel?; diagramType?: MermaidDiagramType; direction?: MermaidDirection; nodeShape?: (data: N) => MermaidNodeShape }. Labels default to String(data), direction defaults to "TD", and shapes default to "rectangle".

import { Graph } from "effect"

const out = Graph.toMermaid(g, {
  direction: "LR",
  nodeShape: (d) => (d === "A" ? "circle" : "rectangle")
})
console.log(out.startsWith("flowchart LR")) // => true
console.log(out.includes('0(("A"))')) // => true  (circle shape for A)

MermaidNodeShape

The node shape union: "rectangle", "rounded", "circle", "diamond", "hexagon", "stadium", "subroutine", "cylindrical". Returned by the nodeShape callback.

import type { Graph } from "effect"

const shape: Graph.MermaidNodeShape = "diamond" // renders A{"label"}

MermaidDirection

Layout orientation: "TB" / "TD" (top-down, default), "BT" (bottom-up), "LR" (left-to-right), "RL" (right-to-left).

import type { Graph } from "effect"

const dir: Graph.MermaidDirection = "LR"

MermaidDiagramType

"flowchart" (for directed graphs, -->) or "graph" (for undirected graphs, ---). Omit to auto-detect from the graph’s kind.

import type { Graph } from "effect"

const t: Graph.MermaidDiagramType = "flowchart"