Hyperlinkv0.8.0-beta.28

← Graph

Graph.dfsconsteffect/Graph.ts:4253
(config?: SearchConfig): <N, E, T extends Kind = "directed">(
  graph: Graph<N, E, T> | MutableGraph<N, E, T>
) => NodeWalker<N>
<N, E, T extends Kind = "directed">(
  graph: Graph<N, E, T> | MutableGraph<N, E, T>,
  config?: SearchConfig
): NodeWalker<N>

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)

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
iterators
Source effect/Graph.ts:425360 lines
export const dfs: {
  (
    config?: SearchConfig
  ): <N, E, T extends Kind = "directed">(graph: Graph<N, E, T> | MutableGraph<N, E, T>) => NodeWalker<N>
  <N, E, T extends Kind = "directed">(
    graph: Graph<N, E, T> | MutableGraph<N, E, T>,
    config?: SearchConfig
  ): NodeWalker<N>
} = dual((args) => isGraph(args[0]), <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 = getNode(graph, current)
          if (Option.isNone(nodeDataOption)) {
            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.value) }
        }

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

      return { next: nextMapped }
    }
  }))
})