Graph
Models relationships between indexed nodes and edges.
This module provides immutable and scoped-mutable graph data structures. A graph can be directed or undirected, and it can store user-defined data on both nodes and edges. The module includes traversal, analysis, path-finding, transformation, and diagram export utilities.
Algorithms
Signature
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>>;
};bellmanFord
Finds the shortest path from the configured source node to the target node using the Bellman-Ford algorithm.
Details
Negative edge weights are allowed, and Infinity behaves like an impassable edge. Returns Option.none() when the target is unreachable or when a negative cycle affects the path to the target. Throws a GraphError when either endpoint is missing or an edge weight is NaN or -Infinity.
Signature
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>>;
};connectedComponents
Finds 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>>;Finds the shortest path from the configured source node to the target node using Dijkstra's algorithm.
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, and throws a GraphError when either endpoint is missing or an edge cost is negative or NaN.
Signature
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>>;
};floydWarshall
Finds shortest paths between all pairs of nodes using the Floyd-Warshall algorithm.
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. A GraphError is thrown if any edge weight is NaN or -Infinity, or if any negative cycle is detected.
Signature
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>;
};Checks whether the graph is acyclic (contains no cycles).
Details
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 use the same edge used to enter the current node 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 whether an undirected graph is bipartite.
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. Uses BFS coloring to determine bipartiteness.
Signature
declare function isBipartite<N, E>(
graph: Graph<N, E, "undirected"> | MutableGraph<N, E, "undirected">,
): boolean;stronglyConnectedComponents
Finds strongly connected components in a directed graph using Kosaraju's algorithm. Each SCC is represented as an array of node indices.
Gotchas
Throws a GraphError when used with an undirected graph.
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 const directed: <N, E>(
mutate?: (mutable: MutableDirectedGraph<N, E>) => undefined,
) => DirectedGraph<N, E>;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
directedfor constructing a directed graph directlyundirectedfor constructing an undirected graph directly
Signature
declare function make<T extends Kind>(
type: T,
): <N, E>(mutate?: (mutable: MutableGraph<N, E, T>) => undefined) => Graph<N, E, T>;undirected
Creates an undirected graph, optionally with initial mutations.
Signature
declare const undirected: <N, E>(
mutate?: (mutable: MutableUndirectedGraph<N, E>) => undefined,
) => UndirectedGraph<N, E>;Converting
toGraphViz
Exports a graph to GraphViz DOT format for visualization.
Signature
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;
};Exports a graph to Mermaid diagram format for visualization.
Details
Mermaid is a popular diagram-as-code tool that generates flowcharts and other visualizations from text-based definitions. This function converts Effect Graph structures to valid Mermaid syntax for use in documentation, web applications, and visualization tools.
Signature
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;
};Errors
GraphError
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.
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 const findEdge: {
<E>(
predicate: (data: E, source: number, target: number) => boolean,
): <N, T extends Kind = "directed">(
graph: Graph<N, E, T> | MutableGraph<N, E, T>,
) => Option<number>;
<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 const findEdges: {
<E>(
predicate: (data: E, source: number, target: number) => boolean,
): <N, T extends Kind = "directed">(
graph: Graph<N, E, T> | MutableGraph<N, E, T>,
) => Array<number>;
<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 const findNode: {
<N>(
predicate: (data: N) => boolean,
): <E, T extends Kind = "directed">(
graph: Graph<N, E, T> | MutableGraph<N, E, T>,
) => Option<number>;
<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 const findNodes: {
<N>(
predicate: (data: N) => boolean,
): <E, T extends Kind = "directed">(
graph: Graph<N, E, T> | MutableGraph<N, E, T>,
) => Array<number>;
<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 safely, if it exists.
Signature
declare const getEdge: {
(
edgeIndex: number,
): <N, E, T extends Kind = "directed">(
graph: Graph<N, E, T> | MutableGraph<N, E, T>,
) => Option<Edge<E>>;
<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 safely, if it exists.
Signature
declare const getNode: {
(
nodeIndex: number,
): <N, E, T extends Kind = "directed">(
graph: Graph<N, E, T> | MutableGraph<N, E, T>,
) => Option<N>;
<N, E, T extends Kind = "directed">(
graph: Graph<N, E, T> | MutableGraph<N, E, T>,
nodeIndex: number,
): Option<N>;
};Checks whether an edge exists between two nodes in the graph.
Signature
declare const hasEdge: {
(
source: number,
target: number,
): <N, E, T extends Kind = "directed">(graph: Graph<N, E, T> | MutableGraph<N, E, T>) => boolean;
<N, E, T extends Kind = "directed">(
graph: Graph<N, E, T> | MutableGraph<N, E, T>,
source: number,
target: number,
): boolean;
};Checks whether a node with the given index exists in the graph.
Signature
declare const hasNode: {
(
nodeIndex: number,
): <N, E, T extends Kind = "directed">(graph: Graph<N, E, T> | MutableGraph<N, E, T>) => boolean;
<N, E, T extends Kind = "directed">(
graph: Graph<N, E, T> | MutableGraph<N, E, T>,
nodeIndex: number,
): boolean;
};Returns the neighboring node indices for a node.
Details
For directed graphs, neighbors are the targets of outgoing edges. For undirected graphs, neighbors are the other endpoints of incident edges.
Signature
declare const neighbors: {
(
nodeIndex: number,
): <N, E, T extends Kind = "directed">(
graph: Graph<N, E, T> | MutableGraph<N, E, T>,
) => Array<number>;
<N, E, T extends Kind = "directed">(
graph: Graph<N, E, T> | MutableGraph<N, E, T>,
nodeIndex: number,
): Array<number>;
};neighborsDirected
Gets directed neighbors of a node in a specific direction.
When to use
Use when maintaining existing code that already passes an explicit traversal direction. New code should prefer successors or predecessors.
Gotchas
Throws a GraphError when used with an undirected graph.
See
successorsfor outgoing neighbors in a directed graphpredecessorsfor incoming neighbors in a directed graph
Signature
declare const neighborsDirected: {
(
nodeIndex: number,
direction: Direction,
): <N, E>(graph: Graph<N, E, "directed"> | MutableGraph<N, E, "directed">) => Array<number>;
<N, E>(
graph: Graph<N, E, "directed"> | MutableGraph<N, E, "directed">,
nodeIndex: number,
direction: Direction,
): 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;predecessors
Returns the incoming neighbor node indices for a node in a directed graph.
When to use
Use when you need the nodes that reach a node by following incoming edges in a directed graph.
Gotchas
Throws a GraphError when used with an undirected graph.
See
successorsfor outgoing neighbors in a directed graphneighborsfor generic neighbor lookup across graph kinds
Signature
declare const predecessors: {
(
nodeIndex: number,
): <N, E>(graph: Graph<N, E, "directed"> | MutableGraph<N, E, "directed">) => Array<number>;
<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.
When to use
Use when you need the nodes reached by following outgoing edges from a node in a directed graph.
Gotchas
Throws a GraphError when used with an undirected graph.
See
predecessorsfor incoming neighbors in a directed graphneighborsfor generic neighbor lookup across graph kinds
Signature
declare const successors: {
(
nodeIndex: number,
): <N, E>(graph: Graph<N, E, "directed"> | MutableGraph<N, E, "directed">) => Array<number>;
<N, E>(
graph: Graph<N, E, "directed"> | MutableGraph<N, E, "directed">,
nodeIndex: number,
): Array<number>;
};Guards
Returns true if a value has the graph runtime type identifier, narrowing it to an immutable or mutable graph.
When to use
Use to narrow an unknown value before treating it as a graph value.
Gotchas
This guard checks the shared graph runtime type identifier and does not distinguish immutable graphs from mutable graphs or directed graphs from undirected graphs.
Signature
declare function isGraph<N = unknown, E = unknown, T extends Kind = Kind, U = never>(
u: U | Graph<N, E, T> | MutableGraph<N, E, T>,
): u is Graph<N, E, T> | MutableGraph<N, E, T>;Iterators
Creates a lazy breadth-first traversal iterator from the configured start nodes.
Details
If no start nodes are supplied, the iterator is empty. The direction option chooses whether to follow outgoing or incoming edges. The radius option limits traversal by edge distance from the start nodes. Throws a GraphError if any configured start node does not exist.
Signature
declare const bfs: {
(
config?: SearchConfig,
): <N, E, T extends Kind = "directed">(
graph: Graph<N, E, T> | MutableGraph<N, E, T>,
) => NodeWalker<N>;
<N, E, T extends Kind = "directed">(
graph: Graph<N, E, T> | MutableGraph<N, E, T>,
config?: SearchConfig,
): NodeWalker<N>;
};Creates a lazy depth-first traversal iterator from the configured start nodes.
Details
If no start nodes are supplied, the iterator is empty. The direction option chooses whether to follow outgoing or incoming edges. The radius option limits traversal by edge distance from the start nodes. Throws a GraphError if any configured start node does not exist.
Signature
declare const dfs: {
(
config?: SearchConfig,
): <N, E, T extends Kind = "directed">(
graph: Graph<N, E, T> | MutableGraph<N, E, T>,
) => NodeWalker<N>;
<N, E, T extends Kind = "directed">(
graph: Graph<N, E, T> | MutableGraph<N, E, T>,
config?: SearchConfig,
): NodeWalker<N>;
};dfsPostOrder
Creates a lazy depth-first postorder traversal iterator from the configured start nodes.
Details
Nodes are emitted after their reachable descendants have been processed. If no start nodes are supplied, the iterator is empty. The direction option chooses whether to follow outgoing or incoming edges. The radius option limits traversal by edge distance from the start nodes.
Gotchas
With a finite radius, iteration first performs a bounded breadth-first traversal to determine shortest-distance membership before emitting nodes in postorder.
Signature
declare const dfsPostOrder: {
(
config?: SearchConfig,
): <N, E, T extends Kind = "directed">(
graph: Graph<N, E, T> | MutableGraph<N, E, T>,
) => NodeWalker<N>;
<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.
Details
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>;Returns an iterator over [index, data] entries in the walker.
Signature
declare function entries<T, N>(walker: Walker<T, N>): Iterable<[T, N]>;Creates an iterator over external nodes (nodes without edges in the specified direction).
Details
External nodes have no outgoing edges (direction: "outgoing") or no incoming edges (direction: "incoming"). These are useful for finding sources, sinks, or isolated nodes.
Signature
declare const externals: {
(
config?: ExternalsConfig,
): <N, E, T extends Kind = "directed">(
graph: Graph<N, E, T> | MutableGraph<N, E, T>,
) => NodeWalker<N>;
<N, E, T extends Kind = "directed">(
graph: Graph<N, E, T> | MutableGraph<N, E, T>,
config?: ExternalsConfig,
): NodeWalker<N>;
};Returns an iterator over the indices in the walker.
Signature
declare function indices<T, N>(walker: Walker<T, N>): Iterable<T>;Creates an iterator over all node indices in the graph.
Details
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.
Details
The iterator uses Kahn's algorithm to lazily produce nodes in topological order. Throws an error if the graph contains cycles.
Signature
declare const topo: {
(
config?: TopoConfig,
): <N, E>(graph: Graph<N, E, "directed"> | MutableGraph<N, E, "directed">) => NodeWalker<N>;
<N, E>(
graph: Graph<N, E, "directed"> | MutableGraph<N, E, "directed">,
config?: TopoConfig,
): NodeWalker<N>;
};Returns an iterator over the values (data) in the walker.
Signature
declare function values<T, N>(walker: Walker<T, N>): Iterable<N>;Models
AllPairsResult interface
Result of an all-pairs shortest path computation.
When to use
Use when storing or passing around the complete output of floydWarshall so callers can look up shortest distances, node paths, and edge data for any source and target node pair.
Details
Contains distance, node-path, and edge-data maps keyed by source and target node indices.
See
floydWarshallfor computing an all-pairs shortest path resultPathResultfor the single source-to-target result shape used by path-finding algorithms
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 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.
See
astarfor the algorithm that consumes this configurationDijkstraConfigfor shortest paths without a heuristicBellmanFordConfigfor shortest paths that may include negative edge weights
Signature
interface AstarConfig<E, N> {
cost: (edgeData: E) => number;
heuristic: (sourceNodeData: N, targetNodeData: N) => number;
source: number;
target: number;
}BellmanFordConfig interface
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.
See
bellmanFordfor the algorithm that consumes this configurationDijkstraConfigfor non-negative edge costsAstarConfigfor heuristic shortest-path search
Signature
interface BellmanFordConfig<E> {
cost: (edgeData: E) => number;
source: number;
target: number;
}DijkstraConfig interface
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.
See
dijkstrafor the algorithm that consumes this configurationAstarConfigfor heuristic shortest-path searchBellmanFordConfigfor shortest paths that may include negative edge weights
Signature
interface DijkstraConfig<E> {
cost: (edgeData: E) => number;
source: number;
target: number;
}DirectedGraph type
Immutable graph type for source-to-target relationships.
When to use
Use as the immutable graph type when edge direction is part of the model and traversal or neighbor queries should follow source-to-target edges.
Details
DirectedGraph<N, E> is a Graph<N, E, "directed"> with node data of type N and edge data of type E.
See
directedfor constructing directed graphsGraphfor the generic immutable graph typeUndirectedGraphfor graphs whose edges connect both endpointsMutableDirectedGraphfor the mutable directed graph type
Signature
type DirectedGraph<N, E> = Graph<N, E, "directed">;Direction of directed edges relative to a node.
Details
"outgoing" selects edges whose source is the node, while "incoming" selects edges whose target is the node.
Signature
type Direction = "outgoing" | "incoming";Represents edge data containing source, target, and user data.
When to use
Use as the graph edge value that carries source node, target node, and stored edge data together.
See
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.
When to use
Use when you need to keep the identifier for a graph edge so you can later read, update, remove, or compare that edge.
Gotchas
An EdgeIndex is an identifier, not an array offset. Removed edge identifiers are not reused.
See
Signature
type EdgeIndex = number;EdgeWalker type
Type alias for edge iteration using Walker. EdgeWalker is represented as Walker<EdgeIndex, Edge<E>>.
When to use
Use to type helpers or parameters that consume edge iterators returned by Graph APIs, where each item is keyed by an EdgeIndex and carries the full Edge.
See
Walkerfor the generic lazy iterator wrapperNodeWalkerfor node iteratorsedgesfor creating edge walkers
Signature
type EdgeWalker<E> = Walker<EdgeIndex, Edge<E>>;ExternalsConfig interface
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".
See
externalsfor the iterator that consumes this configuration
Signature
interface ExternalsConfig {
readonly direction?: Direction;
}Companion namespace containing type-level metadata for immutable graphs.
Immutable graph interface.
When to use
Use as the immutable graph model for code that queries, traverses, transforms, or analyzes graph structure without mutating it.
See
MutableGraphfor the mutable counterpart used inside mutation scopesDirectedGraphfor aGraphfixed to directed edgesUndirectedGraphfor aGraphfixed to undirected edges
Signature
interface Graph<out N, out E, T extends Kind = "directed"> extends Proto<N, E> {
readonly mutable: false;
readonly type: T;
}IdentityOptions interface
Configures node and edge identity for graph set operations.
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.
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.
Signature
interface IdentityOptions<N, E, NI = N, EI = E> {
readonly edgeIdentity?: (edge: E) => EI;
readonly nodeIdentity?: (node: N) => NI;
}Graph type for distinguishing directed and undirected graphs.
When to use
Use when writing graph-polymorphic types or helpers that need to preserve whether a graph is directed or undirected.
See
Graphfor immutable graphs parameterized by kindMutableGraphfor mutable graphs parameterized by kind
Signature
type Kind = "directed" | "undirected";MermaidDiagramType type
Mermaid diagram types for different visualization formats.
Details
Specifies the Mermaid diagram syntax to use: - flowchart: For directed graphs with arrows (A --> B) - graph: For undirected graphs with lines (A --- B)
When not specified, automatically selects based on graph type: directed graphs use "flowchart", undirected graphs use "graph".
Signature
type MermaidDiagramType = "flowchart" | "graph";MermaidDirection type
Mermaid diagram direction types for controlling layout orientation.
Details
Determines the flow direction of nodes and edges in the diagram: - TB/TD: Top to Bottom (vertical layout, default) - BT: Bottom to Top (reverse vertical) - LR: Left to Right (horizontal layout) - RL: Right to Left (reverse horizontal)
Signature
type MermaidDirection = "TB" | "TD" | "BT" | "RL" | "LR";MermaidNodeShape type
Mermaid node shape types for diagram visualization.
Details
Each shape produces different visual representations in Mermaid diagrams: - rectangle: Standard rectangular nodes A["label"] - rounded: Rounded rectangular nodes A("label") - circle: Circular nodes A(("label")) - diamond: Diamond-shaped nodes A{"label"} - hexagon: Hexagonal nodes A{{"label"}} - stadium: Stadium-shaped nodes A(["label"]) - subroutine: Subroutine-style nodes A[["label"]] - cylindrical: Cylindrical database-style nodes A[("label")]
Signature
type MermaidNodeShape =
| "rectangle"
| "rounded"
| "circle"
| "diamond"
| "hexagon"
| "stadium"
| "subroutine"
| "cylindrical";MutableDirectedGraph type
Mutable directed graph type alias.
When to use
Use when annotating a temporary graph value that can be changed in place and whose edges have source-to-target direction.
See
MutableGraphfor the generic mutable graph typeDirectedGraphfor the immutable directed graph typeMutableUndirectedGraphfor mutable graphs without edge direction
Signature
type MutableDirectedGraph<N, E> = MutableGraph<N, E, "directed">;MutableGraph
Companion namespace containing type-level metadata for scoped mutable graphs.
MutableGraph interface
Mutable graph interface.
When to use
Use when adding, removing, or updating nodes and edges inside a graph mutation scope.
See
Graphfor the immutable graph interfacemutatefor scoped mutation of an immutable graphbeginMutationfor opening a mutable graph manuallyendMutationfor returning to an immutable graph
Signature
interface MutableGraph<in out N, in out E, T extends Kind = "directed">
extends Iterable<readonly [NodeIndex, N]>, Equal, Pipeable, Inspectable {
readonly "~effect/collections/Graph": Variance<N, E>;
readonly mutable: true;
readonly type: T;
}MutableUndirectedGraph type
Mutable undirected graph type alias.
When to use
Use when annotating a temporary graph value that can be changed in place and whose edges connect both endpoints without direction.
See
MutableDirectedGraphfor mutable graphs with directed edgesUndirectedGraphfor the immutable undirected graph typeMutableGraphfor the generic mutable graph type
Signature
type MutableUndirectedGraph<N, E> = MutableGraph<N, E, "undirected">;NeighborhoodConfig interface
Configuration for selecting a graph neighborhood.
Details
radius limits the edge distance from the center node and defaults to 1. direction controls how directed edges are traversed and defaults to "outgoing".
Signature
interface NeighborhoodConfig {
readonly direction?: TraversalDirection;
readonly radius?: number;
}Node index for node identification using plain numbers.
When to use
Use when storing or passing the stable identifier of a graph node between Graph operations.
Details
addNode allocates node identifiers from the graph's next node index.
Gotchas
A NodeIndex is an identifier, not an array offset. Removed node identifiers are not reused.
See
Signature
type NodeIndex = number;NodeWalker type
Type alias for node iteration using Walker. NodeWalker is represented as Walker<NodeIndex, N>.
When to use
Use as the shared node walker type returned by graph traversal and node listing APIs.
See
Walkerfor the generic lazy iterator wrapperEdgeWalkerfor edge iterators
Signature
type NodeWalker<N> = Walker<NodeIndex, N>;PathResult interface
Result of a shortest path computation.
When to use
Use to read the successful source-to-target shortest path returned by path-finding algorithms, including the ordered node indices, total distance, and traversed edge data.
Details
Contains the node-index path, the total numeric distance, and the edge data encountered along the path.
Gotchas
costs contains original edge data, not the numeric output of the cost function unless the edge data is numeric.
See
dijkstrafor shortest paths with non-negative edge costsastarfor heuristic shortest-path searchbellmanFordfor shortest paths that may include negative edge weightsAllPairsResultfor the all-pairs shortest-path result shape
Signature
interface PathResult<E> {
readonly costs: Array<E>;
readonly distance: number;
readonly path: Array<number>;
}Common public protocol for graph values.
Details
Contains only the runtime marker and shared protocols. Graph storage is kept internal; use module functions such as nodes, edges, getNode, and getEdge to inspect graph contents.
Signature
interface Proto<out N, out E>
extends Iterable<readonly [NodeIndex, N]>, Equal, Pipeable, Inspectable {
readonly "~effect/collections/Graph": Variance<N, E>;
}SearchConfig interface
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. direction chooses whether traversal follows outgoing edges, incoming edges, or ignores edge direction. radius limits traversal by edge distance from the nearest start node.
Gotchas
Traversal creation throws a GraphError when any configured start node does not exist.
See
dfsfor depth-first traversalbfsfor breadth-first traversaldfsPostOrderfor depth-first postorder traversal
Signature
interface SearchConfig {
readonly direction?: TraversalDirection;
readonly radius?: number;
readonly start?: Array<number>;
}TopoConfig interface
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.
See
topofor the iterator that consumes this configuration
Signature
interface TopoConfig {
readonly initials?: Array<number>;
}TraversalDirection type
Controls how traversal follows directed edges.
Details
"outgoing" follows edges from source to target, "incoming" follows them from target to source, and "undirected" allows traversal in either direction.
Signature
type TraversalDirection = Direction | "undirected";UndirectedGraph type
Immutable graph type for relationships without source-to-target direction.
When to use
Use when modeling relationships where each edge connects both endpoints without a source-to-target direction.
Details
UndirectedGraph<N, E> is a Graph<N, E, "undirected">.
See
undirectedfor constructing undirected graphsDirectedGraphfor graphs whose edges have source-to-target directionMutableUndirectedGraphfor the mutable undirected graph type
Signature
type UndirectedGraph<N, E> = Graph<N, E, "undirected">;Represents an iterable wrapper used by graph traversal and listing APIs.
Details
A Walker yields [index, data] pairs lazily and can be viewed as just the indices, just the values, or mapped entries with indices, values, entries, and visit.
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>;
}Mutations
Adds a new edge to a mutable graph and returns its index.
When to use
Use to connect two existing nodes in a mutable graph while storing edge data and receiving the new edge identifier.
Details
Creates an Edge with the source, target, and data at the next edge index, updates adjacency indexes, and increments the graph's next edge index. Undirected graphs register the same edge for both endpoints.
Gotchas
The source and target nodes must already exist in the mutable graph; missing endpoints throw a GraphError.
See
mutatefor obtaining a mutable graph from an immutable graphaddNodefor creating node indexes before connecting themgetEdgefor reading the returned edgeremoveEdgefor removing an edge from a mutable graph
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.
When to use
Use to allocate a new node in a mutable graph before storing edges or querying it by index.
Details
The returned index is allocated from the graph's next node index. The mutable graph stores the node data and initializes empty incoming and outgoing edge indexes for the new node.
Gotchas
NodeIndex values are identifiers and are not reused after removals.
See
mutatefor obtaining a mutable graph from an immutable graphaddEdgefor connecting existing nodesremoveNodefor removing nodes from a mutable graph
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.
Details
Finalizes the mutable handle. Later public mutation operations on that handle fail with a GraphError.
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>) => undefined,
): (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>) => undefined,
): Graph<N, E, T>;
};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;Options
GraphVizOptions interface
Configuration options for GraphViz DOT format generation from graphs.
Details
These options customize node labels, edge labels, and graph naming in DOT format compatible with GraphViz tools.
Signature
interface GraphVizOptions<N, E> {
readonly edgeLabel?: (data: E) => string;
readonly graphName?: string;
readonly nodeLabel?: (data: N) => string;
}MermaidOptions interface
Configuration options for Mermaid diagram generation from graphs.
Details
These options customize node labels, edge labels, diagram type, layout direction, node shapes, and graph naming in Mermaid format.
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;
}Set Operations
complement
Returns the complement over the existing node set.
Details
Adds every missing edge between distinct nodes. The createEdge function receives the source and target node data for each added edge. The result has the same graph kind as self.
G' = {V, (V x V) \ E}
Signature
declare const complement: {
<N, E>(
createEdge: (source: N, target: N) => E,
): <T extends Kind = "directed">(self: Graph<N, E, T>) => Graph<N, E, T>;
<N, E, T extends Kind = "directed">(
self: Graph<N, E, T>,
createEdge: (source: N, target: N) => E,
): Graph<N, E, T>;
};Composes two graphs, merging nodes by identity.
Details
Nodes and edges present in both graphs use data from that. The result has the same graph kind as self. Throws a GraphError when the graph kinds do not match. nodeIdentity and edgeIdentity default to the complete node and edge data. Edge identity also includes the endpoint identities.
G1 โช G2 = {V1 โช V2, E1 โช E2}
Gotchas
Nodes with equal identities in one input graph are coalesced. The last node supplies the data, and redirected edges can collapse or become self-loops. Parallel edges with equal identities are also coalesced, with the last edge supplying the data.
Signature
declare const compose: {
<N, E, T extends Kind = "directed", NI = N, EI = E>(
that: Graph<N, E, T>,
options?: IdentityOptions<N, E, NI, EI>,
): (self: Graph<N, E, NoInfer<T>>) => Graph<N, E, T>;
<N, E, T extends Kind = "directed", NI = N, EI = E>(
self: Graph<N, E, T>,
that: Graph<N, E, NoInfer<T>>,
options?: IdentityOptions<N, E, NI, EI>,
): Graph<N, E, T>;
};difference
Returns self without edges also present in that.
Details
All nodes from self are preserved. Edges are matched by endpoint and edge identities. The result has the same graph kind as self. Throws a GraphError when the graph kinds do not match. nodeIdentity and edgeIdentity default to the complete node and edge data.
G1 \ G2 = {V1, E1 \ E2}
Gotchas
Nodes with equal identities in one input graph are coalesced. The last node supplies the data, and redirected edges can collapse or become self-loops. If that contains an edge identity, every parallel edge with that identity is removed from self.
Signature
declare const difference: {
<N, E, T extends Kind = "directed", NI = N, EI = E>(
that: Graph<N, E, T>,
options?: IdentityOptions<N, E, NI, EI>,
): (self: Graph<N, E, NoInfer<T>>) => Graph<N, E, T>;
<N, E, T extends Kind = "directed", NI = N, EI = E>(
self: Graph<N, E, T>,
that: Graph<N, E, NoInfer<T>>,
options?: IdentityOptions<N, E, NI, EI>,
): Graph<N, E, T>;
};intersection
Returns the intersection of two graphs, matching nodes by identity.
Details
Node data comes from self, and edge data comes from that. The result has the same graph kind as self. Throws a GraphError when the graph kinds do not match. nodeIdentity and edgeIdentity default to the complete node and edge data. Edge identity also includes the endpoint identities.
G1 โฉ G2 = {V1 โฉ V2, E1 โฉ E2}
Gotchas
Nodes with equal identities in one input graph are coalesced. The last node supplies the data, and redirected edges can collapse or become self-loops. The result contains at most one edge for each shared edge identity.
Signature
declare const intersection: {
<N, E, T extends Kind = "directed", NI = N, EI = E>(
that: Graph<N, E, T>,
options?: IdentityOptions<N, E, NI, EI>,
): (self: Graph<N, E, NoInfer<T>>) => Graph<N, E, T>;
<N, E, T extends Kind = "directed", NI = N, EI = E>(
self: Graph<N, E, T>,
that: Graph<N, E, NoInfer<T>>,
options?: IdentityOptions<N, E, NI, EI>,
): Graph<N, E, T>;
};neighborhood
Returns the induced subgraph containing nodes within a radius of a node.
Details
The radius option is the maximum edge distance from nodeIndex and defaults to 1. The direction option controls directed graph traversal and defaults to "outgoing". The result has the same graph kind as self and keeps all original edges whose endpoints are both reached. "undirected" ignores edge direction while finding reachable nodes.
Signature
declare const neighborhood: {
(
nodeIndex: number,
options?: NeighborhoodConfig,
): <N, E, T extends Kind = "directed">(self: Graph<N, E, T>) => Graph<N, E, T>;
<N, E, T extends Kind = "directed">(
self: Graph<N, E, T>,
nodeIndex: number,
options?: NeighborhoodConfig,
): Graph<N, E, T>;
};Returns the disjoint union of two graphs.
Details
Copies all nodes and edges from both graphs without merging equal node data. The result has the same graph kind as self. Throws a GraphError when the graph kinds do not match.
G1 + G2 = {disjoint V1 + V2, disjoint E1 + E2}
Signature
declare const sum: {
<N, E, T extends Kind>(that: Graph<N, E, T>): (self: Graph<N, E, NoInfer<T>>) => Graph<N, E, T>;
<N, E, T extends Kind>(self: Graph<N, E, T>, that: Graph<N, E, NoInfer<T>>): Graph<N, E, T>;
};symmetricDifference
Returns edges present in exactly one of two graphs.
Details
Keeps nodes from both graphs. Overlapping nodes use data from that. The result has the same graph kind as self. Throws a GraphError when the graph kinds do not match. nodeIdentity and edgeIdentity default to the complete node and edge data. Edge identity also includes the endpoint identities.
G1 ฮ G2 = {V1 โช V2, (E1 โช E2) \ (E1 โฉ E2)}
Gotchas
Edges with different projected identities are distinct. Nodes with equal identities in one input graph are coalesced. The last node supplies the data, and redirected edges can collapse or become self-loops. Parallel edges with equal identities are coalesced before the graphs are compared.
Signature
declare const symmetricDifference: {
<N, E, T extends Kind = "directed", NI = N, EI = E>(
that: Graph<N, E, T>,
options?: IdentityOptions<N, E, NI, EI>,
): (self: Graph<N, E, NoInfer<T>>) => Graph<N, E, T>;
<N, E, T extends Kind = "directed", NI = N, EI = E>(
self: Graph<N, E, T>,
that: Graph<N, E, NoInfer<T>>,
options?: IdentityOptions<N, E, NI, EI>,
): Graph<N, E, T>;
};Transforming
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;Transforms every node's data in a mutable graph in place using the provided mapping function.
Details
Node indices and edges are preserved; only the stored node data is replaced.
Signature
declare function mapNodes<N, E, T extends Kind = "directed">(
mutable: MutableGraph<N, E, T>,
f: (data: N) => N,
): void;Swaps source and target nodes for every edge in a mutable graph.
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;
Finds the shortest path from the configured source node to the target node using the A* pathfinding algorithm.
Details
The edge-cost function must return non-negative weights and not
NaN.Infinityis allowed and behaves like an impassable edge. The heuristic should be consistent to preserve shortest-path guarantees. ReturnsOption.none()when the target is not reachable, and throws aGraphErrorwhen either endpoint is missing or an edge cost is negative orNaN.