effect-io-ai

Package: effect
Module: Graph

Graph.dfsPostOrder

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. The radius option limits traversal by edge distance from the start nodes.

Gotchas

With a finite radius, iteration first performs a bounded breadth-first traversal to determine shortest-distance membership before emitting nodes in postorder.

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
}

Signature

declare 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>; }

Source

Since v3.18.0