Function isAcyclic

packages/effect/src/Graph.ts:1889–1994

(
  graph: Graph<N, E, T> | MutableGraph<N, E, T>
)

 * @category algorithms
 */
export const isAcyclic = <N, E, T extends Kind = "directed">(
  graph: Graph<N, E, T> | MutableGraph<N, E, T>
): boolean => {
  // Use existing cycle flag if available
  if (Option.isSome(graph.isAcyclic)) {
    return graph.isAcyclic.value
  }

  if (graph.type === "undirected") {
    const visited = new Set<NodeIndex>()

    for (const startNode of graph.nodes.keys()) {
      if (visited.has(startNode)) {
        continue
      }

      visited.add(startNode)
      const stack: Array<{ node: NodeIndex; parent: NodeIndex | null }> = [{ node: startNode, parent: null }]

      while (stack.length > 0) {
        const { node, parent } = stack.pop()!
        const nodeNeighbors = getUndirectedNeighbors(graph as any, node)

        for (const neighbor of nodeNeighbors) {
          if (!visited.has(neighbor)) {
            visited.add(neighbor)
            stack.push({ node: neighbor, parent: node })
          } else if (neighbor !== parent) {
            graph.isAcyclic = Option.some(false)
            return false
          }
        }
      }
    }

    graph.isAcyclic = Option.some(true)
    return true
  }

  // Stack-safe DFS cycle detection using iterative approach
  const visited = new Set<NodeIndex>()
  const recursionStack = new Set<NodeIndex>()

  // Stack entry: [node, neighbors, neighborIndex, isFirstVisit]
  type DfsStackEntry = [NodeIndex, Array<NodeIndex>, number, boolean]

  // 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: Array<DfsStackEntry> = [[startNode, [], 0, true]]

    while (stack.length > 0) {
      const [node, neighbors, neighborIndex, isFirstVisit] = stack[stack.length - 1]