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.acyclic)) {
    return graph.acyclic.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.acyclic = Option.some(false)
            return false
          }
        }
      }
    }

    graph.acyclic = 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]

      // 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 = getDirectedNeighbors(
          graph as Graph<N, E, "directed"> | MutableGraph<N, E, "directed">,
          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
}