/**
 * The `Graph` module provides immutable and scoped-mutable graph data
 * structures for modeling relationships between indexed nodes and edges. A
 * graph can be directed or undirected, stores user-defined data on both nodes
 * and edges, and exposes traversal, analysis, path finding, transformation, and
 * diagram export utilities.
 *
 * **Mental model**
 *
 * - Nodes and edges are addressed by stable numeric indices: {@link NodeIndex}
 *   and {@link EdgeIndex}
 * - Node data has type `N`; edge data has type `E`
 * - {@link Graph} values are immutable snapshots; use {@link MutableGraph}
 *   through {@link mutate}, {@link beginMutation}, or constructor callbacks to
 *   add, remove, or update nodes and edges
 * - Directed graphs follow edge direction for neighbors and traversals, while
 *   undirected graphs treat each edge as connecting both endpoints
 * - Missing lookups return `Option`, while structurally invalid operations such
 *   as adding an edge to a missing node throw {@link GraphError}
 *
 * **Common tasks**
 *
 * - Create graphs: {@link directed}, {@link undirected}
 * - Mutate safely: {@link mutate}, {@link addNode}, {@link addEdge},
 *   {@link removeNode}, {@link removeEdge}
 * - Query contents: {@link getNode}, {@link getEdge}, {@link hasNode},
 *   {@link hasEdge}, {@link nodeCount}, {@link edgeCount}, {@link neighbors}
 * - Transform data: {@link updateNode}, {@link updateEdge}, {@link mapNodes},
 *   {@link mapEdges}, {@link filterNodes}, {@link filterEdges},
 *   {@link filterMapNodes}, {@link filterMapEdges}
 * - Traverse lazily: {@link dfs}, {@link bfs}, {@link topo},
 *   {@link dfsPostOrder}, {@link nodes}, {@link edges}, {@link Walker}
 * - Analyze structure: {@link isAcyclic}, {@link isBipartite},
 *   {@link connectedComponents}, {@link stronglyConnectedComponents},
 *   {@link externals}
 * - Find paths: {@link dijkstra}, {@link astar}, {@link bellmanFord},
 *   {@link floydWarshall}
 * - Export diagrams: {@link toGraphViz}, {@link toMermaid}
 *
 * **Gotchas**
 *
 * - Only mutable graphs can be changed. Create one with {@link mutate} or by
 *   passing a callback to {@link directed} / {@link undirected}.
 * - Traversal APIs return lazy {@link Walker} values. Use {@link indices},
 *   {@link values}, or {@link entries} to choose what each iteration yields.
 * - `NodeIndex` and `EdgeIndex` values are identifiers, not array offsets. They
 *   are not reused after removals.
 * - Shortest-path algorithms require a cost function. {@link dijkstra} and
 *   {@link astar} reject negative weights; use {@link bellmanFord} or
 *   {@link floydWarshall} when negative weights are part of the model.
 *
 * @since 4.0.0
 */
import * as Data from "./Data.js";
import * as Equal from "./Equal.js";
import { dual } from "./Function.js";
import * as Hash from "./Hash.js";
import { NodeInspectSymbol } from "./Inspectable.js";
import * as Option from "./Option.js";
import { pipeArguments } from "./Pipeable.js";
import { hasProperty } from "./Predicate.js";
const TypeId = "~effect/collections/Graph";
/**
 * Represents edge data containing source, target, and user data.
 *
 * **When to use**
 *
 * Use as the graph edge value returned by `getEdge` and `edges` when you need
 * the source node, target node, and stored edge data together.
 *
 * @see {@link getEdge} for reading a single edge by identifier
 * @see {@link addEdge} for adding edges to a graph
 * @see {@link edges} for iterating graph edges
 *
 * @category models
 * @since 3.18.0
 */
export class Edge extends Data.Class {}
// =============================================================================
// Proto Objects
// =============================================================================
/** @internal */
const ProtoGraph = {
  [TypeId]: TypeId,
  [Symbol.iterator]() {
    return this.nodes[Symbol.iterator]();
  },
  [NodeInspectSymbol]() {
    return this.toJSON();
  },
  [Equal.symbol](that) {
    if (isGraph(that)) {
      if (this.nodes.size !== that.nodes.size || this.edges.size !== that.edges.size || this.type !== that.type) {
        return false;
      }
      // Compare nodes
      for (const [nodeIndex, nodeData] of this.nodes) {
        if (!that.nodes.has(nodeIndex)) {
          return false;
        }
        const otherNodeData = that.nodes.get(nodeIndex);
        if (!Equal.equals(nodeData, otherNodeData)) {
          return false;
        }
      }
      // Compare edges
      for (const [edgeIndex, edgeData] of this.edges) {
        if (!that.edges.has(edgeIndex)) {
          return false;
        }
        const otherEdge = that.edges.get(edgeIndex);
        if (!Equal.equals(edgeData, otherEdge)) {
          return false;
        }
      }
      return true;
    }
    return false;
  },
  [Hash.symbol]() {
    let hash = Hash.string("Graph");
    hash = hash ^ Hash.string(this.type);
    hash = hash ^ Hash.number(this.nodes.size);
    hash = hash ^ Hash.number(this.edges.size);
    for (const [nodeIndex, nodeData] of this.nodes) {
      hash = hash ^ Hash.hash(nodeIndex) + Hash.hash(nodeData);
    }
    for (const [edgeIndex, edgeData] of this.edges) {
      hash = hash ^ Hash.hash(edgeIndex) + Hash.hash(edgeData);
    }
    return hash;
  },
  toJSON() {
    return {
      _id: "Graph",
      nodeCount: this.nodes.size,
      edgeCount: this.edges.size,
      type: this.type
    };
  },
  toString() {
    return `Graph(${this.type}, ${this.nodes.size}, ${this.edges.size})`;
  },
  pipe() {
    return pipeArguments(this, arguments);
  }
};
// =============================================================================
// Errors
// =============================================================================
// TODO: Do we need safe variants for these?
/**
 * 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.
 *
 * @category errors
 * @since 3.18.0
 */
export class GraphError extends /*#__PURE__*/Data.TaggedError("GraphError") {}
/** @internal */
const missingNode = node => new GraphError({
  message: `Node ${node} does not exist`
});
// =============================================================================
// Constructors
// =============================================================================
/**
 * Returns `true` if a value has the graph runtime type identifier, narrowing
 * it to a `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.
 *
 * @category guards
 * @since 4.0.0
 */
export const isGraph = u => hasProperty(u, TypeId);
/**
 * Creates a directed graph, optionally with initial mutations.
 *
 * **Example** (Creating a directed graph)
 *
 * ```ts
 * import { Graph } from "effect"
 *
 * // Directed graph with initial nodes and edges
 * const graph = Graph.directed<string, string>((mutable) => {
 *   const a = Graph.addNode(mutable, "A")
 *   const b = Graph.addNode(mutable, "B")
 *   const c = Graph.addNode(mutable, "C")
 *   Graph.addEdge(mutable, a, b, "A->B")
 *   Graph.addEdge(mutable, b, c, "B->C")
 * })
 * ```
 *
 * @category constructors
 * @since 3.18.0
 */
export const directed = mutate => {
  const graph = Object.create(ProtoGraph);
  graph.type = "directed";
  graph.nodes = new Map();
  graph.edges = new Map();
  graph.adjacency = new Map();
  graph.reverseAdjacency = new Map();
  graph.nextNodeIndex = 0;
  graph.nextEdgeIndex = 0;
  graph.acyclic = Option.some(true);
  graph.mutable = false;
  if (mutate) {
    const mutable = beginMutation(graph);
    mutate(mutable);
    return endMutation(mutable);
  }
  return graph;
};
/**
 * Creates an undirected graph, optionally with initial mutations.
 *
 * **Example** (Creating an undirected graph)
 *
 * ```ts
 * import { Graph } from "effect"
 *
 * // Undirected graph with initial nodes and edges
 * const graph = Graph.undirected<string, string>((mutable) => {
 *   const a = Graph.addNode(mutable, "A")
 *   const b = Graph.addNode(mutable, "B")
 *   const c = Graph.addNode(mutable, "C")
 *   Graph.addEdge(mutable, a, b, "A-B")
 *   Graph.addEdge(mutable, b, c, "B-C")
 * })
 * ```
 *
 * @category constructors
 * @since 3.18.0
 */
export const undirected = mutate => {
  const graph = Object.create(ProtoGraph);
  graph.type = "undirected";
  graph.nodes = new Map();
  graph.edges = new Map();
  graph.adjacency = new Map();
  graph.reverseAdjacency = new Map();
  graph.nextNodeIndex = 0;
  graph.nextEdgeIndex = 0;
  graph.acyclic = Option.some(true);
  graph.mutable = false;
  if (mutate) {
    const mutable = beginMutation(graph);
    mutate(mutable);
    return endMutation(mutable);
  }
  return graph;
};
// =============================================================================
// Scoped Mutable API
// =============================================================================
/**
 * Creates a mutable scope for safe graph mutations by copying the data structure.
 *
 * **Example** (Beginning a mutation scope)
 *
 * ```ts
 * import { Graph } from "effect"
 *
 * const graph = Graph.directed<string, number>()
 * const mutable = Graph.beginMutation(graph)
 * // Now mutable can be safely modified without affecting original graph
 * ```
 *
 * @category mutations
 * @since 3.18.0
 */
export const beginMutation = graph => {
  // Copy adjacency maps with deep cloned arrays
  const adjacency = new Map();
  const reverseAdjacency = new Map();
  for (const [nodeIndex, edges] of graph.adjacency) {
    adjacency.set(nodeIndex, [...edges]);
  }
  for (const [nodeIndex, edges] of graph.reverseAdjacency) {
    reverseAdjacency.set(nodeIndex, [...edges]);
  }
  const mutable = Object.create(ProtoGraph);
  mutable.type = graph.type;
  mutable.nodes = new Map(graph.nodes);
  mutable.edges = new Map(graph.edges);
  mutable.adjacency = adjacency;
  mutable.reverseAdjacency = reverseAdjacency;
  mutable.nextNodeIndex = graph.nextNodeIndex;
  mutable.nextEdgeIndex = graph.nextEdgeIndex;
  mutable.acyclic = graph.acyclic;
  mutable.mutable = true;
  return mutable;
};
/**
 * Converts a mutable graph back to an immutable graph, ending the mutation scope.
 *
 * **Example** (Ending a mutation scope)
 *
 * ```ts
 * import { Graph } from "effect"
 *
 * const graph = Graph.directed<string, number>()
 * const mutable = Graph.beginMutation(graph)
 * // ... perform mutations on mutable ...
 * const newGraph = Graph.endMutation(mutable)
 * ```
 *
 * @category mutations
 * @since 3.18.0
 */
export const endMutation = mutable => {
  const graph = Object.create(ProtoGraph);
  graph.type = mutable.type;
  graph.nodes = new Map(mutable.nodes);
  graph.edges = new Map(mutable.edges);
  graph.adjacency = mutable.adjacency;
  graph.reverseAdjacency = mutable.reverseAdjacency;
  graph.nextNodeIndex = mutable.nextNodeIndex;
  graph.nextEdgeIndex = mutable.nextEdgeIndex;
  graph.acyclic = mutable.acyclic;
  graph.mutable = false;
  return graph;
};
/**
 * Performs scoped mutations on a graph, automatically managing the mutation lifecycle.
 *
 * **Example** (Applying scoped mutations)
 *
 * ```ts
 * import { Graph } from "effect"
 *
 * const graph = Graph.directed<string, number>()
 * const newGraph = Graph.mutate(graph, (mutable) => {
 *   const nodeA = Graph.addNode(mutable, "A")
 *   const nodeB = Graph.addNode(mutable, "B")
 *   Graph.addEdge(mutable, nodeA, nodeB, 1)
 * })
 *
 * console.log(Graph.nodeCount(newGraph)) // 2
 * console.log(Graph.edgeCount(newGraph)) // 1
 * ```
 *
 * @category mutations
 * @since 3.18.0
 */
export const mutate = /*#__PURE__*/dual(2, (graph, f) => {
  const mutable = beginMutation(graph);
  f(mutable);
  return endMutation(mutable);
});
// =============================================================================
// Basic Node Operations
// =============================================================================
/**
 * 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.
 *
 * **Example** (Adding nodes)
 *
 * ```ts
 * import { Graph } from "effect"
 *
 * const result = Graph.mutate(Graph.directed<string, number>(), (mutable) => {
 *   const nodeA = Graph.addNode(mutable, "Node A")
 *   const nodeB = Graph.addNode(mutable, "Node B")
 *   console.log(nodeA) // NodeIndex with value 0
 *   console.log(nodeB) // NodeIndex with value 1
 * })
 * ```
 *
 * @see {@link mutate} for obtaining a mutable graph from an immutable graph
 * @see {@link addEdge} for connecting existing nodes
 * @see {@link removeNode} for removing nodes from a mutable graph
 *
 * @category mutations
 * @since 3.18.0
 */
export const addNode = (mutable, data) => {
  const nodeIndex = mutable.nextNodeIndex;
  // Add node data
  mutable.nodes.set(nodeIndex, data);
  // Initialize empty adjacency lists
  mutable.adjacency.set(nodeIndex, []);
  mutable.reverseAdjacency.set(nodeIndex, []);
  // Update graph allocators
  mutable.nextNodeIndex = mutable.nextNodeIndex + 1;
  return nodeIndex;
};
/**
 * Gets the data associated with a node index safely, if it exists.
 *
 * **Example** (Getting node data)
 *
 * ```ts
 * import { Graph, Option } from "effect"
 *
 * const graph = Graph.mutate(Graph.directed<string, number>(), (mutable) => {
 *   Graph.addNode(mutable, "Node A")
 * })
 *
 * const nodeIndex = 0
 * const nodeData = Graph.getNode(graph, nodeIndex)
 *
 * if (Option.isSome(nodeData)) {
 *   console.log(nodeData.value) // "Node A"
 * }
 * ```
 *
 * @category getters
 * @since 3.18.0
 */
export const getNode = /*#__PURE__*/dual(2, (graph, nodeIndex) => graph.nodes.has(nodeIndex) ? Option.some(graph.nodes.get(nodeIndex)) : Option.none());
/**
 * Checks whether a node with the given index exists in the graph.
 *
 * **Example** (Checking node existence)
 *
 * ```ts
 * import { Graph } from "effect"
 *
 * const graph = Graph.mutate(Graph.directed<string, number>(), (mutable) => {
 *   Graph.addNode(mutable, "Node A")
 * })
 *
 * const nodeIndex = 0
 * const exists = Graph.hasNode(graph, nodeIndex)
 * console.log(exists) // true
 *
 * const nonExistentIndex = 999
 * const notExists = Graph.hasNode(graph, nonExistentIndex)
 * console.log(notExists) // false
 * ```
 *
 * @category getters
 * @since 3.18.0
 */
export const hasNode = /*#__PURE__*/dual(2, (graph, nodeIndex) => graph.nodes.has(nodeIndex));
/**
 * Returns the number of nodes in the graph.
 *
 * **Example** (Counting nodes)
 *
 * ```ts
 * import { Graph } from "effect"
 *
 * const emptyGraph = Graph.directed<string, number>()
 * console.log(Graph.nodeCount(emptyGraph)) // 0
 *
 * const graphWithNodes = Graph.mutate(emptyGraph, (mutable) => {
 *   Graph.addNode(mutable, "Node A")
 *   Graph.addNode(mutable, "Node B")
 *   Graph.addNode(mutable, "Node C")
 * })
 *
 * console.log(Graph.nodeCount(graphWithNodes)) // 3
 * ```
 *
 * @category getters
 * @since 3.18.0
 */
export const nodeCount = graph => graph.nodes.size;
/**
 * Finds the first node that matches the given predicate.
 *
 * **Example** (Finding the first matching node)
 *
 * ```ts
 * import { Graph } from "effect"
 *
 * const graph = Graph.mutate(Graph.directed<string, number>(), (mutable) => {
 *   Graph.addNode(mutable, "Node A")
 *   Graph.addNode(mutable, "Node B")
 *   Graph.addNode(mutable, "Node C")
 * })
 *
 * const result = Graph.findNode(graph, (data) => data.startsWith("Node B"))
 * console.log(result) // Option.some(1)
 *
 * const notFound = Graph.findNode(graph, (data) => data === "Node D")
 * console.log(notFound) // Option.none()
 * ```
 *
 * @category getters
 * @since 3.18.0
 */
export const findNode = /*#__PURE__*/dual(2, (graph, predicate) => {
  for (const [index, data] of graph.nodes) {
    if (predicate(data)) {
      return Option.some(index);
    }
  }
  return Option.none();
});
/**
 * Finds all nodes that match the given predicate.
 *
 * **Example** (Finding matching nodes)
 *
 * ```ts
 * import { Graph } from "effect"
 *
 * const graph = Graph.mutate(Graph.directed<string, number>(), (mutable) => {
 *   Graph.addNode(mutable, "Start A")
 *   Graph.addNode(mutable, "Node B")
 *   Graph.addNode(mutable, "Start C")
 * })
 *
 * const result = Graph.findNodes(graph, (data) => data.startsWith("Start"))
 * console.log(result) // [0, 2]
 *
 * const empty = Graph.findNodes(graph, (data) => data === "Not Found")
 * console.log(empty) // []
 * ```
 *
 * @category getters
 * @since 3.18.0
 */
export const findNodes = /*#__PURE__*/dual(2, (graph, predicate) => {
  const results = [];
  for (const [index, data] of graph.nodes) {
    if (predicate(data)) {
      results.push(index);
    }
  }
  return results;
});
/**
 * Finds the first edge that matches the given predicate.
 *
 * **Example** (Finding the first matching edge)
 *
 * ```ts
 * import { Graph } from "effect"
 *
 * const graph = Graph.mutate(Graph.directed<string, number>(), (mutable) => {
 *   const nodeA = Graph.addNode(mutable, "Node A")
 *   const nodeB = Graph.addNode(mutable, "Node B")
 *   const nodeC = Graph.addNode(mutable, "Node C")
 *   Graph.addEdge(mutable, nodeA, nodeB, 10)
 *   Graph.addEdge(mutable, nodeB, nodeC, 20)
 * })
 *
 * const result = Graph.findEdge(graph, (data) => data > 15)
 * console.log(result) // Option.some(1)
 *
 * const notFound = Graph.findEdge(graph, (data) => data > 100)
 * console.log(notFound) // Option.none()
 * ```
 *
 * @category getters
 * @since 3.18.0
 */
export const findEdge = /*#__PURE__*/dual(2, (graph, predicate) => {
  for (const [edgeIndex, edgeData] of graph.edges) {
    if (predicate(edgeData.data, edgeData.source, edgeData.target)) {
      return Option.some(edgeIndex);
    }
  }
  return Option.none();
});
/**
 * Finds all edges that match the given predicate.
 *
 * **Example** (Finding matching edges)
 *
 * ```ts
 * import { Graph } from "effect"
 *
 * const graph = Graph.mutate(Graph.directed<string, number>(), (mutable) => {
 *   const nodeA = Graph.addNode(mutable, "Node A")
 *   const nodeB = Graph.addNode(mutable, "Node B")
 *   const nodeC = Graph.addNode(mutable, "Node C")
 *   Graph.addEdge(mutable, nodeA, nodeB, 10)
 *   Graph.addEdge(mutable, nodeB, nodeC, 20)
 *   Graph.addEdge(mutable, nodeC, nodeA, 30)
 * })
 *
 * const result = Graph.findEdges(graph, (data) => data >= 20)
 * console.log(result) // [1, 2]
 *
 * const empty = Graph.findEdges(graph, (data) => data > 100)
 * console.log(empty) // []
 * ```
 *
 * @category getters
 * @since 3.18.0
 */
export const findEdges = /*#__PURE__*/dual(2, (graph, predicate) => {
  const results = [];
  for (const [edgeIndex, edgeData] of graph.edges) {
    if (predicate(edgeData.data, edgeData.source, edgeData.target)) {
      results.push(edgeIndex);
    }
  }
  return results;
});
/**
 * Updates a single node's data by applying a transformation function.
 *
 * **Example** (Updating node data)
 *
 * ```ts
 * import { Graph } from "effect"
 *
 * const graph = Graph.directed<string, number>((mutable) => {
 *   Graph.addNode(mutable, "Node A")
 *   Graph.addNode(mutable, "Node B")
 *   Graph.updateNode(mutable, 0, (data) => data.toUpperCase())
 * })
 *
 * const nodeData = Graph.getNode(graph, 0)
 * console.log(nodeData) // Option.some("NODE A")
 * ```
 *
 * @category transforming
 * @since 3.18.0
 */
export const updateNode = (mutable, index, f) => {
  if (!mutable.nodes.has(index)) {
    return;
  }
  const currentData = mutable.nodes.get(index);
  const newData = f(currentData);
  mutable.nodes.set(index, newData);
};
/**
 * Updates a single edge's data by applying a transformation function.
 *
 * **Example** (Updating edge data)
 *
 * ```ts
 * import { Graph } from "effect"
 *
 * const result = Graph.mutate(Graph.directed<string, number>(), (mutable) => {
 *   const nodeA = Graph.addNode(mutable, "Node A")
 *   const nodeB = Graph.addNode(mutable, "Node B")
 *   const edgeIndex = Graph.addEdge(mutable, nodeA, nodeB, 10)
 *   Graph.updateEdge(mutable, edgeIndex, (data) => data * 2)
 * })
 *
 * const edgeData = Graph.getEdge(result, 0)
 * console.log(edgeData) // Option.some(new Graph.Edge({ source: 0, target: 1, data: 20 }))
 * ```
 *
 * @category mutations
 * @since 3.18.0
 */
export const updateEdge = (mutable, edgeIndex, f) => {
  if (!mutable.edges.has(edgeIndex)) {
    return;
  }
  const currentEdge = mutable.edges.get(edgeIndex);
  const newData = f(currentEdge.data);
  mutable.edges.set(edgeIndex, new Edge({
    ...currentEdge,
    data: newData
  }));
};
/**
 * 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.
 *
 * **Example** (Mapping node data)
 *
 * ```ts
 * import { Graph } from "effect"
 *
 * const graph = Graph.directed<string, number>((mutable) => {
 *   Graph.addNode(mutable, "node a")
 *   Graph.addNode(mutable, "node b")
 *   Graph.addNode(mutable, "node c")
 *   Graph.mapNodes(mutable, (data) => data.toUpperCase())
 * })
 *
 * const nodeData = Graph.getNode(graph, 0)
 * console.log(nodeData) // Option.some("NODE A")
 * ```
 *
 * @category transforming
 * @since 3.18.0
 */
export const mapNodes = (mutable, f) => {
  // Transform existing node data in place
  for (const [index, data] of mutable.nodes) {
    const newData = f(data);
    mutable.nodes.set(index, newData);
  }
};
/**
 * Transforms all edge data in a mutable graph using the provided mapping function.
 *
 * **Example** (Mapping edge data)
 *
 * ```ts
 * import { Graph } from "effect"
 *
 * const graph = Graph.directed<string, number>((mutable) => {
 *   const a = Graph.addNode(mutable, "A")
 *   const b = Graph.addNode(mutable, "B")
 *   const c = Graph.addNode(mutable, "C")
 *   Graph.addEdge(mutable, a, b, 10)
 *   Graph.addEdge(mutable, b, c, 20)
 *   Graph.mapEdges(mutable, (data) => data * 2)
 * })
 *
 * const edgeData = Graph.getEdge(graph, 0)
 * console.log(edgeData) // Option.some(new Graph.Edge({ source: 0, target: 1, data: 20 }))
 * ```
 *
 * @category transforming
 * @since 3.18.0
 */
export const mapEdges = (mutable, f) => {
  // Transform existing edge data in place
  for (const [index, edgeData] of mutable.edges) {
    const newData = f(edgeData.data);
    mutable.edges.set(index, {
      ...edgeData,
      data: newData
    });
  }
};
/**
 * Swaps source and target nodes for every edge in a mutable graph.
 *
 * **Example** (Reversing edge directions)
 *
 * ```ts
 * import { Graph } from "effect"
 *
 * const graph = Graph.directed<string, number>((mutable) => {
 *   const a = Graph.addNode(mutable, "A")
 *   const b = Graph.addNode(mutable, "B")
 *   const c = Graph.addNode(mutable, "C")
 *   Graph.addEdge(mutable, a, b, 1) // A -> B
 *   Graph.addEdge(mutable, b, c, 2) // B -> C
 *   Graph.reverse(mutable) // Now B -> A, C -> B
 * })
 *
 * const edge0 = Graph.getEdge(graph, 0)
 * console.log(edge0) // Option.some(new Graph.Edge({ source: 1, target: 0, data: 1 }))
 * ```
 *
 * @category transforming
 * @since 3.18.0
 */
export const reverse = mutable => {
  // Reverse all edges by swapping source and target
  for (const [index, edgeData] of mutable.edges) {
    mutable.edges.set(index, new Edge({
      source: edgeData.target,
      target: edgeData.source,
      data: edgeData.data
    }));
  }
  // Clear and rebuild adjacency lists with reversed directions
  mutable.adjacency.clear();
  mutable.reverseAdjacency.clear();
  // Rebuild adjacency lists with reversed directions
  for (const [edgeIndex, edgeData] of mutable.edges) {
    // Add to forward adjacency (source -> target)
    const sourceEdges = mutable.adjacency.get(edgeData.source) || [];
    sourceEdges.push(edgeIndex);
    mutable.adjacency.set(edgeData.source, sourceEdges);
    // Add to reverse adjacency (target <- source)
    const targetEdges = mutable.reverseAdjacency.get(edgeData.target) || [];
    targetEdges.push(edgeIndex);
    mutable.reverseAdjacency.set(edgeData.target, targetEdges);
  }
  // Invalidate cycle flag since edge directions changed
  mutable.acyclic = Option.none();
};
/**
 * 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.
 *
 * **Example** (Filtering and mapping nodes)
 *
 * ```ts
 * import { Graph, Option } from "effect"
 *
 * const graph = Graph.directed<string, number>((mutable) => {
 *   const a = Graph.addNode(mutable, "active")
 *   const b = Graph.addNode(mutable, "inactive")
 *   const c = Graph.addNode(mutable, "active")
 *   Graph.addEdge(mutable, a, b, 1)
 *   Graph.addEdge(mutable, b, c, 2)
 *
 *   // Keep only "active" nodes and transform to uppercase
 *   Graph.filterMapNodes(
 *     mutable,
 *     (data) =>
 *       data === "active" ? Option.some(data.toUpperCase()) : Option.none()
 *   )
 * })
 *
 * console.log(Graph.nodeCount(graph)) // 2 (only "active" nodes remain)
 * ```
 *
 * @category transforming
 * @since 3.18.0
 */
export const filterMapNodes = (mutable, f) => {
  const nodesToRemove = [];
  // First pass: identify nodes to remove and transform data for nodes to keep
  for (const [index, data] of mutable.nodes) {
    const result = f(data);
    if (Option.isSome(result)) {
      // Transform node data
      mutable.nodes.set(index, result.value);
    } else {
      // Mark for removal
      nodesToRemove.push(index);
    }
  }
  // Second pass: remove filtered out nodes and their edges
  for (const nodeIndex of nodesToRemove) {
    removeNode(mutable, nodeIndex);
  }
};
/**
 * Filters and optionally transforms edges in a mutable graph using a predicate function.
 * Edges that return Option.none are removed from the graph.
 *
 * **Example** (Filtering and mapping edges)
 *
 * ```ts
 * import { Graph, Option } from "effect"
 *
 * const graph = Graph.directed<string, number>((mutable) => {
 *   const a = Graph.addNode(mutable, "A")
 *   const b = Graph.addNode(mutable, "B")
 *   const c = Graph.addNode(mutable, "C")
 *   Graph.addEdge(mutable, a, b, 5)
 *   Graph.addEdge(mutable, b, c, 15)
 *   Graph.addEdge(mutable, c, a, 25)
 *
 *   // Keep only edges with weight >= 10 and double their weight
 *   Graph.filterMapEdges(
 *     mutable,
 *     (data) => data >= 10 ? Option.some(data * 2) : Option.none()
 *   )
 * })
 *
 * console.log(Graph.edgeCount(graph)) // 2 (edges with weight 5 removed)
 * ```
 *
 * @category transforming
 * @since 3.18.0
 */
export const filterMapEdges = (mutable, f) => {
  const edgesToRemove = [];
  // First pass: identify edges to remove and transform data for edges to keep
  for (const [index, edgeData] of mutable.edges) {
    const result = f(edgeData.data);
    if (Option.isSome(result)) {
      // Transform edge data
      mutable.edges.set(index, {
        ...edgeData,
        data: result.value
      });
    } else {
      // Mark for removal
      edgesToRemove.push(index);
    }
  }
  // Second pass: remove filtered out edges
  for (const edgeIndex of edgesToRemove) {
    removeEdge(mutable, edgeIndex);
  }
};
/**
 * Filters nodes by removing those that don't match the predicate.
 * This function modifies the mutable graph in place.
 *
 * **Example** (Filtering nodes)
 *
 * ```ts
 * import { Graph } from "effect"
 *
 * const graph = Graph.directed<string, number>((mutable) => {
 *   Graph.addNode(mutable, "active")
 *   Graph.addNode(mutable, "inactive")
 *   Graph.addNode(mutable, "pending")
 *   Graph.addNode(mutable, "active")
 *
 *   // Keep only "active" nodes
 *   Graph.filterNodes(mutable, (data) => data === "active")
 * })
 *
 * console.log(Graph.nodeCount(graph)) // 2 (only "active" nodes remain)
 * ```
 *
 * @category transforming
 * @since 3.18.0
 */
export const filterNodes = (mutable, predicate) => {
  const nodesToRemove = [];
  // Identify nodes to remove
  for (const [index, data] of mutable.nodes) {
    if (!predicate(data)) {
      nodesToRemove.push(index);
    }
  }
  // Remove filtered out nodes (this also removes connected edges)
  for (const nodeIndex of nodesToRemove) {
    removeNode(mutable, nodeIndex);
  }
};
/**
 * Filters edges by removing those that don't match the predicate.
 * This function modifies the mutable graph in place.
 *
 * **Example** (Filtering edges)
 *
 * ```ts
 * import { Graph } from "effect"
 *
 * const graph = Graph.directed<string, number>((mutable) => {
 *   const a = Graph.addNode(mutable, "A")
 *   const b = Graph.addNode(mutable, "B")
 *   const c = Graph.addNode(mutable, "C")
 *
 *   Graph.addEdge(mutable, a, b, 5)
 *   Graph.addEdge(mutable, b, c, 15)
 *   Graph.addEdge(mutable, c, a, 25)
 *
 *   // Keep only edges with weight >= 10
 *   Graph.filterEdges(mutable, (data) => data >= 10)
 * })
 *
 * console.log(Graph.edgeCount(graph)) // 2 (edge with weight 5 removed)
 * ```
 *
 * @category transforming
 * @since 3.18.0
 */
export const filterEdges = (mutable, predicate) => {
  const edgesToRemove = [];
  // Identify edges to remove
  for (const [index, edgeData] of mutable.edges) {
    if (!predicate(edgeData.data)) {
      edgesToRemove.push(index);
    }
  }
  // Remove filtered out edges
  for (const edgeIndex of edgesToRemove) {
    removeEdge(mutable, edgeIndex);
  }
};
// =============================================================================
// Cycle Flag Management (Internal)
// =============================================================================
/** @internal */
const invalidateCycleFlagOnRemoval = mutable => {
  // Only invalidate if the graph had cycles (removing edges/nodes cannot introduce cycles in acyclic graphs).
  if (mutable.acyclic._tag === "Some" && mutable.acyclic.value === false) {
    mutable.acyclic = Option.none();
  }
};
/** @internal */
const invalidateCycleFlagOnAddition = mutable => {
  // Only invalidate if the graph was acyclic (adding edges cannot remove cycles from cyclic graphs).
  if (mutable.acyclic._tag === "Some" && mutable.acyclic.value === true) {
    mutable.acyclic = Option.none();
  }
};
// =============================================================================
// Edge Operations
// =============================================================================
/**
 * 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`.
 *
 * **Example** (Adding edges)
 *
 * ```ts
 * import { Graph } from "effect"
 *
 * const result = Graph.mutate(Graph.directed<string, number>(), (mutable) => {
 *   const nodeA = Graph.addNode(mutable, "Node A")
 *   const nodeB = Graph.addNode(mutable, "Node B")
 *   const edge = Graph.addEdge(mutable, nodeA, nodeB, 42)
 *   console.log(edge) // EdgeIndex with value 0
 * })
 * ```
 *
 * @see {@link mutate} for obtaining a mutable graph from an immutable graph
 * @see {@link addNode} for creating node indexes before connecting them
 * @see {@link getEdge} for reading the returned edge
 * @see {@link removeEdge} for removing an edge from a mutable graph
 *
 * @category mutations
 * @since 3.18.0
 */
export const addEdge = (mutable, source, target, data) => {
  // Validate that both nodes exist
  if (!mutable.nodes.has(source)) {
    throw missingNode(source);
  }
  if (!mutable.nodes.has(target)) {
    throw missingNode(target);
  }
  const edgeIndex = mutable.nextEdgeIndex;
  // Create edge data
  const edgeData = new Edge({
    source,
    target,
    data
  });
  mutable.edges.set(edgeIndex, edgeData);
  // Update adjacency lists
  const sourceAdjacency = mutable.adjacency.get(source);
  if (sourceAdjacency !== undefined) {
    sourceAdjacency.push(edgeIndex);
  }
  const targetReverseAdjacency = mutable.reverseAdjacency.get(target);
  if (targetReverseAdjacency !== undefined) {
    targetReverseAdjacency.push(edgeIndex);
  }
  // For undirected graphs, add reverse connections
  if (mutable.type === "undirected") {
    const targetAdjacency = mutable.adjacency.get(target);
    if (targetAdjacency !== undefined) {
      targetAdjacency.push(edgeIndex);
    }
    const sourceReverseAdjacency = mutable.reverseAdjacency.get(source);
    if (sourceReverseAdjacency !== undefined) {
      sourceReverseAdjacency.push(edgeIndex);
    }
  }
  // Update allocators
  mutable.nextEdgeIndex = mutable.nextEdgeIndex + 1;
  // Only invalidate cycle flag if the graph was acyclic
  // Adding edges cannot remove cycles from cyclic graphs
  invalidateCycleFlagOnAddition(mutable);
  return edgeIndex;
};
/**
 * Removes a node and all its incident edges from a mutable graph.
 *
 * **Example** (Removing a node)
 *
 * ```ts
 * import { Graph } from "effect"
 *
 * const result = Graph.mutate(Graph.directed<string, number>(), (mutable) => {
 *   const nodeA = Graph.addNode(mutable, "Node A")
 *   const nodeB = Graph.addNode(mutable, "Node B")
 *   Graph.addEdge(mutable, nodeA, nodeB, 42)
 *
 *   // Remove nodeA and all edges connected to it
 *   Graph.removeNode(mutable, nodeA)
 * })
 * ```
 *
 * @category mutations
 * @since 3.18.0
 */
export const removeNode = (mutable, nodeIndex) => {
  // Check if node exists
  if (!mutable.nodes.has(nodeIndex)) {
    return; // Node doesn't exist, nothing to remove
  }
  // Collect all incident edges for removal
  const edgesToRemove = [];
  // Get outgoing edges
  const outgoingEdges = mutable.adjacency.get(nodeIndex);
  if (outgoingEdges !== undefined) {
    for (const edge of outgoingEdges) {
      edgesToRemove.push(edge);
    }
  }
  // Get incoming edges
  const incomingEdges = mutable.reverseAdjacency.get(nodeIndex);
  if (incomingEdges !== undefined) {
    for (const edge of incomingEdges) {
      edgesToRemove.push(edge);
    }
  }
  // Remove all incident edges
  for (const edgeIndex of edgesToRemove) {
    removeEdgeInternal(mutable, edgeIndex);
  }
  // Remove the node itself
  mutable.nodes.delete(nodeIndex);
  mutable.adjacency.delete(nodeIndex);
  mutable.reverseAdjacency.delete(nodeIndex);
  // Only invalidate cycle flag if the graph wasn't already known to be acyclic
  // Removing nodes cannot introduce cycles in an acyclic graph
  invalidateCycleFlagOnRemoval(mutable);
};
/**
 * Removes an edge from a mutable graph.
 *
 * **Example** (Removing an edge)
 *
 * ```ts
 * import { Graph } from "effect"
 *
 * const result = Graph.mutate(Graph.directed<string, number>(), (mutable) => {
 *   const nodeA = Graph.addNode(mutable, "Node A")
 *   const nodeB = Graph.addNode(mutable, "Node B")
 *   const edge = Graph.addEdge(mutable, nodeA, nodeB, 42)
 *
 *   // Remove the edge
 *   Graph.removeEdge(mutable, edge)
 * })
 * ```
 *
 * @category mutations
 * @since 3.18.0
 */
export const removeEdge = (mutable, edgeIndex) => {
  const wasRemoved = removeEdgeInternal(mutable, edgeIndex);
  // Only invalidate cycle flag if an edge was actually removed
  // and only if the graph wasn't already known to be acyclic
  if (wasRemoved) {
    invalidateCycleFlagOnRemoval(mutable);
  }
};
/** @internal */
const removeEdgeInternal = (mutable, edgeIndex) => {
  // Get edge data
  const edge = mutable.edges.get(edgeIndex);
  if (edge === undefined) {
    return false; // Edge doesn't exist, no mutation occurred
  }
  const {
    source,
    target
  } = edge;
  // Remove from adjacency lists
  const sourceAdjacency = mutable.adjacency.get(source);
  if (sourceAdjacency !== undefined) {
    const index = sourceAdjacency.indexOf(edgeIndex);
    if (index !== -1) {
      sourceAdjacency.splice(index, 1);
    }
  }
  const targetReverseAdjacency = mutable.reverseAdjacency.get(target);
  if (targetReverseAdjacency !== undefined) {
    const index = targetReverseAdjacency.indexOf(edgeIndex);
    if (index !== -1) {
      targetReverseAdjacency.splice(index, 1);
    }
  }
  // For undirected graphs, remove reverse connections
  if (mutable.type === "undirected") {
    const targetAdjacency = mutable.adjacency.get(target);
    if (targetAdjacency !== undefined) {
      const index = targetAdjacency.indexOf(edgeIndex);
      if (index !== -1) {
        targetAdjacency.splice(index, 1);
      }
    }
    const sourceReverseAdjacency = mutable.reverseAdjacency.get(source);
    if (sourceReverseAdjacency !== undefined) {
      const index = sourceReverseAdjacency.indexOf(edgeIndex);
      if (index !== -1) {
        sourceReverseAdjacency.splice(index, 1);
      }
    }
  }
  // Remove edge data
  mutable.edges.delete(edgeIndex);
  return true; // Edge was successfully removed
};
// =============================================================================
// Edge Query Operations
// =============================================================================
/**
 * Gets the edge data associated with an edge index safely, if it exists.
 *
 * **Example** (Getting edge data)
 *
 * ```ts
 * import { Graph } from "effect"
 *
 * const graph = Graph.mutate(Graph.directed<string, number>(), (mutable) => {
 *   const nodeA = Graph.addNode(mutable, "Node A")
 *   const nodeB = Graph.addNode(mutable, "Node B")
 *   Graph.addEdge(mutable, nodeA, nodeB, 42)
 * })
 *
 * const edgeIndex = 0
 * const edgeData = Graph.getEdge(graph, edgeIndex)
 *
 * if (edgeData._tag === "Some") {
 *   console.log(edgeData.value.data) // 42
 *   console.log(edgeData.value.source) // 0
 *   console.log(edgeData.value.target) // 1
 * }
 * ```
 *
 * @category getters
 * @since 3.18.0
 */
export const getEdge = /*#__PURE__*/dual(2, (graph, edgeIndex) => Option.fromUndefinedOr(graph.edges.get(edgeIndex)));
/**
 * Checks whether an edge exists between two nodes in the graph.
 *
 * **Example** (Checking edge existence)
 *
 * ```ts
 * import { Graph } from "effect"
 *
 * const graph = Graph.mutate(Graph.directed<string, number>(), (mutable) => {
 *   const nodeA = Graph.addNode(mutable, "Node A")
 *   const nodeB = Graph.addNode(mutable, "Node B")
 *   const nodeC = Graph.addNode(mutable, "Node C")
 *   Graph.addEdge(mutable, nodeA, nodeB, 42)
 * })
 *
 * const nodeA = 0
 * const nodeB = 1
 * const nodeC = 2
 *
 * const hasAB = Graph.hasEdge(graph, nodeA, nodeB)
 * console.log(hasAB) // true
 *
 * const hasAC = Graph.hasEdge(graph, nodeA, nodeC)
 * console.log(hasAC) // false
 * ```
 *
 * @category getters
 * @since 3.18.0
 */
export const hasEdge = /*#__PURE__*/dual(3, (graph, source, target) => {
  const adjacencyList = graph.adjacency.get(source);
  if (adjacencyList === undefined) {
    return false;
  }
  // Check if any edge in the adjacency list connects to the target
  for (const edgeIndex of adjacencyList) {
    const edge = graph.edges.get(edgeIndex);
    if (edge !== undefined && edge.target === target) {
      return true;
    }
  }
  return false;
});
/**
 * Returns the number of edges in the graph.
 *
 * **Example** (Counting edges)
 *
 * ```ts
 * import { Graph } from "effect"
 *
 * const emptyGraph = Graph.directed<string, number>()
 * console.log(Graph.edgeCount(emptyGraph)) // 0
 *
 * const graphWithEdges = Graph.mutate(emptyGraph, (mutable) => {
 *   const nodeA = Graph.addNode(mutable, "Node A")
 *   const nodeB = Graph.addNode(mutable, "Node B")
 *   const nodeC = Graph.addNode(mutable, "Node C")
 *   Graph.addEdge(mutable, nodeA, nodeB, 1)
 *   Graph.addEdge(mutable, nodeB, nodeC, 2)
 *   Graph.addEdge(mutable, nodeC, nodeA, 3)
 * })
 *
 * console.log(Graph.edgeCount(graphWithEdges)) // 3
 * ```
 *
 * @category getters
 * @since 3.18.0
 */
export const edgeCount = graph => graph.edges.size;
/**
 * 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.
 *
 * **Example** (Getting outgoing neighbors)
 *
 * ```ts
 * import { Graph } from "effect"
 *
 * const graph = Graph.mutate(Graph.directed<string, number>(), (mutable) => {
 *   const nodeA = Graph.addNode(mutable, "Node A")
 *   const nodeB = Graph.addNode(mutable, "Node B")
 *   const nodeC = Graph.addNode(mutable, "Node C")
 *   Graph.addEdge(mutable, nodeA, nodeB, 1)
 *   Graph.addEdge(mutable, nodeA, nodeC, 2)
 * })
 *
 * const nodeA = 0
 * const nodeB = 1
 * const nodeC = 2
 *
 * const neighborsA = Graph.neighbors(graph, nodeA)
 * console.log(neighborsA) // [1, 2]
 *
 * const neighborsB = Graph.neighbors(graph, nodeB)
 * console.log(neighborsB) // []
 * ```
 *
 * @category getters
 * @since 3.18.0
 */
export const neighbors = /*#__PURE__*/dual(2, (graph, nodeIndex) => {
  // For undirected graphs, use the specialized helper that returns the other endpoint
  if (graph.type === "undirected") {
    return getUndirectedNeighbors(graph, nodeIndex);
  }
  const adjacencyList = graph.adjacency.get(nodeIndex);
  if (adjacencyList === undefined) {
    return [];
  }
  const result = [];
  for (const edgeIndex of adjacencyList) {
    const edge = graph.edges.get(edgeIndex);
    if (edge !== undefined) {
      result.push(edge.target);
    }
  }
  return result;
});
/**
 * Gets neighbors of a node in a specific direction for bidirectional traversal.
 *
 * **Example** (Traversing directed neighbors)
 *
 * ```ts
 * 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")
 * })
 *
 * const nodeA = 0
 * const nodeB = 1
 *
 * // Get outgoing neighbors (nodes that nodeA points to)
 * const outgoing = Graph.neighborsDirected(graph, nodeA, "outgoing")
 *
 * // Get incoming neighbors (nodes that point to nodeB)
 * const incoming = Graph.neighborsDirected(graph, nodeB, "incoming")
 * ```
 *
 * @category queries
 * @since 3.18.0
 */
export const neighborsDirected = /*#__PURE__*/dual(3, (graph, nodeIndex, direction) => {
  const adjacencyMap = direction === "incoming" ? graph.reverseAdjacency : graph.adjacency;
  const adjacencyList = adjacencyMap.get(nodeIndex);
  if (adjacencyList === undefined) {
    return [];
  }
  const result = [];
  for (const edgeIndex of adjacencyList) {
    const edge = graph.edges.get(edgeIndex);
    if (edge !== undefined) {
      // For incoming direction, we want the source node instead of target
      const neighborNode = direction === "incoming" ? edge.source : edge.target;
      result.push(neighborNode);
    }
  }
  return result;
});
/**
 * Exports a graph to GraphViz DOT format for visualization.
 *
 * **Example** (Exporting GraphViz DOT)
 *
 * ```ts
 * import { Graph } from "effect"
 *
 * const graph = Graph.mutate(Graph.directed<string, number>(), (mutable) => {
 *   const nodeA = Graph.addNode(mutable, "Node A")
 *   const nodeB = Graph.addNode(mutable, "Node B")
 *   const nodeC = Graph.addNode(mutable, "Node C")
 *   Graph.addEdge(mutable, nodeA, nodeB, 1)
 *   Graph.addEdge(mutable, nodeB, nodeC, 2)
 *   Graph.addEdge(mutable, nodeC, nodeA, 3)
 * })
 *
 * const dot = Graph.toGraphViz(graph)
 * console.log(dot)
 * // digraph G {
 * //   "0" [label="Node A"];
 * //   "1" [label="Node B"];
 * //   "2" [label="Node C"];
 * //   "0" -> "1" [label="1"];
 * //   "1" -> "2" [label="2"];
 * //   "2" -> "0" [label="3"];
 * // }
 * ```
 *
 * @category converting
 * @since 3.18.0
 */
export const toGraphViz = /*#__PURE__*/dual(args => isGraph(args[0]), (graph, options) => {
  const {
    edgeLabel = data => String(data),
    graphName = "G",
    nodeLabel = data => String(data)
  } = options ?? {};
  const isDirected = graph.type === "directed";
  const graphType = isDirected ? "digraph" : "graph";
  const edgeOperator = isDirected ? "->" : "--";
  const lines = [];
  lines.push(`${graphType} ${graphName} {`);
  // Add nodes
  for (const [nodeIndex, nodeData] of graph.nodes) {
    const label = nodeLabel(nodeData).replace(/"/g, "\\\"");
    lines.push(`  "${nodeIndex}" [label="${label}"];`);
  }
  // Add edges
  for (const [, edgeData] of graph.edges) {
    const label = edgeLabel(edgeData.data).replace(/"/g, "\\\"");
    lines.push(`  "${edgeData.source}" ${edgeOperator} "${edgeData.target}" [label="${label}"];`);
  }
  lines.push("}");
  return lines.join("\n");
});
/**
 * Escapes special characters in labels for Mermaid syntax compatibility.
 */
const escapeMermaidLabel = label => {
  // Escape special characters for Mermaid using HTML entity codes
  // According to: https://mermaid.js.org/syntax/flowchart.html#special-characters-that-break-syntax
  return label.replace(/#/g, "#35;").replace(/"/g, "#quot;").replace(/</g, "#lt;").replace(/>/g, "#gt;").replace(/&/g, "#amp;").replace(/\[/g, "#91;").replace(/\]/g, "#93;").replace(/\{/g, "#123;").replace(/\}/g, "#125;").replace(/\(/g, "#40;").replace(/\)/g, "#41;").replace(/\|/g, "#124;").replace(/\\/g, "#92;").replace(/\n/g, "<br/>");
};
/**
 * Formats a Mermaid node with the specified shape and label.
 */
const formatMermaidNode = (nodeId, label, shape) => {
  switch (shape) {
    case "rectangle":
      return `${nodeId}["${label}"]`;
    case "rounded":
      return `${nodeId}("${label}")`;
    case "circle":
      return `${nodeId}(("${label}"))`;
    case "diamond":
      return `${nodeId}{"${label}"}`;
    case "hexagon":
      return `${nodeId}{{"${label}"}}`;
    case "stadium":
      return `${nodeId}(["${label}"])`;
    case "subroutine":
      return `${nodeId}[["${label}"]]`;
    case "cylindrical":
      return `${nodeId}[("${label}")]`;
    default:
      return `${nodeId}["${label}"]`;
    // Default rectangle
  }
};
/**
 * 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.
 *
 * **Example** (Exporting a directed Mermaid diagram)
 *
 * ```ts
 * import { Graph } from "effect"
 *
 * // Basic directed graph export
 * const graph = Graph.directed<string, number>((mutable) => {
 *   const app = Graph.addNode(mutable, "App")
 *   const db = Graph.addNode(mutable, "Database")
 *   const cache = Graph.addNode(mutable, "Cache")
 *   Graph.addEdge(mutable, app, db, 1)
 *   Graph.addEdge(mutable, app, cache, 2)
 * })
 *
 * const mermaid = Graph.toMermaid(graph)
 * console.log(mermaid)
 * // flowchart TD
 * //   0["App"]
 * //   1["Database"]
 * //   2["Cache"]
 * //   0 -->|"1"| 1
 * //   0 -->|"2"| 2
 * ```
 *
 * **Example** (Exporting an undirected Mermaid diagram)
 *
 * ```ts
 * import { Graph } from "effect"
 *
 * // Undirected graph with custom labels and direction
 * const socialGraph = Graph.undirected<{ name: string }, string>((mutable) => {
 *   const alice = Graph.addNode(mutable, { name: "Alice" })
 *   const bob = Graph.addNode(mutable, { name: "Bob" })
 *   const charlie = Graph.addNode(mutable, { name: "Charlie" })
 *   Graph.addEdge(mutable, alice, bob, "friends")
 *   Graph.addEdge(mutable, bob, charlie, "colleagues")
 * })
 *
 * const mermaid = Graph.toMermaid(socialGraph, {
 *   nodeLabel: (person) => person.name,
 *   edgeLabel: (relationship) => relationship,
 *   direction: "LR"
 * })
 * console.log(mermaid)
 * // graph LR
 * //   0["Alice"]
 * //   1["Bob"]
 * //   2["Charlie"]
 * //   0 ---|"friends"| 1
 * //   1 ---|"colleagues"| 2
 * ```
 *
 * **Example** (Customizing Mermaid node shapes)
 *
 * ```ts
 * import { Graph } from "effect"
 *
 * // Advanced styling with node shapes for flowchart
 * const workflow = Graph.directed<{ type: string; name: string }, string>(
 *   (mutable) => {
 *     const start = Graph.addNode(mutable, { type: "start", name: "Begin" })
 *     const process = Graph.addNode(mutable, {
 *       type: "process",
 *       name: "Process Data"
 *     })
 *     const decision = Graph.addNode(mutable, {
 *       type: "decision",
 *       name: "Valid?"
 *     })
 *     const end = Graph.addNode(mutable, { type: "end", name: "Complete" })
 *     Graph.addEdge(mutable, start, process, "")
 *     Graph.addEdge(mutable, process, decision, "")
 *     Graph.addEdge(mutable, decision, end, "yes")
 *   }
 * )
 *
 * const mermaid = Graph.toMermaid(workflow, {
 *   nodeLabel: (node) => node.name,
 *   nodeShape: (node) => {
 *     switch (node.type) {
 *       case "start":
 *         return "stadium"
 *       case "process":
 *         return "rectangle"
 *       case "decision":
 *         return "diamond"
 *       case "end":
 *         return "stadium"
 *       default:
 *         return "rectangle"
 *     }
 *   }
 * })
 * console.log(mermaid)
 * // flowchart TD
 * //   0(["Begin"])
 * //   1["Process Data"]
 * //   2{"Valid?"}
 * //   3(["Complete"])
 * //   0 --> 1
 * //   1 --> 2
 * //   2 --> 3
 * ```
 *
 * **Example** (Visualizing dependency graphs)
 *
 * ```ts
 * import { Graph } from "effect"
 *
 * // Real-world example: Software dependency graph
 * interface Dependency {
 *   name: string
 *   version: string
 *   type: "library" | "framework" | "tool"
 * }
 *
 * const dependencyGraph = Graph.directed<Dependency, string>((mutable) => {
 *   const app = Graph.addNode(mutable, {
 *     name: "MyApp",
 *     version: "1.0.0",
 *     type: "library"
 *   })
 *   const react = Graph.addNode(mutable, {
 *     name: "React",
 *     version: "18.0.0",
 *     type: "framework"
 *   })
 *   const lodash = Graph.addNode(mutable, {
 *     name: "Lodash",
 *     version: "4.17.0",
 *     type: "library"
 *   })
 *   const webpack = Graph.addNode(mutable, {
 *     name: "Webpack",
 *     version: "5.0.0",
 *     type: "tool"
 *   })
 *
 *   Graph.addEdge(mutable, app, react, "depends on")
 *   Graph.addEdge(mutable, app, lodash, "depends on")
 *   Graph.addEdge(mutable, app, webpack, "builds with")
 * })
 *
 * const dependencyDiagram = Graph.toMermaid(dependencyGraph, {
 *   nodeLabel: (dep) => `${dep.name}\\nv${dep.version}`,
 *   edgeLabel: (edge) => edge,
 *   nodeShape: (dep) =>
 *     dep.type === "framework" ?
 *       "hexagon" :
 *       dep.type === "tool"
 *       ? "diamond"
 *       : "rectangle",
 *   direction: "TB"
 * })
 *
 * console.log(dependencyDiagram)
 * // flowchart TB
 * //   0["MyApp\nv1.0.0"]
 * //   1{{"React\nv18.0.0"}}
 * //   2["Lodash\nv4.17.0"]
 * //   3{"Webpack\nv5.0.0"}
 * //   0 -->|"depends on"| 1
 * //   0 -->|"depends on"| 2
 * //   0 -->|"builds with"| 3
 * ```
 *
 * @category converting
 * @since 3.18.0
 */
export const toMermaid = /*#__PURE__*/dual(args => isGraph(args[0]), (graph, options) => {
  // Extract and validate options with defaults
  const {
    diagramType,
    direction = "TD",
    edgeLabel = data => String(data),
    nodeLabel = data => String(data),
    nodeShape = () => "rectangle"
  } = options ?? {};
  // Auto-detect diagram type if not specified
  const finalDiagramType = diagramType ?? (graph.type === "directed" ? "flowchart" : "graph");
  // Generate diagram header
  const lines = [];
  lines.push(`${finalDiagramType} ${direction}`);
  // Add nodes
  for (const [nodeIndex, nodeData] of graph.nodes) {
    const nodeId = String(nodeIndex);
    const label = escapeMermaidLabel(nodeLabel(nodeData));
    const shape = nodeShape(nodeData);
    const formattedNode = formatMermaidNode(nodeId, label, shape);
    lines.push(`  ${formattedNode}`);
  }
  // Add edges
  const edgeOperator = finalDiagramType === "flowchart" ? "-->" : "---";
  for (const [, edgeData] of graph.edges) {
    const sourceId = String(edgeData.source);
    const targetId = String(edgeData.target);
    const label = escapeMermaidLabel(edgeLabel(edgeData.data));
    if (label) {
      lines.push(`  ${sourceId} ${edgeOperator}|"${label}"| ${targetId}`);
    } else {
      lines.push(`  ${sourceId} ${edgeOperator} ${targetId}`);
    }
  }
  return lines.join("\n");
});
// =============================================================================
// Graph Structure Analysis Algorithms
// =============================================================================
/**
 * 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 go to the immediate parent creates a cycle.
 *
 * **Example** (Checking cycles)
 *
 * ```ts
 * import { Graph } from "effect"
 *
 * // Acyclic directed graph (DAG)
 * const dag = Graph.directed<string, string>((mutable) => {
 *   const a = Graph.addNode(mutable, "A")
 *   const b = Graph.addNode(mutable, "B")
 *   const c = Graph.addNode(mutable, "C")
 *   Graph.addEdge(mutable, a, b, "A->B")
 *   Graph.addEdge(mutable, b, c, "B->C")
 * })
 * console.log(Graph.isAcyclic(dag)) // true
 *
 * // Cyclic directed graph
 * const cyclic = Graph.directed<string, string>((mutable) => {
 *   const a = Graph.addNode(mutable, "A")
 *   const b = Graph.addNode(mutable, "B")
 *   Graph.addEdge(mutable, a, b, "A->B")
 *   Graph.addEdge(mutable, b, a, "B->A") // Creates cycle
 * })
 * console.log(Graph.isAcyclic(cyclic)) // false
 * ```
 *
 * @category algorithms
 * @since 3.18.0
 */
export const isAcyclic = graph => {
  // Use existing cycle flag if available
  if (Option.isSome(graph.acyclic)) {
    return graph.acyclic.value;
  }
  // Stack-safe DFS cycle detection using iterative approach
  const visited = new Set();
  const recursionStack = new Set();
  // Get all nodes to handle disconnected components
  for (const startNode of graph.nodes.keys()) {
    if (visited.has(startNode)) {
      continue; // Already processed this component
    }
    // Iterative DFS with explicit stack
    const stack = [[startNode, [], 0, true]];
    while (stack.length > 0) {
      const [node, neighbors, neighborIndex, isFirstVisit] = stack[stack.length - 1];
      // First visit to this node
      if (isFirstVisit) {
        if (recursionStack.has(node)) {
          // Back edge found - cycle detected
          graph.acyclic = Option.some(false);
          return false;
        }
        if (visited.has(node)) {
          stack.pop();
          continue;
        }
        visited.add(node);
        recursionStack.add(node);
        // Get neighbors for this node
        const nodeNeighbors = Array.from(neighborsDirected(graph, node, "outgoing"));
        stack[stack.length - 1] = [node, nodeNeighbors, 0, false];
        continue;
      }
      // Process next neighbor
      if (neighborIndex < neighbors.length) {
        const neighbor = neighbors[neighborIndex];
        stack[stack.length - 1] = [node, neighbors, neighborIndex + 1, false];
        if (recursionStack.has(neighbor)) {
          // Back edge found - cycle detected
          graph.acyclic = Option.some(false);
          return false;
        }
        if (!visited.has(neighbor)) {
          stack.push([neighbor, [], 0, true]);
        }
      } else {
        // Done with this node - backtrack
        recursionStack.delete(node);
        stack.pop();
      }
    }
  }
  // Cache the result
  graph.acyclic = Option.some(true);
  return true;
};
/**
 * 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.
 *
 * **Example** (Checking bipartite graphs)
 *
 * ```ts
 * import { Graph } from "effect"
 *
 * // Bipartite graph (alternating coloring possible)
 * const bipartite = Graph.undirected<string, string>((mutable) => {
 *   const a = Graph.addNode(mutable, "A")
 *   const b = Graph.addNode(mutable, "B")
 *   const c = Graph.addNode(mutable, "C")
 *   const d = Graph.addNode(mutable, "D")
 *   Graph.addEdge(mutable, a, b, "edge") // Set 1: {A, C}, Set 2: {B, D}
 *   Graph.addEdge(mutable, b, c, "edge")
 *   Graph.addEdge(mutable, c, d, "edge")
 * })
 * console.log(Graph.isBipartite(bipartite)) // true
 *
 * // Non-bipartite graph (odd cycle)
 * const triangle = Graph.undirected<string, string>((mutable) => {
 *   const a = Graph.addNode(mutable, "A")
 *   const b = Graph.addNode(mutable, "B")
 *   const c = Graph.addNode(mutable, "C")
 *   Graph.addEdge(mutable, a, b, "edge")
 *   Graph.addEdge(mutable, b, c, "edge")
 *   Graph.addEdge(mutable, c, a, "edge") // Triangle (3-cycle)
 * })
 * console.log(Graph.isBipartite(triangle)) // false
 * ```
 *
 * @category algorithms
 * @since 3.18.0
 */
export const isBipartite = graph => {
  const coloring = new Map();
  const discovered = new Set();
  let isBipartiteGraph = true;
  // Get all nodes to handle disconnected components
  for (const startNode of graph.nodes.keys()) {
    if (!discovered.has(startNode)) {
      // Start BFS coloring from this component
      const queue = [startNode];
      coloring.set(startNode, 0); // Color start node with 0
      discovered.add(startNode);
      while (queue.length > 0 && isBipartiteGraph) {
        const current = queue.shift();
        const currentColor = coloring.get(current);
        const neighborColor = currentColor === 0 ? 1 : 0;
        // Get all neighbors for undirected graph
        const nodeNeighbors = getUndirectedNeighbors(graph, current);
        for (const neighbor of nodeNeighbors) {
          if (!discovered.has(neighbor)) {
            // Color unvisited neighbor with opposite color
            coloring.set(neighbor, neighborColor);
            discovered.add(neighbor);
            queue.push(neighbor);
          } else {
            // Check if neighbor has the same color (conflict)
            if (coloring.get(neighbor) === currentColor) {
              isBipartiteGraph = false;
              break;
            }
          }
        }
      }
      // Early exit if not bipartite
      if (!isBipartiteGraph) {
        break;
      }
    }
  }
  return isBipartiteGraph;
};
/**
 * Get neighbors for undirected graphs by checking both adjacency and reverse adjacency.
 * For undirected graphs, we need to find the other endpoint of each edge incident to the node.
 */
const getUndirectedNeighbors = (graph, nodeIndex) => {
  const neighbors = new Set();
  // Check edges where this node is the source
  const adjacencyList = graph.adjacency.get(nodeIndex);
  if (adjacencyList !== undefined) {
    for (const edgeIndex of adjacencyList) {
      const edge = graph.edges.get(edgeIndex);
      if (edge !== undefined) {
        // For undirected graphs, the neighbor is the other endpoint
        const otherNode = edge.source === nodeIndex ? edge.target : edge.source;
        neighbors.add(otherNode);
      }
    }
  }
  return Array.from(neighbors);
};
/**
 * Finds connected components in an undirected graph.
 * Each component is represented as an array of node indices.
 *
 * **Example** (Finding connected components)
 *
 * ```ts
 * import { Graph } from "effect"
 *
 * const graph = Graph.undirected<string, string>((mutable) => {
 *   const a = Graph.addNode(mutable, "A")
 *   const b = Graph.addNode(mutable, "B")
 *   const c = Graph.addNode(mutable, "C")
 *   const d = Graph.addNode(mutable, "D")
 *   Graph.addEdge(mutable, a, b, "edge") // Component 1: A-B
 *   Graph.addEdge(mutable, c, d, "edge") // Component 2: C-D
 * })
 *
 * const components = Graph.connectedComponents(graph)
 * console.log(components) // [[0, 1], [2, 3]]
 * ```
 *
 * @category algorithms
 * @since 3.18.0
 */
export const connectedComponents = graph => {
  const visited = new Set();
  const components = [];
  for (const startNode of graph.nodes.keys()) {
    if (!visited.has(startNode)) {
      // DFS to find all nodes in this component
      const component = [];
      const stack = [startNode];
      while (stack.length > 0) {
        const current = stack.pop();
        if (!visited.has(current)) {
          visited.add(current);
          component.push(current);
          // Add all unvisited neighbors to stack
          const nodeNeighbors = getUndirectedNeighbors(graph, current);
          for (const neighbor of nodeNeighbors) {
            if (!visited.has(neighbor)) {
              stack.push(neighbor);
            }
          }
        }
      }
      components.push(component);
    }
  }
  return components;
};
/**
 * Finds strongly connected components in a directed graph using Kosaraju's algorithm.
 * Each SCC is represented as an array of node indices.
 *
 * **Example** (Finding strongly connected components)
 *
 * ```ts
 * import { Graph } from "effect"
 *
 * const graph = Graph.directed<string, string>((mutable) => {
 *   const a = Graph.addNode(mutable, "A")
 *   const b = Graph.addNode(mutable, "B")
 *   const c = Graph.addNode(mutable, "C")
 *   Graph.addEdge(mutable, a, b, "A->B")
 *   Graph.addEdge(mutable, b, c, "B->C")
 *   Graph.addEdge(mutable, c, a, "C->A") // Creates SCC: A-B-C
 * })
 *
 * const sccs = Graph.stronglyConnectedComponents(graph)
 * console.log(sccs) // [[0, 1, 2]]
 * ```
 *
 * @category algorithms
 * @since 3.18.0
 */
export const stronglyConnectedComponents = graph => {
  const visited = new Set();
  const finishOrder = [];
  for (const startNode of graph.nodes.keys()) {
    if (visited.has(startNode)) {
      continue;
    }
    const stack = [[startNode, [], 0, true]];
    while (stack.length > 0) {
      const [node, nodeNeighbors, neighborIndex, isFirstVisit] = stack[stack.length - 1];
      if (isFirstVisit) {
        if (visited.has(node)) {
          stack.pop();
          continue;
        }
        visited.add(node);
        const nodeNeighborsList = neighbors(graph, node);
        stack[stack.length - 1] = [node, nodeNeighborsList, 0, false];
        continue;
      }
      // Process next neighbor
      if (neighborIndex < nodeNeighbors.length) {
        const neighbor = nodeNeighbors[neighborIndex];
        stack[stack.length - 1] = [node, nodeNeighbors, neighborIndex + 1, false];
        if (!visited.has(neighbor)) {
          stack.push([neighbor, [], 0, true]);
        }
      } else {
        // Done with this node - add to finish order (post-order)
        finishOrder.push(node);
        stack.pop();
      }
    }
  }
  // Step 2: Stack-safe DFS on transpose graph in reverse finish order
  visited.clear();
  const sccs = [];
  for (let i = finishOrder.length - 1; i >= 0; i--) {
    const startNode = finishOrder[i];
    if (visited.has(startNode)) {
      continue;
    }
    const scc = [];
    const stack = [startNode];
    while (stack.length > 0) {
      const node = stack.pop();
      if (visited.has(node)) {
        continue;
      }
      visited.add(node);
      scc.push(node);
      // Use reverse adjacency (transpose graph)
      const reverseAdjacency = graph.reverseAdjacency.get(node);
      if (reverseAdjacency !== undefined) {
        for (const edgeIndex of reverseAdjacency) {
          const edge = graph.edges.get(edgeIndex);
          if (edge !== undefined) {
            const predecessor = edge.source;
            if (!visited.has(predecessor)) {
              stack.push(predecessor);
            }
          }
        }
      }
    }
    sccs.push(scc);
  }
  return sccs;
};
/**
 * Finds the shortest path from the configured source node to the target node
 * using Dijkstra's algorithm.
 *
 * **Details**
 *
 * Edge costs must be non-negative. Returns `Option.none()` when the target is
 * not reachable, and throws a `GraphError` when either endpoint is missing or a
 * negative edge cost is encountered.
 *
 * **Example** (Finding shortest paths with Dijkstra)
 *
 * ```ts
 * import { Graph } from "effect"
 *
 * const graph = Graph.directed<string, number>((mutable) => {
 *   const a = Graph.addNode(mutable, "A")
 *   const b = Graph.addNode(mutable, "B")
 *   const c = Graph.addNode(mutable, "C")
 *   Graph.addEdge(mutable, a, b, 5)
 *   Graph.addEdge(mutable, a, c, 10)
 *   Graph.addEdge(mutable, b, c, 2)
 * })
 *
 * const result = Graph.dijkstra(graph, {
 *   source: 0,
 *   target: 2,
 *   cost: (edgeData) => edgeData
 * })
 *
 * if (result._tag === "Some") {
 *   console.log(result.value.path) // [0, 1, 2] - shortest path A->B->C
 *   console.log(result.value.distance) // 7 - total distance
 * }
 * ```
 *
 * @category algorithms
 * @since 3.18.0
 */
export const dijkstra = /*#__PURE__*/dual(2, (graph, config) => {
  // Validate that source and target nodes exist
  if (!graph.nodes.has(config.source)) {
    throw missingNode(config.source);
  }
  if (!graph.nodes.has(config.target)) {
    throw missingNode(config.target);
  }
  // Early return if source equals target
  if (config.source === config.target) {
    return Option.some({
      path: [config.source],
      distance: 0,
      costs: []
    });
  }
  // Distance tracking and priority queue simulation
  const distances = new Map();
  const previous = new Map();
  const visited = new Set();
  // Initialize distances
  // Iterate directly over node keys
  for (const node of graph.nodes.keys()) {
    distances.set(node, node === config.source ? 0 : Infinity);
    previous.set(node, null);
  }
  // Simple priority queue using array (can be optimized with proper heap)
  const priorityQueue = [{
    node: config.source,
    distance: 0
  }];
  while (priorityQueue.length > 0) {
    // Find minimum distance node (priority queue extract-min)
    let minIndex = 0;
    for (let i = 1; i < priorityQueue.length; i++) {
      if (priorityQueue[i].distance < priorityQueue[minIndex].distance) {
        minIndex = i;
      }
    }
    const current = priorityQueue.splice(minIndex, 1)[0];
    const currentNode = current.node;
    // Skip if already visited (can happen with duplicate entries)
    if (visited.has(currentNode)) {
      continue;
    }
    visited.add(currentNode);
    // Early termination if we reached the target
    if (currentNode === config.target) {
      break;
    }
    // Get current distance
    const currentDistance = distances.get(currentNode);
    // Examine all outgoing edges
    const adjacencyList = graph.adjacency.get(currentNode);
    if (adjacencyList !== undefined) {
      for (const edgeIndex of adjacencyList) {
        const edge = graph.edges.get(edgeIndex);
        if (edge !== undefined) {
          const neighbor = edge.target;
          const cost = config.cost(edge.data);
          // Validate non-negative weights
          if (cost < 0) {
            throw new GraphError({
              message: "Dijkstra's algorithm requires non-negative edge weights"
            });
          }
          const newDistance = currentDistance + cost;
          const neighborDistance = distances.get(neighbor);
          // Relaxation step
          if (newDistance < neighborDistance) {
            distances.set(neighbor, newDistance);
            previous.set(neighbor, {
              node: currentNode,
              edgeData: edge.data
            });
            // Add to priority queue if not visited
            if (!visited.has(neighbor)) {
              priorityQueue.push({
                node: neighbor,
                distance: newDistance
              });
            }
          }
        }
      }
    }
  }
  // Check if target is reachable
  const distance = distances.get(config.target);
  if (distance === Infinity) {
    return Option.none(); // No path exists
  }
  // Reconstruct path
  const path = [];
  const costs = [];
  let currentNode = config.target;
  while (currentNode !== null) {
    path.unshift(currentNode);
    const prev = previous.get(currentNode);
    if (prev !== null) {
      costs.unshift(prev.edgeData);
      currentNode = prev.node;
    } else {
      currentNode = null;
    }
  }
  return Option.some({
    path,
    distance,
    costs
  });
});
/**
 * 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, but
 * a `GraphError` is thrown if any negative cycle is detected.
 *
 * **Example** (Finding all-pairs shortest paths)
 *
 * ```ts
 * import { Graph } from "effect"
 *
 * const graph = Graph.directed<string, number>((mutable) => {
 *   const a = Graph.addNode(mutable, "A")
 *   const b = Graph.addNode(mutable, "B")
 *   const c = Graph.addNode(mutable, "C")
 *   Graph.addEdge(mutable, a, b, 3)
 *   Graph.addEdge(mutable, b, c, 2)
 *   Graph.addEdge(mutable, a, c, 7)
 * })
 *
 * const result = Graph.floydWarshall(graph, (edgeData) => edgeData)
 * const distanceAToC = result.distances.get(0)?.get(2) // 5 (A->B->C)
 * const pathAToC = result.paths.get(0)?.get(2) // [0, 1, 2]
 * ```
 *
 * @category algorithms
 * @since 3.18.0
 */
export const floydWarshall = /*#__PURE__*/dual(2, (graph, cost) => {
  // Get all nodes for Floyd-Warshall algorithm (needs array for nested iteration)
  const allNodes = Array.from(graph.nodes.keys());
  // Initialize distance matrix
  const distances = new Map();
  const next = new Map();
  const edgeMatrix = new Map();
  // Initialize with infinity for all pairs
  for (const i of allNodes) {
    distances.set(i, new Map());
    next.set(i, new Map());
    edgeMatrix.set(i, new Map());
    for (const j of allNodes) {
      distances.get(i).set(j, i === j ? 0 : Infinity);
      next.get(i).set(j, null);
      edgeMatrix.get(i).set(j, null);
    }
  }
  // Set edge weights
  for (const [, edgeData] of graph.edges) {
    const weight = cost(edgeData.data);
    const i = edgeData.source;
    const j = edgeData.target;
    // Use minimum weight if multiple edges exist
    const currentWeight = distances.get(i).get(j);
    if (weight < currentWeight) {
      distances.get(i).set(j, weight);
      next.get(i).set(j, j);
      edgeMatrix.get(i).set(j, edgeData.data);
    }
  }
  // Floyd-Warshall main loop
  for (const k of allNodes) {
    for (const i of allNodes) {
      for (const j of allNodes) {
        const distIK = distances.get(i).get(k);
        const distKJ = distances.get(k).get(j);
        const distIJ = distances.get(i).get(j);
        if (distIK !== Infinity && distKJ !== Infinity && distIK + distKJ < distIJ) {
          distances.get(i).set(j, distIK + distKJ);
          next.get(i).set(j, next.get(i).get(k));
        }
      }
    }
  }
  // Check for negative cycles
  for (const i of allNodes) {
    if (distances.get(i).get(i) < 0) {
      throw new GraphError({
        message: `Negative cycle detected involving node ${i}`
      });
    }
  }
  // Build result paths and edge weights
  const paths = new Map();
  const costs = new Map();
  for (const i of allNodes) {
    paths.set(i, new Map());
    costs.set(i, new Map());
    for (const j of allNodes) {
      if (i === j) {
        paths.get(i).set(j, [i]);
        costs.get(i).set(j, []);
      } else if (distances.get(i).get(j) === Infinity) {
        paths.get(i).set(j, null);
        costs.get(i).set(j, []);
      } else {
        // Reconstruct path iteratively
        const path = [];
        const weights = [];
        let current = i;
        path.push(current);
        while (current !== j) {
          const nextNode = next.get(current).get(j);
          if (nextNode === null) break;
          const edgeData = edgeMatrix.get(current).get(nextNode);
          if (edgeData !== null) {
            weights.push(edgeData);
          }
          current = nextNode;
          path.push(current);
        }
        paths.get(i).set(j, path);
        costs.get(i).set(j, weights);
      }
    }
  }
  return {
    distances,
    paths,
    costs
  };
});
/**
 * 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 the heuristic
 * should be admissible to preserve shortest-path guarantees. Returns
 * `Option.none()` when the target is not reachable, and throws a `GraphError`
 * when either endpoint is missing or a negative edge cost is encountered.
 *
 * **Example** (Finding shortest paths with A-star)
 *
 * ```ts
 * import { Graph } from "effect"
 *
 * const graph = Graph.directed<{ x: number; y: number }, number>((mutable) => {
 *   const a = Graph.addNode(mutable, { x: 0, y: 0 })
 *   const b = Graph.addNode(mutable, { x: 1, y: 0 })
 *   const c = Graph.addNode(mutable, { x: 2, y: 0 })
 *   Graph.addEdge(mutable, a, b, 1)
 *   Graph.addEdge(mutable, b, c, 1)
 * })
 *
 * // Manhattan distance heuristic
 * const heuristic = (
 *   nodeData: { x: number; y: number },
 *   targetData: { x: number; y: number }
 * ) => Math.abs(nodeData.x - targetData.x) + Math.abs(nodeData.y - targetData.y)
 *
 * const result = Graph.astar(graph, {
 *   source: 0,
 *   target: 2,
 *   cost: (edgeData) => edgeData,
 *   heuristic
 * })
 *
 * if (result._tag === "Some") {
 *   console.log(result.value.path) // [0, 1, 2] - shortest path
 *   console.log(result.value.distance) // 2 - total distance
 * }
 * ```
 *
 * @category algorithms
 * @since 3.18.0
 */
export const astar = /*#__PURE__*/dual(2, (graph, config) => {
  // Validate that source and target nodes exist
  if (!graph.nodes.has(config.source)) {
    throw missingNode(config.source);
  }
  if (!graph.nodes.has(config.target)) {
    throw missingNode(config.target);
  }
  // Early return if source equals target
  if (config.source === config.target) {
    return Option.some({
      path: [config.source],
      distance: 0,
      costs: []
    });
  }
  // Get target node data for heuristic calculations
  const targetNodeData = getNode(graph, config.target);
  if (Option.isNone(targetNodeData)) {
    throw new GraphError({
      message: `Missing node data for target node ${config.target}`
    });
  }
  // Distance tracking (g-score) and f-score (g + h)
  const gScore = new Map();
  const fScore = new Map();
  const previous = new Map();
  const visited = new Set();
  // Initialize scores
  // Iterate directly over node keys
  for (const node of graph.nodes.keys()) {
    gScore.set(node, node === config.source ? 0 : Infinity);
    fScore.set(node, Infinity);
    previous.set(node, null);
  }
  // Calculate initial f-score for source
  const sourceNodeData = getNode(graph, config.source);
  if (Option.isSome(sourceNodeData)) {
    const h = config.heuristic(sourceNodeData.value, targetNodeData.value);
    fScore.set(config.source, h);
  }
  // Priority queue using f-score (total estimated cost)
  const openSet = [{
    node: config.source,
    fScore: fScore.get(config.source)
  }];
  while (openSet.length > 0) {
    // Find node with lowest f-score
    let minIndex = 0;
    for (let i = 1; i < openSet.length; i++) {
      if (openSet[i].fScore < openSet[minIndex].fScore) {
        minIndex = i;
      }
    }
    const current = openSet.splice(minIndex, 1)[0];
    const currentNode = current.node;
    // Skip if already visited
    if (visited.has(currentNode)) {
      continue;
    }
    visited.add(currentNode);
    // Early termination if we reached the target
    if (currentNode === config.target) {
      break;
    }
    // Get current g-score
    const currentGScore = gScore.get(currentNode);
    // Examine all outgoing edges
    const adjacencyList = graph.adjacency.get(currentNode);
    if (adjacencyList !== undefined) {
      for (const edgeIndex of adjacencyList) {
        const edge = graph.edges.get(edgeIndex);
        if (edge !== undefined) {
          const neighbor = edge.target;
          const weight = config.cost(edge.data);
          // Validate non-negative weights
          if (weight < 0) {
            throw new GraphError({
              message: "A* algorithm requires non-negative edge weights"
            });
          }
          const tentativeGScore = currentGScore + weight;
          const neighborGScore = gScore.get(neighbor);
          // If this path to neighbor is better than any previous one
          if (tentativeGScore < neighborGScore) {
            // Update g-score and previous
            gScore.set(neighbor, tentativeGScore);
            previous.set(neighbor, {
              node: currentNode,
              edgeData: edge.data
            });
            // Calculate f-score using heuristic
            const neighborNodeData = getNode(graph, neighbor);
            if (Option.isSome(neighborNodeData)) {
              const h = config.heuristic(neighborNodeData.value, targetNodeData.value);
              const f = tentativeGScore + h;
              fScore.set(neighbor, f);
              // Add to open set if not visited
              if (!visited.has(neighbor)) {
                openSet.push({
                  node: neighbor,
                  fScore: f
                });
              }
            }
          }
        }
      }
    }
  }
  // Check if target is reachable
  const distance = gScore.get(config.target);
  if (distance === Infinity) {
    return Option.none(); // No path exists
  }
  // Reconstruct path
  const path = [];
  const costs = [];
  let currentNode = config.target;
  while (currentNode !== null) {
    path.unshift(currentNode);
    const prev = previous.get(currentNode) ?? null;
    if (prev !== null) {
      costs.unshift(prev.edgeData);
      currentNode = prev.node;
    } else {
      currentNode = null;
    }
  }
  return Option.some({
    path,
    distance,
    costs
  });
});
/**
 * Finds the shortest path from the configured source node to the target node
 * using the Bellman-Ford algorithm.
 *
 * **Details**
 *
 * Negative edge weights are allowed. 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.
 *
 * **Example** (Finding shortest paths with Bellman-Ford)
 *
 * ```ts
 * import { Graph } from "effect"
 *
 * const graph = Graph.directed<string, number>((mutable) => {
 *   const a = Graph.addNode(mutable, "A")
 *   const b = Graph.addNode(mutable, "B")
 *   const c = Graph.addNode(mutable, "C")
 *   Graph.addEdge(mutable, a, b, -1) // Negative weight allowed
 *   Graph.addEdge(mutable, b, c, 3)
 *   Graph.addEdge(mutable, a, c, 5)
 * })
 *
 * const result = Graph.bellmanFord(graph, {
 *   source: 0,
 *   target: 2,
 *   cost: (edgeData) => edgeData
 * })
 *
 * if (result._tag === "Some") {
 *   console.log(result.value.path) // [0, 1, 2] - shortest path A->B->C
 *   console.log(result.value.distance) // 2 - total distance
 * }
 * ```
 *
 * @category algorithms
 * @since 3.18.0
 */
export const bellmanFord = /*#__PURE__*/dual(2, (graph, config) => {
  // Validate that source and target nodes exist
  if (!graph.nodes.has(config.source)) {
    throw missingNode(config.source);
  }
  if (!graph.nodes.has(config.target)) {
    throw missingNode(config.target);
  }
  // Early return if source equals target
  if (config.source === config.target) {
    return Option.some({
      path: [config.source],
      distance: 0,
      costs: []
    });
  }
  // Initialize distances and predecessors
  const distances = new Map();
  const previous = new Map();
  // Iterate directly over node keys
  for (const node of graph.nodes.keys()) {
    distances.set(node, node === config.source ? 0 : Infinity);
    previous.set(node, null);
  }
  // Collect all edges for relaxation
  const edges = [];
  for (const [, edgeData] of graph.edges) {
    const weight = config.cost(edgeData.data);
    edges.push({
      source: edgeData.source,
      target: edgeData.target,
      weight,
      edgeData: edgeData.data
    });
  }
  // Relax edges up to V-1 times
  const nodeCount = graph.nodes.size;
  for (let i = 0; i < nodeCount - 1; i++) {
    let hasUpdate = false;
    for (const edge of edges) {
      const sourceDistance = distances.get(edge.source);
      const targetDistance = distances.get(edge.target);
      // Relaxation step
      if (sourceDistance !== Infinity && sourceDistance + edge.weight < targetDistance) {
        distances.set(edge.target, sourceDistance + edge.weight);
        previous.set(edge.target, {
          node: edge.source,
          edgeData: edge.edgeData
        });
        hasUpdate = true;
      }
    }
    // Early termination if no updates
    if (!hasUpdate) {
      break;
    }
  }
  // Check for negative cycles
  for (const edge of edges) {
    const sourceDistance = distances.get(edge.source);
    const targetDistance = distances.get(edge.target);
    if (sourceDistance !== Infinity && sourceDistance + edge.weight < targetDistance) {
      // Negative cycle detected - check if it affects the path to target
      const affectedNodes = new Set();
      const queue = [edge.target];
      while (queue.length > 0) {
        const node = queue.shift();
        if (affectedNodes.has(node)) continue;
        affectedNodes.add(node);
        // Add all nodes reachable from this node
        const adjacencyList = graph.adjacency.get(node);
        if (adjacencyList !== undefined) {
          for (const edgeIndex of adjacencyList) {
            const edge = graph.edges.get(edgeIndex);
            if (edge !== undefined) {
              queue.push(edge.target);
            }
          }
        }
      }
      // If target is affected by a negative cycle, no shortest path exists.
      if (affectedNodes.has(config.target)) {
        return Option.none();
      }
    }
  }
  // Check if target is reachable
  const distance = distances.get(config.target);
  if (distance === Infinity) {
    return Option.none(); // No path exists
  }
  // Reconstruct path
  const path = [];
  const costs = [];
  let currentNode = config.target;
  while (currentNode !== null) {
    path.unshift(currentNode);
    const prev = previous.get(currentNode);
    if (prev !== null) {
      costs.unshift(prev.edgeData);
      currentNode = prev.node;
    } else {
      currentNode = null;
    }
  }
  return Option.some({
    path,
    distance,
    costs
  });
});
/**
 * 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`.
 *
 * **Example** (Working with node walkers)
 *
 * ```ts
 * 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"]]
 * ```
 *
 * @category models
 * @since 3.18.0
 */
export class Walker {
  // @ts-ignore
  [Symbol.iterator];
  /**
   * Visits each element and maps it to a value using the provided function.
   *
   * **Details**
   *
   * Takes a function that receives the index and data,
   * and returns an iterable of the mapped values. Skips elements that
   * no longer exist in the graph.
   *
   * **Example** (Visiting walker elements)
   *
   * ```ts
   * 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)
   * })
   *
   * const dfs = Graph.dfs(graph, { start: [0] })
   *
   * // Map to just the node data
   * const values = Array.from(dfs.visit((index, data) => data))
   * console.log(values) // ["A", "B"]
   *
   * // Map to custom objects
   * const custom = Array.from(
   *   dfs.visit((index, data) => ({ id: index, name: data }))
   * )
   * console.log(custom) // [{ id: 0, name: "A" }, { id: 1, name: "B" }]
   * ```
   *
   * @since 4.0.0
   */
  visit;
  constructor(
  /**
   * Visits each element and maps it to a value using the provided function.
   *
   * Takes a function that receives the index and data,
   * and returns an iterable of the mapped values. Skips elements that
   * no longer exist in the graph.
   *
   * **Example** (Visiting walker elements)
   *
   * ```ts
   * 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)
   * })
   *
   * const dfs = Graph.dfs(graph, { start: [0] })
   *
   * // Map to just the node data
   * const values = Array.from(dfs.visit((index, data) => data))
   * console.log(values) // ["A", "B"]
   *
   * // Map to custom objects
   * const custom = Array.from(
   *   dfs.visit((index, data) => ({ id: index, name: data }))
   * )
   * console.log(custom) // [{ id: 0, name: "A" }, { id: 1, name: "B" }]
   * ```
   *
   * @category iterators
   * @since 4.0.0
   */
  visit) {
    this.visit = visit;
    this[Symbol.iterator] = visit((index, data) => [index, data])[Symbol.iterator];
  }
}
/**
 * Returns an iterator over the indices in the walker.
 *
 * **Example** (Iterating walker indices)
 *
 * ```ts
 * 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)
 * })
 *
 * const dfs = Graph.dfs(graph, { start: [0] })
 * const indices = Array.from(Graph.indices(dfs))
 * console.log(indices) // [0, 1]
 * ```
 *
 * @category iterators
 * @since 3.18.0
 */
export const indices = walker => walker.visit((index, _) => index);
/**
 * Returns an iterator over the values (data) in the walker.
 *
 * **Example** (Iterating walker values)
 *
 * ```ts
 * 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)
 * })
 *
 * const dfs = Graph.dfs(graph, { start: [0] })
 * const values = Array.from(Graph.values(dfs))
 * console.log(values) // ["A", "B"]
 * ```
 *
 * @category iterators
 * @since 3.18.0
 */
export const values = walker => walker.visit((_, data) => data);
/**
 * Returns an iterator over [index, data] entries in the walker.
 *
 * **Example** (Iterating walker entries)
 *
 * ```ts
 * 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)
 * })
 *
 * const dfs = Graph.dfs(graph, { start: [0] })
 * const entries = Array.from(Graph.entries(dfs))
 * console.log(entries) // [[0, "A"], [1, "B"]]
 * ```
 *
 * @category iterators
 * @since 3.18.0
 */
export const entries = walker => walker.visit((index, data) => [index, data]);
/**
 * 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. Throws a `GraphError`
 * if any configured start node does not exist.
 *
 * **Example** (Traversing depth-first)
 *
 * ```ts
 * import { Graph } from "effect"
 *
 * const graph = Graph.directed<string, number>((mutable) => {
 *   const a = Graph.addNode(mutable, "A")
 *   const b = Graph.addNode(mutable, "B")
 *   const c = Graph.addNode(mutable, "C")
 *   Graph.addEdge(mutable, a, b, 1)
 *   Graph.addEdge(mutable, b, c, 1)
 * })
 *
 * // Start from a specific node
 * const dfs1 = Graph.dfs(graph, { start: [0] })
 * for (const nodeIndex of Graph.indices(dfs1)) {
 *   console.log(nodeIndex) // Traverses in DFS order: 0, 1, 2
 * }
 *
 * // Empty iterator (no starting nodes)
 * const dfs2 = Graph.dfs(graph)
 * // Can be used programmatically
 * ```
 *
 * @category iterators
 * @since 3.18.0
 */
export const dfs = /*#__PURE__*/dual(args => isGraph(args[0]), (graph, config = {}) => {
  const start = config.start ?? [];
  const direction = config.direction ?? "outgoing";
  // Validate that all start nodes exist
  for (const nodeIndex of start) {
    if (!hasNode(graph, nodeIndex)) {
      throw missingNode(nodeIndex);
    }
  }
  return new Walker(f => ({
    [Symbol.iterator]: () => {
      const stack = [...start];
      const discovered = new Set();
      const nextMapped = () => {
        while (stack.length > 0) {
          const current = stack.pop();
          if (discovered.has(current)) {
            continue;
          }
          discovered.add(current);
          const nodeDataOption = getNode(graph, current);
          if (Option.isNone(nodeDataOption)) {
            continue;
          }
          const neighbors = neighborsDirected(graph, current, direction);
          for (let i = neighbors.length - 1; i >= 0; i--) {
            const neighbor = neighbors[i];
            if (!discovered.has(neighbor)) {
              stack.push(neighbor);
            }
          }
          return {
            done: false,
            value: f(current, nodeDataOption.value)
          };
        }
        return {
          done: true,
          value: undefined
        };
      };
      return {
        next: nextMapped
      };
    }
  }));
});
/**
 * 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. Throws a `GraphError`
 * if any configured start node does not exist.
 *
 * **Example** (Traversing breadth-first)
 *
 * ```ts
 * import { Graph } from "effect"
 *
 * const graph = Graph.directed<string, number>((mutable) => {
 *   const a = Graph.addNode(mutable, "A")
 *   const b = Graph.addNode(mutable, "B")
 *   const c = Graph.addNode(mutable, "C")
 *   Graph.addEdge(mutable, a, b, 1)
 *   Graph.addEdge(mutable, b, c, 1)
 * })
 *
 * // Start from a specific node
 * const bfs1 = Graph.bfs(graph, { start: [0] })
 * for (const nodeIndex of Graph.indices(bfs1)) {
 *   console.log(nodeIndex) // Traverses in BFS order: 0, 1, 2
 * }
 *
 * // Empty iterator (no starting nodes)
 * const bfs2 = Graph.bfs(graph)
 * // Can be used programmatically
 * ```
 *
 * @category iterators
 * @since 3.18.0
 */
export const bfs = /*#__PURE__*/dual(args => isGraph(args[0]), (graph, config = {}) => {
  const start = config.start ?? [];
  const direction = config.direction ?? "outgoing";
  // Validate that all start nodes exist
  for (const nodeIndex of start) {
    if (!hasNode(graph, nodeIndex)) {
      throw missingNode(nodeIndex);
    }
  }
  return new Walker(f => ({
    [Symbol.iterator]: () => {
      const queue = [...start];
      const discovered = new Set();
      const nextMapped = () => {
        while (queue.length > 0) {
          const current = queue.shift();
          if (!discovered.has(current)) {
            discovered.add(current);
            const neighbors = neighborsDirected(graph, current, direction);
            for (const neighbor of neighbors) {
              if (!discovered.has(neighbor)) {
                queue.push(neighbor);
              }
            }
            const nodeData = getNode(graph, current);
            if (Option.isSome(nodeData)) {
              return {
                done: false,
                value: f(current, nodeData.value)
              };
            }
            return nextMapped();
          }
        }
        return {
          done: true,
          value: undefined
        };
      };
      return {
        next: nextMapped
      };
    }
  }));
});
/**
 * 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.
 *
 * **Example** (Sorting topologically)
 *
 * ```ts
 * import { Graph } from "effect"
 *
 * const graph = Graph.directed<string, number>((mutable) => {
 *   const a = Graph.addNode(mutable, "A")
 *   const b = Graph.addNode(mutable, "B")
 *   const c = Graph.addNode(mutable, "C")
 *   Graph.addEdge(mutable, a, b, 1)
 *   Graph.addEdge(mutable, b, c, 1)
 * })
 *
 * // Standard topological sort
 * const topo1 = Graph.topo(graph)
 * for (const nodeIndex of Graph.indices(topo1)) {
 *   console.log(nodeIndex) // 0, 1, 2 (topological order)
 * }
 *
 * // With initial nodes
 * const topo2 = Graph.topo(graph, { initials: [0] })
 *
 * // Check before sorting a cyclic graph
 * const cyclicGraph = Graph.directed<string, number>((mutable) => {
 *   const a = Graph.addNode(mutable, "A")
 *   const b = Graph.addNode(mutable, "B")
 *   Graph.addEdge(mutable, a, b, 1)
 *   Graph.addEdge(mutable, b, a, 2) // Creates cycle
 * })
 *
 * if (!Graph.isAcyclic(cyclicGraph)) {
 *   console.log("cyclic graph") // cyclic graph
 * }
 * ```
 *
 * @category iterators
 * @since 3.18.0
 */
export const topo = /*#__PURE__*/dual(args => isGraph(args[0]), (graph, config = {}) => {
  // Check if graph is acyclic first
  if (!isAcyclic(graph)) {
    throw new GraphError({
      message: "Cannot perform topological sort on cyclic graph"
    });
  }
  const initials = config.initials ?? [];
  // Validate that all initial nodes exist
  for (const nodeIndex of initials) {
    if (!hasNode(graph, nodeIndex)) {
      throw missingNode(nodeIndex);
    }
  }
  return new Walker(f => ({
    [Symbol.iterator]: () => {
      const inDegree = new Map();
      const remaining = new Set();
      const queue = [...initials];
      // Initialize in-degree counts
      for (const [nodeIndex] of graph.nodes) {
        inDegree.set(nodeIndex, 0);
        remaining.add(nodeIndex);
      }
      // Calculate in-degrees
      for (const [, edgeData] of graph.edges) {
        const currentInDegree = inDegree.get(edgeData.target) || 0;
        inDegree.set(edgeData.target, currentInDegree + 1);
      }
      // Add nodes with zero in-degree to queue if no initials provided
      if (initials.length === 0) {
        for (const [nodeIndex, degree] of inDegree) {
          if (degree === 0) {
            queue.push(nodeIndex);
          }
        }
      }
      const nextMapped = () => {
        while (queue.length > 0) {
          const current = queue.shift();
          if (remaining.has(current)) {
            remaining.delete(current);
            // Process outgoing edges, reducing in-degree of targets
            const neighbors = neighborsDirected(graph, current, "outgoing");
            for (const neighbor of neighbors) {
              if (remaining.has(neighbor)) {
                const currentInDegree = inDegree.get(neighbor) || 0;
                const newInDegree = currentInDegree - 1;
                inDegree.set(neighbor, newInDegree);
                // If in-degree becomes 0, add to queue
                if (newInDegree === 0) {
                  queue.push(neighbor);
                }
              }
            }
            const nodeData = getNode(graph, current);
            if (Option.isSome(nodeData)) {
              return {
                done: false,
                value: f(current, nodeData.value)
              };
            }
            return nextMapped();
          }
        }
        return {
          done: true,
          value: undefined
        };
      };
      return {
        next: nextMapped
      };
    }
  }));
});
/**
 * 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.
 *
 * **Example** (Traversing in postorder)
 *
 * ```ts
 * import { Graph } from "effect"
 *
 * const graph = Graph.directed<string, number>((mutable) => {
 *   const root = Graph.addNode(mutable, "root")
 *   const child1 = Graph.addNode(mutable, "child1")
 *   const child2 = Graph.addNode(mutable, "child2")
 *   Graph.addEdge(mutable, root, child1, 1)
 *   Graph.addEdge(mutable, root, child2, 1)
 * })
 *
 * // Postorder: children before parents
 * const postOrder = Graph.dfsPostOrder(graph, { start: [0] })
 * for (const node of postOrder) {
 *   console.log(node) // 1, 2, 0
 * }
 * ```
 *
 * @category iterators
 * @since 3.18.0
 */
export const dfsPostOrder = /*#__PURE__*/dual(args => isGraph(args[0]), (graph, config = {}) => {
  const start = config.start ?? [];
  const direction = config.direction ?? "outgoing";
  // Validate that all start nodes exist
  for (const nodeIndex of start) {
    if (!hasNode(graph, nodeIndex)) {
      throw missingNode(nodeIndex);
    }
  }
  return new Walker(f => ({
    [Symbol.iterator]: () => {
      const stack = [];
      const discovered = new Set();
      const finished = new Set();
      // Initialize stack with start nodes
      for (let i = start.length - 1; i >= 0; i--) {
        stack.push({
          node: start[i],
          visitedChildren: false
        });
      }
      const nextMapped = () => {
        while (stack.length > 0) {
          const current = stack[stack.length - 1];
          if (!discovered.has(current.node)) {
            discovered.add(current.node);
            current.visitedChildren = false;
          }
          if (!current.visitedChildren) {
            current.visitedChildren = true;
            const neighbors = neighborsDirected(graph, current.node, direction);
            for (let i = neighbors.length - 1; i >= 0; i--) {
              const neighbor = neighbors[i];
              if (!discovered.has(neighbor) && !finished.has(neighbor)) {
                stack.push({
                  node: neighbor,
                  visitedChildren: false
                });
              }
            }
          } else {
            const nodeToEmit = stack.pop().node;
            if (!finished.has(nodeToEmit)) {
              finished.add(nodeToEmit);
              const nodeData = getNode(graph, nodeToEmit);
              if (Option.isSome(nodeData)) {
                return {
                  done: false,
                  value: f(nodeToEmit, nodeData.value)
                };
              }
              return nextMapped();
            }
          }
        }
        return {
          done: true,
          value: undefined
        };
      };
      return {
        next: nextMapped
      };
    }
  }));
});
/**
 * 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.
 *
 * **Example** (Iterating all nodes)
 *
 * ```ts
 * import { Graph } from "effect"
 *
 * const graph = Graph.directed<string, number>((mutable) => {
 *   const a = Graph.addNode(mutable, "A")
 *   const b = Graph.addNode(mutable, "B")
 *   const c = Graph.addNode(mutable, "C")
 *   Graph.addEdge(mutable, a, b, 1)
 * })
 *
 * const indices = Array.from(Graph.indices(Graph.nodes(graph)))
 * console.log(indices) // [0, 1, 2]
 * ```
 *
 * @category iterators
 * @since 3.18.0
 */
export const nodes = graph => new Walker(f => ({
  [Symbol.iterator]() {
    const nodeMap = graph.nodes;
    const iterator = nodeMap.entries();
    return {
      next() {
        const result = iterator.next();
        if (result.done) {
          return {
            done: true,
            value: undefined
          };
        }
        const [nodeIndex, nodeData] = result.value;
        return {
          done: false,
          value: f(nodeIndex, nodeData)
        };
      }
    };
  }
}));
/**
 * 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.
 *
 * **Example** (Iterating all edges)
 *
 * ```ts
 * import { Graph } from "effect"
 *
 * const graph = Graph.directed<string, number>((mutable) => {
 *   const a = Graph.addNode(mutable, "A")
 *   const b = Graph.addNode(mutable, "B")
 *   const c = Graph.addNode(mutable, "C")
 *   Graph.addEdge(mutable, a, b, 1)
 *   Graph.addEdge(mutable, b, c, 2)
 * })
 *
 * const indices = Array.from(Graph.indices(Graph.edges(graph)))
 * console.log(indices) // [0, 1]
 * ```
 *
 * @category iterators
 * @since 3.18.0
 */
export const edges = graph => new Walker(f => ({
  [Symbol.iterator]() {
    const edgeMap = graph.edges;
    const iterator = edgeMap.entries();
    return {
      next() {
        const result = iterator.next();
        if (result.done) {
          return {
            done: true,
            value: undefined
          };
        }
        const [edgeIndex, edgeData] = result.value;
        return {
          done: false,
          value: f(edgeIndex, edgeData)
        };
      }
    };
  }
}));
/**
 * 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.
 *
 * **Example** (Iterating external nodes)
 *
 * ```ts
 * import { Graph } from "effect"
 *
 * const graph = Graph.directed<string, number>((mutable) => {
 *   const source = Graph.addNode(mutable, "source") // 0 - no incoming
 *   const middle = Graph.addNode(mutable, "middle") // 1 - has both
 *   const sink = Graph.addNode(mutable, "sink") // 2 - no outgoing
 *   const isolated = Graph.addNode(mutable, "isolated") // 3 - no edges
 *
 *   Graph.addEdge(mutable, source, middle, 1)
 *   Graph.addEdge(mutable, middle, sink, 2)
 * })
 *
 * // Nodes with no outgoing edges (sinks + isolated)
 * const sinks = Array.from(
 *   Graph.indices(Graph.externals(graph, { direction: "outgoing" }))
 * )
 * console.log(sinks) // [2, 3]
 *
 * // Nodes with no incoming edges (sources + isolated)
 * const sources = Array.from(
 *   Graph.indices(Graph.externals(graph, { direction: "incoming" }))
 * )
 * console.log(sources) // [0, 3]
 * ```
 *
 * @category iterators
 * @since 3.18.0
 */
export const externals = /*#__PURE__*/dual(args => isGraph(args[0]), (graph, config = {}) => {
  const direction = config.direction ?? "outgoing";
  return new Walker(f => ({
    [Symbol.iterator]: () => {
      const nodeMap = graph.nodes;
      const adjacencyMap = direction === "incoming" ? graph.reverseAdjacency : graph.adjacency;
      const nodeIterator = nodeMap.entries();
      const nextMapped = () => {
        let current = nodeIterator.next();
        while (!current.done) {
          const [nodeIndex, nodeData] = current.value;
          const adjacencyList = adjacencyMap.get(nodeIndex);
          // Node is external if it has no edges in the specified direction
          if (adjacencyList === undefined || adjacencyList.length === 0) {
            return {
              done: false,
              value: f(nodeIndex, nodeData)
            };
          }
          current = nodeIterator.next();
        }
        return {
          done: true,
          value: undefined
        };
      };
      return {
        next: nextMapped
      };
    }
  }));
});
//# sourceMappingURL=Graph.js.map