# Graph

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

The mental model:

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

## Common case: build a graph, then read it

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

```ts
import { Graph } from "effect"

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

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

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

### Topological order (a build order)

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

```ts
import { Graph } from "effect"

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

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

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

```ts
import { Graph } from "effect"

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

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

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

### Shortest path with Dijkstra

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

```ts
import { Graph, Option } from "effect"

const roads = Graph.directed<string, number>((m) => {
  const a = Graph.addNode(m, "A")
  const b = Graph.addNode(m, "B")
  const c = Graph.addNode(m, "C")
  Graph.addEdge(m, a, b, 5) // A -> B costs 5
  Graph.addEdge(m, a, c, 10) // A -> C costs 10
  Graph.addEdge(m, b, c, 2) // B -> C costs 2
})

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

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

### Visualizing a graph

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

```ts
import { Graph } from "effect"

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

console.log(Graph.toMermaid(deps))
```

produces:

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

---

# Reference

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

```ts
import { Graph } from "effect"

// Nodes: 0=A 1=B 2=C ; Edges: A->B (1), B->C (2), A->C (4)
const g = Graph.directed<string, number>((m) => {
  const a = Graph.addNode(m, "A")
  const b = Graph.addNode(m, "B")
  const c = Graph.addNode(m, "C")
  Graph.addEdge(m, a, b, 1)
  Graph.addEdge(m, b, c, 2)
  Graph.addEdge(m, a, c, 4)
})
```

## Types & errors

### NodeIndex

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

```ts
import { Graph } from "effect"

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

### EdgeIndex

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

```ts
import { Graph } from "effect"

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

### Edge

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

```ts
import { Graph, Option } from "effect"

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

### Kind

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

```ts
import type { Graph } from "effect"

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

### Graph

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

```ts
import type { Graph } from "effect"

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

### MutableGraph

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

```ts
import { Graph } from "effect"

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

### DirectedGraph

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

```ts
import type { Graph } from "effect"

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

### UndirectedGraph

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

```ts
import type { Graph } from "effect"

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

### MutableDirectedGraph

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

```ts
import type { Graph } from "effect"

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

### MutableUndirectedGraph

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

```ts
import type { Graph } from "effect"

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

### Direction

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

```ts
import { Graph } from "effect"

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

### GraphError

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

```ts
import { Graph } from "effect"

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

### isGraph

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

```ts
import { Graph } from "effect"

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

## Construction & mutation

### directed

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

```ts
import { Graph } from "effect"

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

### undirected

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

```ts
import { Graph } from "effect"

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

### beginMutation

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

```ts
import { Graph } from "effect"

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

### endMutation

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

```ts
import { Graph } from "effect"

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

### mutate

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

```ts
import { Graph } from "effect"

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

## Nodes

### addNode

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

```ts
import { Graph } from "effect"

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

### getNode

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

```ts
import { Graph } from "effect"

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

### hasNode

Returns whether a node index exists in the graph.

```ts
import { Graph } from "effect"

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

### nodeCount

The number of nodes in the graph.

```ts
import { Graph } from "effect"

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

### updateNode

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

```ts
import { Graph } from "effect"

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

### removeNode

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

```ts
import { Graph } from "effect"

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

### findNode

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

```ts
import { Graph } from "effect"

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

### findNodes

Returns every `NodeIndex` whose data matches a predicate.

```ts
import { Graph } from "effect"

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

### mapNodes

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

```ts
import { Graph } from "effect"

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

### filterNodes

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

```ts
import { Graph } from "effect"

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

### filterMapNodes

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

```ts
import { Graph, Option } from "effect"

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

## Edges

### addEdge

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

```ts
import { Graph } from "effect"

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

### getEdge

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

```ts
import { Graph, Option } from "effect"

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

### hasEdge

Returns whether a directed edge exists from `source` to `target`.

```ts
import { Graph } from "effect"

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

### edgeCount

The number of edges in the graph.

```ts
import { Graph } from "effect"

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

### updateEdge

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

```ts
import { Graph, Option } from "effect"

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

### removeEdge

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

```ts
import { Graph } from "effect"

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

### findEdge

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

```ts
import { Graph } from "effect"

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

### findEdges

Returns every matching `EdgeIndex`.

```ts
import { Graph } from "effect"

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

### mapEdges

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

```ts
import { Graph, Option } from "effect"

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

### filterEdges

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

```ts
import { Graph } from "effect"

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

### filterMapEdges

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

```ts
import { Graph, Option } from "effect"

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

## Structure & queries

### reverse

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

```ts
import { Graph } from "effect"

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

### neighbors

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

```ts
import { Graph } from "effect"

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

### neighborsDirected

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

```ts
import { Graph } from "effect"

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

### externals

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

```ts
import { Graph } from "effect"

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

### ExternalsConfig

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

```ts
import type { Graph } from "effect"

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

### nodes

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

```ts
import { Graph } from "effect"

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

### edges

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

```ts
import { Graph } from "effect"

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

## Traversal

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

### Walker

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

```ts
import { Graph } from "effect"

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

### NodeWalker

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

```ts
import type { Graph } from "effect"

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

### EdgeWalker

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

```ts
import { Graph } from "effect"

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

### indices

Iterates just the indices of a walker.

```ts
import { Graph } from "effect"

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

### values

Iterates just the data of a walker.

```ts
import { Graph } from "effect"

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

### entries

Iterates `[index, data]` pairs of a walker.

```ts
import { Graph } from "effect"

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

### dfs

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

```ts
import { Graph } from "effect"

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

### bfs

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

```ts
import { Graph } from "effect"

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

### dfsPostOrder

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

```ts
import { Graph } from "effect"

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

### topo

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

```ts
import { Graph } from "effect"

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

### SearchConfig

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

```ts
import { Graph } from "effect"

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

### TopoConfig

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

```ts
import type { Graph } from "effect"

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

## Algorithms

### isAcyclic

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

```ts
import { Graph } from "effect"

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

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

### isBipartite

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

```ts
import { Graph } from "effect"

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

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

### connectedComponents

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

```ts
import { Graph } from "effect"

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

### stronglyConnectedComponents

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

```ts
import { Graph } from "effect"

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

### dijkstra

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

```ts
import { Graph, Option } from "effect"

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

### DijkstraConfig

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

```ts
import type { Graph } from "effect"

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

### PathResult

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

```ts
import { Graph, Option } from "effect"

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

### floydWarshall

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

```ts
import { Graph } from "effect"

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

### AllPairsResult

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

```ts
import type { Graph } from "effect"

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

### astar

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

```ts
import { Graph, Option } from "effect"

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

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

### AstarConfig

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

```ts
import type { Graph } from "effect"

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

### bellmanFord

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

```ts
import { Graph, Option } from "effect"

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

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

### BellmanFordConfig

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

```ts
import type { Graph } from "effect"

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

## Export

### toGraphViz

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

```ts
import { Graph } from "effect"

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

### GraphVizOptions

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

```ts
import { Graph } from "effect"

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

### toMermaid

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

```ts
import { Graph } from "effect"

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

### MermaidOptions

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

```ts
import { Graph } from "effect"

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

### MermaidNodeShape

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

```ts
import type { Graph } from "effect"

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

### MermaidDirection

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

```ts
import type { Graph } from "effect"

const dir: Graph.MermaidDirection = "LR"
```

### MermaidDiagramType

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

```ts
import type { Graph } from "effect"

const t: Graph.MermaidDiagramType = "flowchart"
```