Hyperlinkv0.8.0-beta.28

← Graph

Graph.dfsPostOrderconsteffect/Graph.ts:4614
(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 postorder traversal iterator from the configured start nodes.

Details

Nodes are emitted after their reachable descendants have been processed. If no start nodes are supplied, the iterator is empty. The direction option chooses whether to follow outgoing or incoming edges.

Example (Traversing in postorder)

import { Graph } from "effect"

const graph = Graph.directed<string, number>((mutable) => {
  const root = Graph.addNode(mutable, "root")
  const child1 = Graph.addNode(mutable, "child1")
  const child2 = Graph.addNode(mutable, "child2")
  Graph.addEdge(mutable, root, child1, 1)
  Graph.addEdge(mutable, root, child2, 1)
})

// Postorder: children before parents
const postOrder = Graph.dfsPostOrder(graph, { start: [0] })
for (const node of postOrder) {
  console.log(node) // 1, 2, 0
}
iterators
Source effect/Graph.ts:461474 lines
export const dfsPostOrder: {
  (
    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: Array<{ node: NodeIndex; visitedChildren: boolean }> = []
      const discovered = new Set<NodeIndex>()
      const finished = new Set<NodeIndex>()

      // Initialize stack with start nodes
      for (let i = start.length - 1; i >= 0; i--) {
        stack.push({ node: start[i], visitedChildren: false })
      }

      const nextMapped = () => {
        while (stack.length > 0) {
          const current = stack[stack.length - 1]

          if (!discovered.has(current.node)) {
            discovered.add(current.node)
            current.visitedChildren = false
          }

          if (!current.visitedChildren) {
            current.visitedChildren = true
            const neighbors = getTraversalNeighbors(graph, current.node, direction)

            for (let i = neighbors.length - 1; i >= 0; i--) {
              const neighbor = neighbors[i]
              if (!discovered.has(neighbor) && !finished.has(neighbor)) {
                stack.push({ node: neighbor, visitedChildren: false })
              }
            }
          } else {
            const nodeToEmit = stack.pop()!.node

            if (!finished.has(nodeToEmit)) {
              finished.add(nodeToEmit)

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

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

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