Graph

Lazily enumerates all simple paths tied for minimum total cost.

When to use

Use when every distinct route tied for the minimum total cost is required.

Details

Parallel edges produce distinct paths. Edge costs must be non-negative; Infinity behaves as unavailable.

Gotchas

The number of tied paths can still be large. Missing endpoints, invalid costs, arithmetic overflow, or an invalid limit throw a GraphError. Mutable graphs are snapshotted when iteration begins.

See

• dijkstra when one shortest path is sufficient
• simplePaths for routes regardless of cost

declare const allShortestPaths: {
  <E>(config: AllShortestPathsConfig<E>): <N, T extends Kind = "directed">(graph: Graph<N, E, T> | MutableGraph<N, E, T>) => PathWalker<E>;
  <N, E, T extends Kind = "directed">(graph: Graph<N, E, T> | MutableGraph<N, E, T>, config: AllShortestPathsConfig<E>): PathWalker<E>;
}

Returns the nodes whose removal increases the number of connected components.

When to use

Use when locating single-node failure points in an undirected network.

Details

Disconnected components, parallel edges, and self-loops are handled by an iterative, stack-safe low-link traversal in O(V + E) time. Results follow graph node order.

Gotchas

Throws a GraphError when used with a directed graph.

See

• bridges for single-edge failure points
• biconnectedComponents for the regions joined at articulation points

declare function articulationPoints<N, E>(graph: Graph<N, E, "undirected"> | MutableGraph<N, E, "undirected">): Array<number>

import { Graph } from "effect"

const graph = Graph.undirected<void, void>((mutable) => {
  for (let i = 0; i < 3; i++) Graph.addNode(mutable, undefined)
  Graph.addEdge(mutable, 0, 1, undefined)
  Graph.addEdge(mutable, 1, 2, undefined)
})

Graph.articulationPoints(graph) // => [1]

Finds the shortest path from the configured source node to the target node using the A* pathfinding algorithm.

When to use

Use when a meaningful heuristic can reduce point-to-point search compared with Dijkstra's algorithm.

Details

The edge-cost function must return non-negative weights and not NaN. Infinity is allowed and behaves like an impassable edge. Returns Option.none() when the target is not reachable.

Gotchas

The heuristic must be consistent for the shortest-path guarantee and must return finite values. Missing endpoints, invalid edge costs, or non-finite heuristic values or arithmetic results throw a GraphError.

See

• dijkstra when no useful heuristic is available
• bellmanFord when edge costs may be negative

declare const astar: {
  <E, N>(config: AstarConfig<E, N>): <T extends Kind = "directed">(graph: Graph<N, E, T> | MutableGraph<N, E, T>) => Option<PathResult<E>>;
  <N, E, T extends Kind = "directed">(graph: Graph<N, E, T> | MutableGraph<N, E, T>, config: AstarConfig<E, N>): Option<PathResult<E>>;
}

import { Graph, Option } from "effect"

const graph = Graph.directed<{ x: number; y: number }, number>((mutable) => {
  const a = Graph.addNode(mutable, { x: 0, y: 0 })
  const b = Graph.addNode(mutable, { x: 1, y: 0 })
  const c = Graph.addNode(mutable, { x: 2, y: 0 })
  Graph.addEdge(mutable, a, b, 1)
  Graph.addEdge(mutable, b, c, 1)
})

// Manhattan distance heuristic
const heuristic = (
  nodeData: { x: number; y: number },
  targetData: { x: number; y: number }
) => Math.abs(nodeData.x - targetData.x) + Math.abs(nodeData.y - targetData.y)

const result = Graph.astar(graph, {
  source: 0,
  target: 2,
  cost: (edgeData) => edgeData,
  heuristic
})

Option.map(result, ({ distance, path }) => [distance, path] as const) // => Option.some([2, [0, 1, 2]])

Finds the shortest path from the configured source node to the target node using the Bellman-Ford algorithm.

When to use

Use when one source-to-target shortest-path query may traverse negative-cost edges.

Details

Negative edge weights are allowed, and Infinity behaves like an impassable edge. Returns Option.none() when the target is unreachable. A reachable negative cycle only causes failure when it can affect the target.

Gotchas

Missing endpoints, unsupported weights, finite-range overflow, or a relevant negative cycle throw a GraphError. In an undirected graph, any reachable negative edge forms a negative cycle because it can be traversed both ways.

See

• dijkstra for non-negative edge costs

declare const bellmanFord: {
  <E>(config: BellmanFordConfig<E>): <N, T extends Kind = "directed">(graph: Graph<N, E, T> | MutableGraph<N, E, T>) => Option<PathResult<E>>;
  <N, E, T extends Kind = "directed">(graph: Graph<N, E, T> | MutableGraph<N, E, T>, config: BellmanFordConfig<E>): Option<PathResult<E>>;
}

import { Graph, Option } from "effect"

const graph = Graph.directed<string, number>((mutable) => {
  const a = Graph.addNode(mutable, "A")
  const b = Graph.addNode(mutable, "B")
  const c = Graph.addNode(mutable, "C")
  Graph.addEdge(mutable, a, b, -1) // Negative weight allowed
  Graph.addEdge(mutable, b, c, 3)
  Graph.addEdge(mutable, a, c, 5)
})

const result = Graph.bellmanFord(graph, {
  source: 0,
  target: 2,
  cost: (edgeData) => edgeData
})

Option.map(result, ({ distance, path }) => [distance, path] as const) // => Option.some([2, [0, 1, 2]])

Returns the maximal biconnected node components of an undirected graph.

When to use

Use when decomposing an undirected graph into maximal regions that remain connected after removing any one node from the region.

Details

Articulation points can occur in more than one component. Isolated vertices are excluded, while a vertex with a self-loop forms a singleton component. Nodes within components and the components themselves follow graph order. Parallel edges are treated independently. The iterative low-link traversal is stack-safe and runs in O(V + E) time.

Gotchas

Throws a GraphError when used with a directed graph.

See

• articulationPoints for the nodes shared between components
• bridges for edges whose removal disconnects the graph

declare function biconnectedComponents<N, E>(graph: Graph<N, E, "undirected"> | MutableGraph<N, E, "undirected">): Array<Array<number>>

import { Graph } from "effect"

const graph = Graph.undirected<void, void>((mutable) => {
  for (let i = 0; i < 5; i++) Graph.addNode(mutable, undefined)
  Graph.addEdge(mutable, 0, 1, undefined)
  Graph.addEdge(mutable, 1, 2, undefined)
  Graph.addEdge(mutable, 2, 0, undefined)
  Graph.addEdge(mutable, 2, 3, undefined)
  Graph.addEdge(mutable, 3, 4, undefined)
  Graph.addEdge(mutable, 4, 2, undefined)
})

Graph.biconnectedComponents(graph) // => [[0, 1, 2], [2, 3, 4]]

Returns the edges whose removal increases the number of connected components.

When to use

Use when locating single-edge failure points in an undirected network.

Details

Parent edges are tracked by edge index, so a parallel edge prevents either edge from being a bridge. Self-loops are never bridges. Results follow graph edge order. The iterative low-link traversal is stack-safe and runs in O(V + E) time.

Gotchas

Throws a GraphError when used with a directed graph.

See

• articulationPoints for single-node failure points
• biconnectedComponents for maximal regions without an articulation split

declare function bridges<N, E>(graph: Graph<N, E, "undirected"> | MutableGraph<N, E, "undirected">): Array<number>

import { Graph } from "effect"

const graph = Graph.undirected<void, void>((mutable) => {
  for (let i = 0; i < 3; i++) Graph.addNode(mutable, undefined)
  Graph.addEdge(mutable, 0, 1, undefined)
  Graph.addEdge(mutable, 1, 2, undefined)
})

Graph.bridges(graph) // => [0, 1]

Returns the connected components of an undirected graph.

When to use

Use when partitioning an undirected graph into groups connected by paths.

Details

Each component is represented as an array of node indices. Isolated nodes form singleton components.

Gotchas

Throws a GraphError when used with a directed graph.

See

• isConnected when only a boolean connectivity check is needed
• weaklyConnectedComponents for directed graphs with orientation ignored
• stronglyConnectedComponents for mutual directed reachability

declare function connectedComponents<N, E>(graph: Graph<N, E, "undirected"> | MutableGraph<N, E, "undirected">): Array<Array<number>>

import { Graph } from "effect"

const graph = Graph.undirected<string, string>((mutable) => {
  const a = Graph.addNode(mutable, "A")
  const b = Graph.addNode(mutable, "B")
  const c = Graph.addNode(mutable, "C")
  const d = Graph.addNode(mutable, "D")
  Graph.addEdge(mutable, a, b, "edge") // Component 1: A-B
  Graph.addEdge(mutable, c, d, "edge") // Component 2: C-D
})

Graph.connectedComponents(graph) // => [[0, 1], [2, 3]]

Finds the shortest path from the configured source node to the target node using Dijkstra's algorithm.

When to use

Use when you need one source-to-target shortest path and every edge cost is non-negative.

Details

Edge costs must be non-negative and not NaN. Infinity is allowed and behaves like an impassable edge. Returns Option.none() when the target is not reachable.

Gotchas

Throws a GraphError when either endpoint is missing or an edge cost is negative or NaN, or when a path distance exceeds the finite number range.

See

• astar when a useful heuristic can guide the search
• bellmanFord when edge costs may be negative
• floydWarshall when shortest paths are needed for all pairs

declare const dijkstra: {
  <E>(config: DijkstraConfig<E>): <N, T extends Kind = "directed">(graph: Graph<N, E, T> | MutableGraph<N, E, T>) => Option<PathResult<E>>;
  <N, E, T extends Kind = "directed">(graph: Graph<N, E, T> | MutableGraph<N, E, T>, config: DijkstraConfig<E>): Option<PathResult<E>>;
}

import { Graph, Option } from "effect"

const graph = Graph.directed<string, number>((mutable) => {
  const a = Graph.addNode(mutable, "A")
  const b = Graph.addNode(mutable, "B")
  const c = Graph.addNode(mutable, "C")
  Graph.addEdge(mutable, a, b, 5)
  Graph.addEdge(mutable, a, c, 10)
  Graph.addEdge(mutable, b, c, 2)
})

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

Option.map(result, ({ distance, path }) => [distance, path] as const) // => Option.some([7, [0, 1, 2]])

Returns one cycle in a graph, if present.

When to use

Use when you need the nodes and edges of a concrete cycle for diagnostics or reporting.

Details

Directed cycles respect edge orientation. A self-loop is represented as a one-edge cycle, and two parallel undirected edges form a two-edge cycle.

See

• isAcyclic when only a boolean cycle check is needed

declare function findCycle<N, E, T extends Kind = "directed">(graph: Graph<N, E, T> | MutableGraph<N, E, T>): Option<CycleResult>

Finds shortest paths between all pairs of nodes using the Floyd-Warshall algorithm.

When to use

Use when many or all node pairs will be queried and cubic computation plus quadratic result storage is acceptable.

Details

Computes distances, reconstructed node paths, and edge-data paths for every source and target pair in O(V^3) time. Negative edge weights are allowed, and Infinity behaves like an impassable edge.

Gotchas

A GraphError is thrown if any edge weight is NaN or -Infinity, or if finite arithmetic overflows or underflows, or if any negative cycle is detected.

See

• dijkstra for one query with non-negative edge costs
• bellmanFord for one query that may include negative edge costs

declare const floydWarshall: {
  <E>(cost: (edgeData: E) => number): <N, T extends Kind = "directed">(graph: Graph<N, E, T> | MutableGraph<N, E, T>) => AllPairsResult<E>;
  <N, E, T extends Kind = "directed">(graph: Graph<N, E, T> | MutableGraph<N, E, T>, cost: (edgeData: E) => number): AllPairsResult<E>;
}

import { Graph } from "effect"

const graph = Graph.directed<string, number>((mutable) => {
  const a = Graph.addNode(mutable, "A")
  const b = Graph.addNode(mutable, "B")
  const c = Graph.addNode(mutable, "C")
  Graph.addEdge(mutable, a, b, 3)
  Graph.addEdge(mutable, b, c, 2)
  Graph.addEdge(mutable, a, c, 7)
})

const result = Graph.floydWarshall(graph, (edgeData) => edgeData)
const shortest = { distance: result.distances.get(0)?.get(2), path: result.paths.get(0)?.get(2) }
shortest // => { distance: 5, path: [0, 1, 2] }

Checks whether the graph is acyclic (contains no cycles).

When to use

Use when validating that a graph contains no cycle and a cycle witness is not needed.

Details

Directed cycles respect edge orientation. Self-loops are cycles, and two parallel edges form a cycle in an undirected graph.

See

• findCycle for retrieving one cycle witness
• topo for ordering a directed acyclic graph

declare function isAcyclic<N, E, T extends Kind = "directed">(graph: Graph<N, E, T> | MutableGraph<N, E, T>): boolean

import { Graph } from "effect"

// Acyclic directed graph (DAG)
const dag = Graph.directed<string, string>((mutable) => {
  const a = Graph.addNode(mutable, "A")
  const b = Graph.addNode(mutable, "B")
  const c = Graph.addNode(mutable, "C")
  Graph.addEdge(mutable, a, b, "A->B")
  Graph.addEdge(mutable, b, c, "B->C")
})
Graph.isAcyclic(dag) // => true

// Cyclic directed graph
const cyclic = Graph.directed<string, string>((mutable) => {
  const a = Graph.addNode(mutable, "A")
  const b = Graph.addNode(mutable, "B")
  Graph.addEdge(mutable, a, b, "A->B")
  Graph.addEdge(mutable, b, a, "B->A") // Creates cycle
})
Graph.isAcyclic(cyclic) // => false

Checks whether an undirected graph is bipartite.

When to use

Use when validating that nodes can be divided into two groups with every edge crossing between the groups.

Details

A bipartite graph is one whose vertices can be divided into two disjoint sets such that no two vertices within the same set are adjacent.

See

• maximumBipartiteMatching for matching nodes after validation

declare function isBipartite<N, E>(graph: Graph<N, E, "undirected"> | MutableGraph<N, E, "undirected">): boolean

import { Graph } from "effect"

// Bipartite graph (alternating coloring possible)
const bipartite = Graph.undirected<string, string>((mutable) => {
  const a = Graph.addNode(mutable, "A")
  const b = Graph.addNode(mutable, "B")
  const c = Graph.addNode(mutable, "C")
  const d = Graph.addNode(mutable, "D")
  Graph.addEdge(mutable, a, b, "edge") // Set 1: {A, C}, Set 2: {B, D}
  Graph.addEdge(mutable, b, c, "edge")
  Graph.addEdge(mutable, c, d, "edge")
})
Graph.isBipartite(bipartite) // => true

// Non-bipartite graph (odd cycle)
const triangle = Graph.undirected<string, string>((mutable) => {
  const a = Graph.addNode(mutable, "A")
  const b = Graph.addNode(mutable, "B")
  const c = Graph.addNode(mutable, "C")
  Graph.addEdge(mutable, a, b, "edge")
  Graph.addEdge(mutable, b, c, "edge")
  Graph.addEdge(mutable, c, a, "edge") // Triangle (3-cycle)
})
Graph.isBipartite(triangle) // => false

Returns a maximum-cardinality matching of an undirected bipartite graph.

When to use

Use when assigning as many disjoint pairs as possible between the two sides of a bipartite graph, such as workers to jobs or users to resources.

Details

The bipartition is derived internally. Self-loops and odd cycles throw a GraphError. Isolated nodes are allowed. Parallel edges do not change the matching cardinality, and the first edge in graph order between each matched pair is reported. Results follow left-partition graph order. Hopcroft-Karp runs in O(E * sqrt(V)) time.

Gotchas

The graph must be undirected and bipartite. The derived left and right sides are not based on stored edge orientation.

See

• isBipartite for validating the graph without computing a matching

declare function maximumBipartiteMatching<N, E>(graph: Graph<N, E, "undirected"> | MutableGraph<N, E, "undirected">): Array<BipartiteMatch>

import { Graph } from "effect"

const graph = Graph.undirected<string, string>((mutable) => {
  for (const node of ["A", "B", "X", "Y"]) Graph.addNode(mutable, node)
  Graph.addEdge(mutable, 0, 2, "A-X")
  Graph.addEdge(mutable, 0, 3, "A-Y")
  Graph.addEdge(mutable, 1, 2, "B-X")
})

Graph.maximumBipartiteMatching(graph) // => [{ left: 0, right: 3, edge: 1 }, { left: 1, right: 2, edge: 2 }]

Returns a maximum flow and corresponding minimum cut for a directed graph.

When to use

Use when computing the greatest transferable capacity from one node to another and per-edge flow values are required.

Details

Parallel edges retain independent capacities, self-loops carry no source-to-target flow, and the flow map includes every original edge in graph order, including zero-flow edges. Edmonds-Karp runs in O(V * E^2) time.

Gotchas

The graph must be directed. Capacities must be finite and non-negative. Missing or equal endpoints, invalid capacities, and a total flow outside the finite number range throw a GraphError. Self-loops always carry zero flow.

See

• minimumCut for the residual-reachability partition

declare const maximumFlow: {
  <E>(config: MaximumFlowConfig<E>): <N>(graph: Graph<N, E, "directed"> | MutableGraph<N, E, "directed">) => MaximumFlowResult;
  <N, E>(graph: Graph<N, E, "directed"> | MutableGraph<N, E, "directed">, config: MaximumFlowConfig<E>): MaximumFlowResult;
}

import { Graph } from "effect"

const graph = Graph.directed<string, number>((mutable) => {
  for (const node of ["source", "a", "target"]) Graph.addNode(mutable, node)
  Graph.addEdge(mutable, 0, 1, 3)
  Graph.addEdge(mutable, 1, 2, 2)
  Graph.addEdge(mutable, 0, 2, 1)
})

Graph.maximumFlow(graph, { source: 0, target: 2, capacity: (edge) => edge }).value // => 3

Returns a minimum cut and its node partitions for a directed graph.

When to use

Use when identifying the minimum-capacity edges that separate a source from a target, together with the resulting node partitions.

Details

The source partition contains nodes reachable from the source in the final residual network; the target partition contains its complement. Both follow graph node order. Cut edges follow graph edge order, and their total capacity equals the returned maximum-flow value. Validation, parallel-edge, self-loop, and O(V * E^2) complexity behavior match maximumFlow.

Gotchas

The graph must be directed. Invalid capacities, missing endpoints, or equal source and target nodes throw a GraphError.

See

• maximumFlow for per-edge flow values

declare const minimumCut: {
  <E>(config: MaximumFlowConfig<E>): <N>(graph: Graph<N, E, "directed"> | MutableGraph<N, E, "directed">) => MinimumCutResult;
  <N, E>(graph: Graph<N, E, "directed"> | MutableGraph<N, E, "directed">, config: MaximumFlowConfig<E>): MinimumCutResult;
}

import { Graph } from "effect"

const graph = Graph.directed<string, number>((mutable) => {
  for (const node of ["source", "a", "target"]) Graph.addNode(mutable, node)
  Graph.addEdge(mutable, 0, 1, 2)
  Graph.addEdge(mutable, 1, 2, 1)
})

Graph.minimumCut(graph, { source: 0, target: 2, capacity: (edge) => edge }).source // => [0, 1]

Returns a minimum spanning forest of an undirected graph using Kruskal's algorithm.

When to use

Use when selecting a minimum-cost acyclic connector for every connected component of an undirected graph.

Details

All node indices and selected edge indices are preserved. Negative finite weights are allowed, Infinity marks an unavailable edge, and equal weights are resolved by original edge order. Disconnected inputs produce a forest, and isolated nodes remain present.

Gotchas

Throws a GraphError for a directed graph or when a weight is NaN or -Infinity. Edges weighted Infinity are omitted.

declare const minimumSpanningForest: {
  <E>(cost: (edgeData: E) => number): <N>(graph: Graph<N, E, "undirected"> | MutableGraph<N, E, "undirected">) => Graph<N, E, "undirected">;
  <N, E>(graph: Graph<N, E, "undirected"> | MutableGraph<N, E, "undirected">, cost: (edgeData: E) => number): Graph<N, E, "undirected">;
}

Lazily enumerates simple source-to-target paths in depth-first edge order.

When to use

Use when you need possible loop-free routes rather than only an optimal route.

Details

Nodes are never repeated within a path, so enumeration is finite even for cyclic graphs. Path distance is the number of traversed edges.

Gotchas

The number of simple paths can be exponential. Missing endpoints or an invalid limit throw a GraphError. Mutable graphs are snapshotted when iteration begins.

See

• allShortestPaths for enumerating only minimum-cost routes

declare const simplePaths: {
  <E>(config: SimplePathsConfig): <N, T extends Kind = "directed">(graph: Graph<N, E, T> | MutableGraph<N, E, T>) => PathWalker<E>;
  <N, E, T extends Kind = "directed">(graph: Graph<N, E, T> | MutableGraph<N, E, T>, config: SimplePathsConfig): PathWalker<E>;
}

Returns the strongly connected components of a directed graph.

When to use

Use when grouping nodes so every node in a component can reach every other node in that component.

Details

Each component is represented as an array of node indices and is computed with Kosaraju's algorithm.

Gotchas

Throws a GraphError when used with an undirected graph.

See

• isStronglyConnected when only a boolean check is needed
• weaklyConnectedComponents when edge orientation should be ignored

declare function stronglyConnectedComponents<N, E>(graph: Graph<N, E, "directed"> | MutableGraph<N, E, "directed">): Array<Array<number>>

import { Graph } from "effect"

const graph = Graph.directed<string, string>((mutable) => {
  const a = Graph.addNode(mutable, "A")
  const b = Graph.addNode(mutable, "B")
  const c = Graph.addNode(mutable, "C")
  Graph.addEdge(mutable, a, b, "A->B")
  Graph.addEdge(mutable, b, c, "B->C")
  Graph.addEdge(mutable, c, a, "C->A") // Creates SCC: A-B-C
})

Graph.stronglyConnectedComponents(graph) // => [[0, 2, 1]]

Returns the transitive reduction of a directed acyclic graph.

When to use

Use when simplifying a dependency DAG while preserving which nodes can reach which other nodes.

Details

The result preserves reachability with the fewest structural source-target pairs. Node and retained edge indices are preserved.

Gotchas

This operation is structural and ignores edge costs. Parallel edges are coalesced by retaining the first edge for each required pair. Throws a GraphError for an undirected graph or cyclic input.

declare function transitiveReduction<N, E>(graph: Graph<N, E, "directed"> | MutableGraph<N, E, "directed">): Graph<N, E, "directed">

Returns minimum unweighted distances from a source to every reachable node.

When to use

Use when every edge represents one step and you need hop counts from one source.

Details

Directed traversal is outgoing by default and can be changed with direction.

Gotchas

Throws a GraphError when the source does not exist.

See

• hasPath when only a reachability boolean is needed
• bfs for lazy traversal in increasing hop distance
• dijkstra for weighted shortest paths

declare const unweightedDistances: {
  (source: number, options?: ReachabilityConfig): <N, E, T extends Kind = "directed">(graph: Graph<N, E, T> | MutableGraph<N, E, T>) => Map<number, number>;
  <N, E, T extends Kind = "directed">(graph: Graph<N, E, T> | MutableGraph<N, E, T>, source: number, options?: ReachabilityConfig): Map<number, number>;
}

Finds weakly connected components in a directed graph.

When to use

Use when grouping directed nodes by connectivity while ignoring edge orientation.

Details

Edge direction is ignored while partitioning nodes. Isolated nodes form singleton components.

Gotchas

Throws a GraphError when used with an undirected graph.

See

• isWeaklyConnected when only a boolean check is needed
• stronglyConnectedComponents for mutual directed reachability

declare function weaklyConnectedComponents<N, E>(graph: Graph<N, E, "directed"> | MutableGraph<N, E, "directed">): Array<Array<number>>

Configuration for enumerating all tied shortest paths.

When to use

Use when bounding enumeration of every route tied for minimum total cost.

Details

Edge costs must be non-negative. limit bounds the number of yielded paths and defaults to Infinity.

Gotchas

Invalid costs and limits throw a GraphError when evaluated.

interface AllShortestPathsConfig<E> extends DijkstraConfig<E> {
  readonly limit?: number;
}

Configuration for finding a shortest path with the A* algorithm.

When to use

Use when configuring astar for point-to-point shortest-path searches where node data can provide a heuristic estimate toward the target.

Details

Specifies the source and target node indices, an edge-cost function that maps edge data to non-negative weights, and a heuristic that estimates the remaining cost from a node to the target.

Gotchas

Heuristic values must be finite and the heuristic must be consistent for A* to guarantee a shortest path.

interface AstarConfig<E, N> {
  cost: (edgeData: E) => number;
  heuristic: (sourceNodeData: N, targetNodeData: N) => number;
  source: number;
  target: number;
}

Configuration for finding a shortest path with the Bellman-Ford algorithm.

When to use

Use when configuring bellmanFord to find a shortest path where edge weights may be negative.

Details

Specifies the source and target node indices, plus a cost function that maps each edge's data to a numeric weight.

interface BellmanFordConfig<E> {
  cost: (edgeData: E) => number;
  source: number;
  target: number;
}

Configuration for finding a shortest path with Dijkstra's algorithm.

When to use

Use when configuring dijkstra to find a shortest path between two existing node indices with non-negative edge costs.

Details

Specifies the source and target node indices, plus a cost function that maps each edge's data to a non-negative numeric weight. Infinity is allowed and behaves like an impassable edge.

Gotchas

dijkstra throws a GraphError when either endpoint does not exist or when the cost function returns a negative weight or NaN.

interface DijkstraConfig<E> {
  cost: (edgeData: E) => number;
  source: number;
  target: number;
}

Configuration for selecting external nodes.

When to use

Use to configure how externals identifies graph boundary nodes when you need sinks with no outgoing edges or sources with no incoming edges.

Details

direction chooses which missing edge direction makes a node external: "outgoing" selects nodes with no outgoing edges, and "incoming" selects nodes with no incoming edges. If omitted, direction defaults to "outgoing".

interface ExternalsConfig {
  readonly direction?: Direction;
}

Configuration options for GraphViz DOT format generation from graphs.

When to use

Use when customizing labels or the graph name produced by toGraphViz.

Details

These options customize node labels, edge labels, and graph naming in DOT format compatible with GraphViz tools.

See

• toGraphViz for generating DOT output

interface GraphVizOptions<N, E> {
  readonly edgeLabel?: (data: E) => string;
  readonly graphName?: string;
  readonly nodeLabel?: (data: N) => string;
}

import type { Graph } from "effect"

// Basic options with custom labels
const basicOptions: Graph.GraphVizOptions<string, number> = {
  nodeLabel: (data) => `Node: ${data}`,
  edgeLabel: (data) => `Weight: ${data}`
}

// Complete options with graph naming
const namedOptions: Graph.GraphVizOptions<string, string> = {
  nodeLabel: (data) => data.toUpperCase(),
  edgeLabel: (data) => data,
  graphName: "MyDependencyGraph"
}
Array.of(basicOptions.nodeLabel?.("A"), namedOptions.graphName) // => ["Node: A", "MyDependencyGraph"]

Configures node and edge identity for graph set operations.

When to use

Use when logical graph membership should be based on a stable key rather than the complete node or edge payload.

Details

Both functions default to using the complete node or edge data. Edge identity also includes the identities of its endpoint nodes and the graph kind. Projected identities use Effect equality and hashing semantics.

Gotchas

Edge identity defines set membership, not edge multiplicity. Parallel edges with the same endpoint identities and projected edge identity are treated as the same member by graph set operations.

interface IdentityOptions<N, E, NI = N, EI = E> {
  readonly edgeIdentity?: (edge: E) => EI;
  readonly nodeIdentity?: (node: N) => NI;
}

Configuration for source-to-target flow algorithms.

When to use

Use when defining endpoints and edge capacities for maximumFlow or minimumCut.

Details

capacity receives stored edge data and must return a finite, non-negative number.

Gotchas

The source and target must be distinct existing nodes in a directed graph.

interface MaximumFlowConfig<E> {
  readonly capacity: (edge: E) => number;
  readonly source: number;
  readonly target: number;
}

Configuration options for Mermaid diagram generation from graphs.

When to use

Use when customizing labels, layout, node shapes, or syntax emitted by toMermaid.

Details

These options customize node labels, edge labels, diagram type, layout direction and node shapes in Mermaid format.

See

• toMermaid for generating Mermaid output

interface MermaidOptions<N, E> {
  readonly diagramType?: MermaidDiagramType;
  readonly direction?: MermaidDirection;
  readonly edgeLabel?: (data: E) => string;
  readonly nodeLabel?: (data: N) => string;
  readonly nodeShape?: (data: N) => MermaidNodeShape;
}

import type { Graph } from "effect"

// Basic options with custom labels
const basicOptions: Graph.MermaidOptions<string, number> = {
  nodeLabel: (data) => `Node: ${data}`,
  edgeLabel: (data) => `Weight: ${data}`
}

// Advanced options with all features
const advancedOptions: Graph.MermaidOptions<string, string> = {
  nodeLabel: (data) => data.toUpperCase(),
  edgeLabel: (data) => data,
  diagramType: "flowchart",
  direction: "LR",
  nodeShape: (data) => data.includes("start") ? "circle" : "rectangle"
}
Array.of(basicOptions.nodeLabel?.("A"), advancedOptions.nodeShape?.("start")) // => ["Node: A", "circle"]

Configuration for selecting a graph neighborhood.

Details

radius limits the edge distance from the center node and defaults to 1. It accepts non-negative integers and Infinity. direction controls how directed edges are traversed and defaults to "outgoing".

interface NeighborhoodConfig {
  readonly direction?: TraversalDirection;
  readonly radius?: number;
}

Configuration for unweighted reachability queries.

When to use

Use when controlling whether reachability follows outgoing edges, incoming edges, or either direction.

Details

direction defaults to "outgoing" and is ignored for undirected graphs.

interface ReachabilityConfig {
  readonly direction?: TraversalDirection;
}

Configuration for DFS, BFS, and postorder graph traversals.

When to use

Use to configure the starting node indices and edge-following direction for lazy graph traversals.

Details

start supplies the node indices where traversal begins. If it is omitted, the iterator is empty. Distinct starts are prioritized in supplied order and duplicates are ignored. direction chooses whether traversal follows outgoing edges, incoming edges, or ignores edge direction. radius limits traversal by edge distance from the nearest start node and accepts non-negative integers or Infinity; omitting it means unbounded traversal.

Gotchas

Traversal creation validates and copies start, and throws a GraphError when a start node does not exist or radius is invalid. Each fresh iterator revalidates those starts against the graph snapshot it captures. Later mutations are not observed by an active iterator.

interface SearchConfig {
  readonly direction?: TraversalDirection;
  readonly radius?: number;
  readonly start?: Array<number>;
}

Configuration for lazy simple-path enumeration.

When to use

Use when bounding enumeration of loop-free routes between two nodes.

Details

limit bounds the number of yielded paths and defaults to Infinity.

Gotchas

limit must be a non-negative integer or Infinity.

interface SimplePathsConfig {
  readonly limit?: number;
  readonly source: number;
  readonly target: number;
}

Configuration for the topological sort iterator.

When to use

Use to prioritize specific zero in-degree nodes in a topological sort.

Details

initials optionally supplies zero in-degree node indices used as prioritized initial queue entries. Topological sorting still includes the other zero in-degree nodes and produces a complete topological order.

Gotchas

Throws a GraphError when any initial node has incoming edges.

interface TopoConfig {
  readonly initials?: Array<number>;
}

Creates a directed graph, optionally with initial mutations.

When to use

Use when relationships have a source-to-target direction, such as dependencies, workflows, or routing links.

Gotchas

The mutable callback handle is finalized when the callback returns and must not be retained for later mutation.

declare const directed: <N, E>(mutate?: (mutable: MutableDirectedGraph<N, E>) => undefined) => DirectedGraph<N, E>

import { Graph } from "effect"

// Directed graph with initial nodes and edges
const graph = Graph.directed<string, string>((mutable) => {
  const a = Graph.addNode(mutable, "A")
  const b = Graph.addNode(mutable, "B")
  const c = Graph.addNode(mutable, "C")
  Graph.addEdge(mutable, a, b, "A->B")
  Graph.addEdge(mutable, b, c, "B->C")
})
Array.of(Graph.nodeCount(graph), Graph.edgeCount(graph)) // => [3, 2]

Reconstructs an immutable graph from its indexed active structure.

When to use

Use when importing a snapshot or other externally indexed graph structure. Prefer directed or undirected when creating a new graph without existing identifiers.

Gotchas

The node and edge arrays must be ordered by strictly increasing, non-negative safe integer indexes, and every edge endpoint must reference a node in the snapshot. Invalid snapshots throw a GraphError. Historical removed identifiers after the greatest active index are not retained.

See

• toSnapshot for capturing a graph snapshot

declare function fromSnapshot<N, E, T extends Kind>(snapshot: Snapshot<N, E, T>): Graph<N, E, T>

import { Graph } from "effect"

const graph = Graph.fromSnapshot({
  type: "directed",
  nodes: [{ index: 2, data: "A" }, { index: 5, data: "B" }],
  edges: [{ index: 3, source: 2, target: 5, data: 1 }]
})

Graph.toSnapshot(graph).edges[0].index // => 3

Creates a graph constructor for the specified graph kind.

When to use

Use when the graph kind is selected dynamically. Prefer directed or undirected when the kind is known statically.

See

• directed for constructing a directed graph directly
• undirected for constructing an undirected graph directly

declare function make<T extends Kind>(type: T): <N, E>(mutate?: (mutable: MutableGraph<N, E, T>) => undefined) => Graph<N, E, T>

import { Graph } from "effect"

const makeGraph = Graph.make("directed")
const graph = makeGraph<string, number>((mutable) => {
  Graph.addNode(mutable, "A")
})

graph.type // => "directed"

Creates an undirected graph, optionally with initial mutations.

When to use

Use when relationships connect both endpoints symmetrically, such as social connections or physical links.

Gotchas

The mutable callback handle is finalized when the callback returns and must not be retained for later mutation.

declare const undirected: <N, E>(mutate?: (mutable: MutableUndirectedGraph<N, E>) => undefined) => UndirectedGraph<N, E>

import { Graph } from "effect"

// Undirected graph with initial nodes and edges
const graph = Graph.undirected<string, string>((mutable) => {
  const a = Graph.addNode(mutable, "A")
  const b = Graph.addNode(mutable, "B")
  const c = Graph.addNode(mutable, "C")
  Graph.addEdge(mutable, a, b, "A-B")
  Graph.addEdge(mutable, b, c, "B-C")
})
Array.of(Graph.nodeCount(graph), Graph.edgeCount(graph)) // => [3, 2]

Exports a graph to GraphViz DOT format for visualization.

When to use

Use when sending graph structure to GraphViz-compatible visualization or documentation tools.

See

• toMermaid for Mermaid diagram output

declare const toGraphViz: {
  <N, E>(options?: GraphVizOptions<N, E>): <T extends Kind = "directed">(graph: Graph<N, E, T> | MutableGraph<N, E, T>) => string;
  <N, E, T extends Kind = "directed">(graph: Graph<N, E, T> | MutableGraph<N, E, T>, options?: GraphVizOptions<N, E>): string;
}

import { Graph } from "effect"

const graph = Graph.mutate(Graph.directed<string, number>(), (mutable) => {
  const nodeA = Graph.addNode(mutable, "Node A")
  const nodeB = Graph.addNode(mutable, "Node B")
  const nodeC = Graph.addNode(mutable, "Node C")
  Graph.addEdge(mutable, nodeA, nodeB, 1)
  Graph.addEdge(mutable, nodeB, nodeC, 2)
  Graph.addEdge(mutable, nodeC, nodeA, 3)
})

Graph.toGraphViz(graph).split("\n") // => ['digraph "G" {', '  "0" [label="Node A"];', '  "1" [label="Node B"];', '  "2" [label="Node C"];', '  "0" -> "1" [label="1"];', '  "1" -> "2" [label="2"];', '  "2" -> "0" [label="3"];', "}"]

Exports a graph to Mermaid diagram format for visualization.

When to use

Use when embedding graph diagrams in Markdown, documentation sites, or other Mermaid-compatible tools.

Details

Directed graphs default to flowchart with arrow edges, while undirected graphs default to graph with line edges. Labels and node shapes can be customized with MermaidOptions.

See

• toGraphViz for GraphViz DOT output

declare const toMermaid: {
  <N, E>(options?: MermaidOptions<N, E>): <T extends Kind = "directed">(graph: Graph<N, E, T> | MutableGraph<N, E, T>) => string;
  <N, E, T extends Kind = "directed">(graph: Graph<N, E, T> | MutableGraph<N, E, T>, options?: MermaidOptions<N, E>): string;
}

import { Graph } from "effect"

const graph = Graph.directed<string, string>((mutable) => {
  const app = Graph.addNode(mutable, "App")
  const database = Graph.addNode(mutable, "Database")
  Graph.addEdge(mutable, app, database, "queries")
})

Graph.toMermaid(graph).split("\n") // => ["flowchart TD", '  0["App"]', '  1["Database"]', '  0 -->|"queries"| 1']

Returns the active indexed structure of a graph.

When to use

Use when serializing a graph or passing its active structure across a boundary where node and edge identifiers must be preserved.

Details

Nodes and edges are returned in graph order with their current indexes. Undirected edges retain their stored endpoint orientation, and each returned node and edge record is newly allocated. The operation runs in O(V + E).

Gotchas

Node and edge payloads are not cloned. The snapshot also omits allocator history for identifiers that are no longer active.

See

• fromSnapshot for reconstructing an immutable graph

declare function toSnapshot<N, E, T extends Kind = "directed">(graph: Graph<N, E, T> | MutableGraph<N, E, T>): Snapshot<N, E, T>

import { Equal, Graph } from "effect"

const graph = Graph.fromSnapshot({
  type: "undirected",
  nodes: [{ index: 2, data: "A" }, { index: 5, data: "B" }],
  edges: [{ index: 3, source: 5, target: 2, data: "A-B" }]
})

Equal.equals(Graph.fromSnapshot(Graph.toSnapshot(graph)), graph) // => true

Error thrown by graph operations when the requested graph structure is invalid, such as referencing a missing node or using unsupported edge weights.

When to use

Use when handling failures thrown by graph operations that reject invalid graph structure or unsupported algorithm inputs.

declare class GraphError extends YieldableError<this> & {
  readonly _tag: "GraphError";
} & Readonly<{
  readonly message: string;
}> {
  constructor(args: {
    readonly message: string;
  });
}

Filters edges by removing those that don't match the predicate. This function modifies the mutable graph in place. Nodes are retained even when removing edges leaves them isolated.

Gotchas

The predicate may query the graph, but cannot mutate or finalize the same graph while it runs.

declare function filterEdges<N, E, T extends Kind = "directed">(mutable: MutableGraph<N, E, T>, predicate: (data: E) => boolean): void

import { Graph } from "effect"

const graph = Graph.directed<string, number>((mutable) => {
  const a = Graph.addNode(mutable, "A")
  const b = Graph.addNode(mutable, "B")
  const c = Graph.addNode(mutable, "C")

  Graph.addEdge(mutable, a, b, 5)
  Graph.addEdge(mutable, b, c, 15)
  Graph.addEdge(mutable, c, a, 25)

  // Keep only edges with weight >= 10
  Graph.filterEdges(mutable, (data) => data >= 10)
})

Graph.edgeCount(graph) // => 2

Filters and optionally transforms edges in a mutable graph using a predicate function. Edges that return Option.none are removed from the graph.

Gotchas

The function may query the graph, but cannot mutate or finalize the same graph while it runs. Retained payloads must remain the same edge type.

declare function filterMapEdges<N, E, T extends Kind = "directed">(mutable: MutableGraph<N, E, T>, f: (data: E) => Option<E>): void

import { Graph, Option } from "effect"

const graph = Graph.directed<string, number>((mutable) => {
  const a = Graph.addNode(mutable, "A")
  const b = Graph.addNode(mutable, "B")
  const c = Graph.addNode(mutable, "C")
  Graph.addEdge(mutable, a, b, 5)
  Graph.addEdge(mutable, b, c, 15)
  Graph.addEdge(mutable, c, a, 25)

  // Keep only edges with weight >= 10 and double their weight
  Graph.filterMapEdges(
    mutable,
    (data) => data >= 10 ? Option.some(data * 2) : Option.none()
  )
})

Graph.edgeCount(graph) // => 2