Function isAcyclic

packages/effect/src/Graph.ts:3510–3631

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

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

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

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

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

      while (stack.length > 0) {
        const { node, incoming } = stack.pop()!
        const adjacencyList = impl.adjacency.get(node)
        if (adjacencyList === undefined) {
          continue
        }

        for (const edgeIndex of adjacencyList) {
          if (edgeIndex === incoming) {
            continue
          }
          const edge = impl.edges.get(edgeIndex)
          if (edge === undefined) {
            continue
          }
          const neighbor = getTraversableNeighbor(graph, node, edge)
          if (!visited.has(neighbor)) {
            visited.add(neighbor)
            stack.push({ node: neighbor, incoming: edgeIndex })
          } else {
            impl.acyclic = Option.some(false)
            return false
          }
        }
      }
    }

    impl.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]