Figure out which items in a dependency graph can be handled in parallel, and which must be deferred until their dependencies are completed. Handles cyclic and acyclic graphs, but if cycles are allowed, then dependency order may not be guaranteed.
For example, given the following directed graph:
flowchart TD
A --> B
A --> C
B --> E
B --> D
C --> D
C --> G
D --> F
F --> E
it will allow you to operate in this order:
Operation will be maximally parallelized, so that each step in the graph only waits until its dependencies are completed.
If a cycle exists in the graph, then at least one node in the cycle will by necessity be operated upon before its dependencies are complete.
Cycles may be disallowed by throwing in the onCycle method
provided.
AbortSignal fires.This is not just a topological sort, and there are better libraries available that implement Kahn's Topological Sort very efficiently.
However, topological sorting is insufficient if you wish to know which items can be operated on in parallel, and Kahn's algorithm only works when the graph is guaranteed to be acyclic and all nodes are known ahead of time.
This implementation does not require that the graph be entirely loaded ahead of time, and provides a mechanism to treat cycles as a warning rather than an error, with the caveat that if cycles are allowed then topological ordering is of course not guaranteed.
While this can be used in theory to explore any infinitely large graph, note that the result set will be stored in memory.
So, if you were to use it to try to crawl all the links in Wikipedia or something, you're going to have a Bad Time if the result set gets too big.
import {
// returns Promise<Map<Node, Result>>
graphRun,
// returns Promise<Map<Node, PromiseSettledResult<Result>>>
// like Promise.allSettled
// Implies failFast:false
allSettled,
// resolves to first successful result, or rejects with AggregateError
// like Promise.any()
any,
// returns or rejects on the first visit to complete
// like Promise.race()
race,
// options provided to sync methods MUST be sychronous
// returns Map<Node, Result>
graphRunSync,
// returns Map<Node, PromiseSettledResult<Result>>
allSettledSync,
// returns first successful result, or throws AggregateError
anySync,
// returns or throws on the first visit
// this is somewhat useless, since you can just call the method
// on the first node in the options.graph list, but is included
// for symmetry reasons.
raceSync,
} from 'graph-run'
// optionally used to trigger an abort of the walk at any time
const ac = new AbortController()
// return value will be a Promise<Map<Node, Result>>
// when using allSettled, returns Promise<Map<Node, PromiseSettledResult>>
const results = await graphRun/*<Node, Result>*/({
// provide one or more node to serve as entry points.
// this MAY be the entire graph, but doesn't have to be.
// Node[]
graph: [some, nodes, known, at, the, start],
// a sync or async method for providing nodes that are
// dependents of the node being considered.
// Return [] if node has no dependencies.
// (n: Node) => Node[] | Promise<Node[]>
getDeps: async (n) => {
// if a promise is returned, then it must resolve to an
// array of nodes.
return [the, dependency, node, objects]
},
// sync or async method that will be executed on each node in the graph
// node is the data object being operated on, signal is an
// AbortSignal that will fire if the operation should halt.
// (node: Node, signal: AbortSignal, path: Node[]) => Result|Promise<Result>
visit: async (node, signal, path) => {
await doSomething(n)
},
// optional: if this method throws, then the traversal will
// of course fail when cycles are encountered. If not provided,
// then cycles are silently detected and skipped.
// first argument is the dependency that would cause a cycle
// second argument is the cycle from that node back to itself
// third is the path to the dependent that wanted to load it,
// but instead will skip it because of the cycle.
// (node: Node, cycle: Node[], path: Node[]) => void | Promise<void>
onCycle: (node, cycle, path) => {
console.error(
`warning: while evaluating ${
node
} at path ${
path.join('->')
} encountered cycle: ${
cycle.join('->')
}. Proceeding without this dependency.`
)
},
// Whether to abort the entire traversal on the first error
// if true, then this will reject with an error and trigger an abort
// on all in-progress operations.
// if false, then the rejection value will be an AggregateError of all
// failures encountered. (For consistency, an AggregateError is
// raised if failFast is false, even if only one failure is countered.)
// default: true
failFast: true
// Optional: pass along a signal that you can use externally to signal
// the graph traversal should end prematurely.
signal: ac.signal
})
// Another example, detect whether it's a directed acyclic graph:
const isDAG = (graph) => {
try {
graphRunSync({
graph: [graph],
getDeps: n => n.children ?? [],
onCycle: () => { throw 'cycle detected' },
visit: () => {}
})
return true
} catch {
return false
}
}
const g = {
children: [
{
name: 'a',
children: [{ name: 'b' }],
}
]
}
console.log(isDAG(g)) // true
// create a cycle
g.children[0].children[0].children = g.children
console.log(isDAG(g)) // false
See the typedocs for complete API details.
Node can be any value type.