Graph
Algorithms
Signature
declare function astar<N, E, T extends Kind = "directed">(
graph: Graph<N, E, T> | MutableGraph<N, E, T>,
config: AstarConfig<E, N>,
): Option<PathResult<E>>;bellmanFord
Find the shortest path between two nodes using Bellman-Ford algorithm.
Bellman-Ford algorithm can handle negative edge weights and detects negative cycles. It has O(VE) time complexity, slower than Dijkstra's but more versatile. Returns Option.none() if a negative cycle is detected that affects the path.
Signature
declare function bellmanFord<N, E, T extends Kind = "directed">(
graph: Graph<N, E, T> | MutableGraph<N, E, T>,
config: BellmanFordConfig<E>,
): Option<PathResult<E>>;connectedComponents
Find connected components in an undirected graph. Each component is represented as an array of node indices.
Signature
declare function connectedComponents<N, E>(
graph: Graph<N, E, "undirected"> | MutableGraph<N, E, "undirected">,
): Array<Array<number>>;Find the shortest path between two nodes using Dijkstra's algorithm.
Dijkstra's algorithm works with non-negative edge weights and finds the shortest path from a source node to a target node in O((V + E) log V) time complexity.
Signature
declare function dijkstra<N, E, T extends Kind = "directed">(
graph: Graph<N, E, T> | MutableGraph<N, E, T>,
config: DijkstraConfig<E>,
): Option<PathResult<E>>;floydWarshall
Find shortest paths between all pairs of nodes using Floyd-Warshall algorithm.
Floyd-Warshall algorithm computes shortest paths between all pairs of nodes in O(V³) time. It can handle negative edge weights and detect negative cycles.
Signature
declare function floydWarshall<N, E, T extends Kind = "directed">(
graph: Graph<N, E, T> | MutableGraph<N, E, T>,
cost: (edgeData: E) => number,
): AllPairsResult<E>;Checks if the graph is acyclic (contains no cycles).
Uses depth-first search to detect back edges, which indicate cycles. For directed graphs, any back edge creates a cycle. For undirected graphs, a back edge that doesn't go to the immediate parent creates a cycle.
Signature
declare function isAcyclic<N, E, T extends Kind = "directed">(
graph: Graph<N, E, T> | MutableGraph<N, E, T>,
): boolean;isBipartite
Checks if an undirected graph is bipartite.
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. Uses BFS coloring to determine bipartiteness.
Signature
declare function isBipartite<N, E>(
graph: Graph<N, E, "undirected"> | MutableGraph<N, E, "undirected">,
): boolean;stronglyConnectedComponents
Find strongly connected components in a directed graph using Kosaraju's algorithm. Each SCC is represented as an array of node indices.
Signature
declare function stronglyConnectedComponents<N, E>(
graph: Graph<N, E, "directed"> | MutableGraph<N, E, "directed">,
): Array<Array<number>>;Constructors
Creates a directed graph, optionally with initial mutations.
Signature
declare function directed<N, E>(
mutate?: (mutable: MutableDirectedGraph<N, E>) => void,
): DirectedGraph<N, E>;undirected
Creates an undirected graph, optionally with initial mutations.
Signature
declare function undirected<N, E>(
mutate?: (mutable: MutableUndirectedGraph<N, E>) => void,
): UndirectedGraph<N, E>;Errors
GraphError
Error thrown when a graph operation fails.
Signature
declare class GraphError extends YieldableError<this> & {
readonly _tag: "GraphError";
} & Readonly<{
readonly message: string;
}> {
constructor(args: {
readonly message: string;
});
}Getters
Returns the number of edges in the graph.
Signature
declare function edgeCount<N, E, T extends Kind = "directed">(
graph: Graph<N, E, T> | MutableGraph<N, E, T>,
): number;Finds the first edge that matches the given predicate.
Signature
declare function findEdge<N, E, T extends Kind = "directed">(
graph: Graph<N, E, T> | MutableGraph<N, E, T>,
predicate: (data: E, source: number, target: number) => boolean,
): Option<number>;Finds all edges that match the given predicate.
Signature
declare function findEdges<N, E, T extends Kind = "directed">(
graph: Graph<N, E, T> | MutableGraph<N, E, T>,
predicate: (data: E, source: number, target: number) => boolean,
): Array<number>;Finds the first node that matches the given predicate.
Signature
declare function findNode<N, E, T extends Kind = "directed">(
graph: Graph<N, E, T> | MutableGraph<N, E, T>,
predicate: (data: N) => boolean,
): Option<number>;Finds all nodes that match the given predicate.
Signature
declare function findNodes<N, E, T extends Kind = "directed">(
graph: Graph<N, E, T> | MutableGraph<N, E, T>,
predicate: (data: N) => boolean,
): Array<number>;Gets the edge data associated with an edge index, if it exists.
Signature
declare function getEdge<N, E, T extends Kind = "directed">(
graph: Graph<N, E, T> | MutableGraph<N, E, T>,
edgeIndex: number,
): Option<Edge<E>>;Gets the data associated with a node index, if it exists.
Signature
declare function getNode<N, E, T extends Kind = "directed">(
graph: Graph<N, E, T> | MutableGraph<N, E, T>,
nodeIndex: number,
): Option<N>;Checks if an edge exists between two nodes in the graph.
Signature
declare function hasEdge<N, E, T extends Kind = "directed">(
graph: Graph<N, E, T> | MutableGraph<N, E, T>,
source: number,
target: number,
): boolean;Checks if a node with the given index exists in the graph.
Signature
declare function hasNode<N, E, T extends Kind = "directed">(
graph: Graph<N, E, T> | MutableGraph<N, E, T>,
nodeIndex: number,
): boolean;Returns the neighboring nodes (targets of outgoing edges) for a given node.
Signature
declare function neighbors<N, E, T extends Kind = "directed">(
graph: Graph<N, E, T> | MutableGraph<N, E, T>,
nodeIndex: number,
): Array<number>;Returns the number of nodes in the graph.
Signature
declare function nodeCount<N, E, T extends Kind = "directed">(
graph: Graph<N, E, T> | MutableGraph<N, E, T>,
): number;Iterators
Creates a new BFS iterator with optional configuration.
The iterator maintains a queue of nodes to visit and tracks discovered nodes. It provides lazy evaluation of the breadth-first search.
Signature
declare function bfs<N, E, T extends Kind = "directed">(
graph: Graph<N, E, T> | MutableGraph<N, E, T>,
config: SearchConfig,
): NodeWalker<N>;Creates a new DFS iterator with optional configuration.
The iterator maintains a stack of nodes to visit and tracks discovered nodes. It provides lazy evaluation of the depth-first search.
Signature
declare function dfs<N, E, T extends Kind = "directed">(
graph: Graph<N, E, T> | MutableGraph<N, E, T>,
config: SearchConfig,
): NodeWalker<N>;dfsPostOrder
Creates a new DFS postorder iterator with optional configuration.
The iterator maintains a stack with visit state tracking and emits nodes in postorder (after all descendants have been processed). Essential for dependency resolution and tree destruction algorithms.
Signature
declare function dfsPostOrder<N, E, T extends Kind = "directed">(
graph: Graph<N, E, T> | MutableGraph<N, E, T>,
config: SearchConfig,
): NodeWalker<N>;Creates an iterator over all edge indices in the graph.
The iterator produces edge indices in the order they were added to the graph. This provides access to all edges regardless of connectivity.
Signature
declare function edges<N, E, T extends Kind = "directed">(
graph: Graph<N, E, T> | MutableGraph<N, E, T>,
): EdgeWalker<E>;Creates an iterator over external nodes (nodes without edges in specified direction).
External nodes are nodes that have no outgoing edges (direction="outgoing") or no incoming edges (direction="incoming"). These are useful for finding sources, sinks, or isolated nodes.
Signature
declare function externals<N, E, T extends Kind = "directed">(
graph: Graph<N, E, T> | MutableGraph<N, E, T>,
config: ExternalsConfig,
): NodeWalker<N>;Creates an iterator over all node indices in the graph.
The iterator produces node indices in the order they were added to the graph. This provides access to all nodes regardless of connectivity.
Signature
declare function nodes<N, E, T extends Kind = "directed">(
graph: Graph<N, E, T> | MutableGraph<N, E, T>,
): NodeWalker<N>;Creates a new topological sort iterator with optional configuration.
The iterator uses Kahn's algorithm to lazily produce nodes in topological order. Throws an error if the graph contains cycles.
Signature
declare function topo<N, E, T extends Kind = "directed">(
graph: Graph<N, E, T> | MutableGraph<N, E, T>,
config: TopoConfig,
): NodeWalker<N>;Models
AllPairsResult interface
Result of all-pairs shortest path computation.
Signature
interface AllPairsResult<E> {
readonly costs: Map<number, Map<number, Array<E>>>;
readonly distances: Map<number, Map<number, number>>;
readonly paths: Map<number, Map<number, Array<number> | null>>;
}AstarConfig interface
Configuration for A* algorithm.
Signature
interface AstarConfig<E, N> {
cost: (edgeData: E) => number;
heuristic: (sourceNodeData: N, targetNodeData: N) => number;
source: number;
target: number;
}BellmanFordConfig interface
Configuration for Bellman-Ford algorithm.
Signature
interface BellmanFordConfig<E> {
cost: (edgeData: E) => number;
source: number;
target: number;
}DijkstraConfig interface
Configuration for Dijkstra's algorithm.
Signature
interface DijkstraConfig<E> {
cost: (edgeData: E) => number;
source: number;
target: number;
}DirectedGraph type
Directed graph type alias.
Signature
type DirectedGraph<N, E> = Graph<N, E, "directed">;Direction for graph traversal, indicating which edges to follow.
Signature
type Direction = "outgoing" | "incoming";Example
import { Graph } from "effect"
const graph = Graph.directed<string, string>((mutable) => {
const a = Graph.addNode(mutable, "A")
const b = Graph.addNode(mutable, "B")
Graph.addEdge(mutable, a, b, "A->B")
})
// Follow outgoing edges (normal direction)
const outgoingNodes = Array.from(
Graph.indices(Graph.dfs(graph, { start: [0], direction: "outgoing" })),
)
// Follow incoming edges (reverse direction)
const incomingNodes = Array.from(
Graph.indices(Graph.dfs(graph, { start: [1], direction: "incoming" })),
)Edge data containing source, target, and user data.
Signature
declare class Edge<E> extends Class<{
readonly data: E;
readonly source: NodeIndex;
readonly target: NodeIndex;
}> {
constructor<E>(args: {
readonly data: E;
readonly source: number;
readonly target: number;
});
}Edge index for edge identification using plain numbers.
Signature
type EdgeIndex = number;EdgeWalker type
Type alias for edge iteration using Walker. EdgeWalker is represented as Walker<EdgeIndex, Edge<E>>.
Signature
type EdgeWalker<E> = Walker<EdgeIndex, Edge<E>>;ExternalsConfig interface
Configuration for externals iterator.
Signature
interface ExternalsConfig {
readonly direction?: Direction;
}Immutable graph interface.
Signature
interface Graph<out N, out E, T extends Kind = "directed"> extends Proto<N, E> {
readonly mutable: false;
readonly type: T;
}GraphVizOptions interface
Configuration options for GraphViz DOT format generation from graphs.
Signature
interface GraphVizOptions<N, E> {
readonly edgeLabel?: (data: E) => string;
readonly graphName?: string;
readonly nodeLabel?: (data: N) => string;
}Graph type for distinguishing directed and undirected graphs.
Signature
type Kind = "directed" | "undirected";MermaidDiagramType type
Mermaid diagram type.
Signature
type MermaidDiagramType = "flowchart" | "graph";MermaidDirection type
Mermaid diagram direction types.
Signature
type MermaidDirection = "TB" | "TD" | "BT" | "LR" | "RL";MermaidNodeShape type
Mermaid node shape types.
Signature
type MermaidNodeShape =
| "rectangle"
| "rounded"
| "circle"
| "diamond"
| "hexagon"
| "stadium"
| "subroutine"
| "cylindrical";MermaidOptions interface
Configuration options for Mermaid diagram generation.
Signature
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;
}MutableDirectedGraph type
Mutable directed graph type alias.
Signature
type MutableDirectedGraph<N, E> = MutableGraph<N, E, "directed">;MutableGraph interface
Mutable graph interface.
Signature
interface MutableGraph<out N, out E, T extends Kind = "directed"> extends Proto<N, E> {
readonly mutable: true;
readonly type: T;
}MutableUndirectedGraph type
Mutable undirected graph type alias.
Signature
type MutableUndirectedGraph<N, E> = MutableGraph<N, E, "undirected">;Node index for node identification using plain numbers.
Signature
type NodeIndex = number;NodeWalker type
Type alias for node iteration using Walker. NodeWalker is represented as Walker<NodeIndex, N>.
Signature
type NodeWalker<N> = Walker<NodeIndex, N>;PathResult interface
Result of a shortest path computation containing the path and total distance.
Signature
interface PathResult<E> {
readonly costs: Array<E>;
readonly distance: number;
readonly path: Array<number>;
}Graph prototype interface.
Signature
interface Proto<out N, out E>
extends Iterable<readonly [NodeIndex, N]>, Equal, Pipeable, Inspectable {
readonly "~effect/Graph": "~effect/Graph";
readonly adjacency: Map<number, Array<number>>;
readonly edges: Map<number, Edge<E>>;
isAcyclic: Option<boolean>;
nextEdgeIndex: number;
nextNodeIndex: number;
readonly nodes: Map<number, N>;
readonly reverseAdjacency: Map<number, Array<number>>;
}SearchConfig interface
Configuration for graph search iterators.
Signature
interface SearchConfig {
readonly direction?: Direction;
readonly start?: Array<number>;
}TopoConfig interface
Configuration options for topological sort iterator.
Signature
interface TopoConfig {
readonly initials?: Array<number>;
}UndirectedGraph type
Undirected graph type alias.
Signature
type UndirectedGraph<N, E> = Graph<N, E, "undirected">;Concrete class for iterables that produce [NodeIndex, NodeData] tuples.
This class provides a common abstraction for all iterables that return node data, including traversal iterators (DFS, BFS, etc.) and element iterators (nodes, externals). It uses a mapEntry function pattern for flexible iteration and transformation.
Signature
declare class Walker<T, N> implements Iterable<[T, N]> {
constructor<T, N>(visit: <U>(f: (index: T, data: N) => U) => Iterable<U>);
readonly [iterator]: () => Iterator<[T, N]>;
readonly visit: <U>(f: (index: T, data: N) => U) => Iterable<U>;
}Example
import { Graph } from "effect"
const graph = Graph.directed<string, number>((mutable) => {
const a = Graph.addNode(mutable, "A")
const b = Graph.addNode(mutable, "B")
Graph.addEdge(mutable, a, b, 1)
})
// Both traversal and element iterators return NodeWalker
const dfsNodes: Graph.NodeWalker<string> = Graph.dfs(graph, { start: [0] })
const allNodes: Graph.NodeWalker<string> = Graph.nodes(graph)
// Common interface for working with node iterables
function processNodes<N>(nodeIterable: Graph.NodeWalker<N>): Array<number> {
return Array.from(Graph.indices(nodeIterable))
}
// Access node data using values() or entries()
const nodeData = Array.from(Graph.values(dfsNodes)) // ["A", "B"]
const nodeEntries = Array.from(Graph.entries(allNodes)) // [[0, "A"], [1, "B"]]Mutations
Adds a new edge to a mutable graph and returns its index.
Signature
declare function addEdge<N, E, T extends Kind = "directed">(
mutable: MutableGraph<N, E, T>,
source: number,
target: number,
data: E,
): number;Adds a new node to a mutable graph and returns its index.
Signature
declare function addNode<N, E, T extends Kind = "directed">(
mutable: MutableGraph<N, E, T>,
data: N,
): number;beginMutation
Creates a mutable scope for safe graph mutations by copying the data structure.
Signature
declare function beginMutation<N, E, T extends Kind = "directed">(
graph: Graph<N, E, T>,
): MutableGraph<N, E, T>;endMutation
Converts a mutable graph back to an immutable graph, ending the mutation scope.
Signature
declare function endMutation<N, E, T extends Kind = "directed">(
mutable: MutableGraph<N, E, T>,
): Graph<N, E, T>;Performs scoped mutations on a graph, automatically managing the mutation lifecycle.
Signature
declare const mutate: {
<N, E, T extends Kind = "directed">(
f: (mutable: MutableGraph<N, E, T>) => void,
): (graph: Graph<N, E, T>) => Graph<N, E, T>;
<N, E, T extends Kind = "directed">(
graph: Graph<N, E, T>,
f: (mutable: MutableGraph<N, E, T>) => void,
): Graph<N, E, T>;
};Example
import { Graph } from "effect"
const graph = Graph.directed<string, number>()
const newGraph = Graph.mutate(graph, (mutable) => {
// Safe mutations go here
// mutable gets automatically converted back to immutable
})removeEdge
Removes an edge from a mutable graph.
Signature
declare function removeEdge<N, E, T extends Kind = "directed">(
mutable: MutableGraph<N, E, T>,
edgeIndex: number,
): void;removeNode
Removes a node and all its incident edges from a mutable graph.
Signature
declare function removeNode<N, E, T extends Kind = "directed">(
mutable: MutableGraph<N, E, T>,
nodeIndex: number,
): void;updateEdge
Updates a single edge's data by applying a transformation function.
Signature
declare function updateEdge<N, E, T extends Kind = "directed">(
mutable: MutableGraph<N, E, T>,
edgeIndex: number,
f: (data: E) => E,
): void;Queries
neighborsDirected
Get directed neighbors of a node in a specific direction.
Signature
declare function neighborsDirected<N, E>(
graph: Graph<N, E, "directed"> | MutableGraph<N, E, "directed">,
nodeIndex: number,
direction: Direction,
): Array<number>;predecessors
Returns the incoming neighbor node indices for a node in a directed graph.
Throws a GraphError when used with an undirected graph.
Signature
declare function predecessors<N, E>(
graph: Graph<N, E, "directed"> | MutableGraph<N, E, "directed">,
nodeIndex: number,
): Array<number>;successors
Returns the outgoing neighbor node indices for a node in a directed graph.
Throws a GraphError when used with an undirected graph.
Signature
declare function successors<N, E>(
graph: Graph<N, E, "directed"> | MutableGraph<N, E, "directed">,
nodeIndex: number,
): Array<number>;Symbol
Transformations
filterEdges
Filters edges by removing those that don't match the predicate. This function modifies the mutable graph in place.
Signature
declare function filterEdges<N, E, T extends Kind = "directed">(
mutable: MutableGraph<N, E, T>,
predicate: (data: E) => boolean,
): void;filterMapEdges
Filters and optionally transforms edges in a mutable graph using a predicate function. Edges that return Option.none are removed from the graph.
Signature
declare function filterMapEdges<N, E, T extends Kind = "directed">(
mutable: MutableGraph<N, E, T>,
f: (data: E) => Option<E>,
): void;filterMapNodes
Filters and optionally transforms nodes in a mutable graph using a predicate function. Nodes that return Option.none are removed along with all their connected edges.
Signature
declare function filterMapNodes<N, E, T extends Kind = "directed">(
mutable: MutableGraph<N, E, T>,
f: (data: N) => Option<N>,
): void;filterNodes
Filters nodes by removing those that don't match the predicate. This function modifies the mutable graph in place.
Signature
declare function filterNodes<N, E, T extends Kind = "directed">(
mutable: MutableGraph<N, E, T>,
predicate: (data: N) => boolean,
): void;Transforms all edge data in a mutable graph using the provided mapping function.
Signature
declare function mapEdges<N, E, T extends Kind = "directed">(
mutable: MutableGraph<N, E, T>,
f: (data: E) => E,
): void;Creates a new graph with transformed node data using the provided mapping function.
Signature
declare function mapNodes<N, E, T extends Kind = "directed">(
mutable: MutableGraph<N, E, T>,
f: (data: N) => N,
): void;Reverses all edge directions in a mutable graph by swapping source and target nodes.
Signature
declare function reverse<N, E, T extends Kind = "directed">(mutable: MutableGraph<N, E, T>): void;updateNode
Updates a single node's data by applying a transformation function.
Signature
declare function updateNode<N, E, T extends Kind = "directed">(
mutable: MutableGraph<N, E, T>,
index: number,
f: (data: N) => N,
): void;Utilities
Returns an iterator over [index, data] entries in the walker.
Signature
declare function entries<T, N>(walker: Walker<T, N>): Iterable<[T, N]>;Returns an iterator over the indices in the walker.
Signature
declare function indices<T, N>(walker: Walker<T, N>): Iterable<T>;Returns an iterator over the values (data) in the walker.
Signature
declare function values<T, N>(walker: Walker<T, N>): Iterable<N>;Utils
toGraphViz
Exports a graph to GraphViz DOT format for visualization.
Signature
declare function toGraphViz<N, E, T extends Kind = "directed">(
graph: Graph<N, E, T> | MutableGraph<N, E, T>,
options?: GraphVizOptions<N, E>,
): string;Exports a graph to Mermaid diagram format for visualization.
Signature
declare function toMermaid<N, E, T extends Kind = "directed">(
graph: Graph<N, E, T> | MutableGraph<N, E, T>,
options?: MermaidOptions<N, E>,
): string;
Find the shortest path between two nodes using A* pathfinding algorithm.
A* is an extension of Dijkstra's algorithm that uses a heuristic function to guide the search towards the target, potentially finding paths faster than Dijkstra's. The heuristic must be admissible (never overestimate the actual cost).