Hyperlinkv0.8.0-beta.28

← Graph

Graph.bfsconsteffect/Graph.ts:4351
(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 breadth-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 breadth-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 bfs1 = Graph.bfs(graph, { start: [0] })
for (const nodeIndex of Graph.indices(bfs1)) {
  console.log(nodeIndex) // Traverses in BFS order: 0, 1, 2
}

// Empty iterator (no starting nodes)
const bfs2 = Graph.bfs(graph)
// Can be used programmatically
iterators
Source effect/Graph.ts:435156 lines
export const bfs: {
  (
    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 queue = [...start]
      const discovered = new Set<NodeIndex>()

      const nextMapped = () => {
        while (queue.length > 0) {
          const current = queue.shift()!

          if (!discovered.has(current)) {
            discovered.add(current)

            const neighbors = getTraversalNeighbors(graph, current, direction)
            for (const neighbor of neighbors) {
              if (!discovered.has(neighbor)) {
                queue.push(neighbor)
              }
            }

            const nodeData = getNode(graph, current)
            if (Option.isSome(nodeData)) {
              return { done: false, value: f(current, nodeData.value) }
            }
            return nextMapped()
          }
        }

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

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