Function dfs

packages/effect/src/Graph.ts:3256–3307

(
  graph: Graph<N, E, T> | MutableGraph<N, E, T>,
  config: SearchConfig = {}
)

 * @category iterators
 */
export const dfs = <N, E, T extends Kind = "directed">(
  graph: Graph<N, E, T> | MutableGraph<N, E, T>,
  config: SearchConfig = {}
): NodeWalker<N> => {
  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<NodeIndex>()

      const nextMapped = () => {
        while (stack.length > 0) {
          const current = stack.pop()!

          if (discovered.has(current)) {
            continue
          }

          discovered.add(current)

          const nodeDataOption = graph.nodes.get(current)
          if (nodeDataOption === undefined) {
            continue
          }

          const neighbors = getTraversalNeighbors(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) }
        }

        return { done: true, value: undefined } as const
      }

      return { next: nextMapped }
    }
  }))
}

/**
 * Creates a new BFS iterator with optional configuration.