effect-io-ai

Package: effect
Module: Graph

Graph.topo

Creates a new topological sort iterator with optional configuration.

Details

The iterator uses Kahn’s algorithm to lazily produce nodes in topological order. Throws an error if the graph contains cycles.

Example (Sorting topologically)

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)
})

// Standard topological sort
const topo1 = Graph.topo(graph)
for (const nodeIndex of Graph.indices(topo1)) {
  console.log(nodeIndex) // 0, 1, 2 (topological order)
}

// With initial nodes
const topo2 = Graph.topo(graph, { initials: [0] })

// Check before sorting a cyclic graph
const cyclicGraph = Graph.directed<string, number>((mutable) => {
  const a = Graph.addNode(mutable, "A")
  const b = Graph.addNode(mutable, "B")
  Graph.addEdge(mutable, a, b, 1)
  Graph.addEdge(mutable, b, a, 2) // Creates cycle
})

if (!Graph.isAcyclic(cyclicGraph)) {
  console.log("cyclic graph") // cyclic graph
}

Signature

declare const topo: { (config?: TopoConfig): <N, E>(graph: Graph<N, E, "directed"> | MutableGraph<N, E, "directed">) => NodeWalker<N>; <N, E>(graph: Graph<N, E, "directed"> | MutableGraph<N, E, "directed">, config?: TopoConfig): NodeWalker<N>; }

Source

Since v3.18.0