Press n or j to go to the next uncovered block, b, p or k for the previous block.
| 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 | 9x 1x 1x 1x 1x 1x 1x 1x 1x 1x 1x 1x 1x 1x 1x 1x 1x 1x 1x 1x 9x 9x 9x 9x 9x 9x 9x 9x 9x 9x 9x 9x 2x 2x 5x 5x 5x 5x 5x 5x 5x 9x 9x 9x 9x 5x 5x 5x 5x 5x | import {
uniqueNodes,
groupByComponents,
getStartNodes,
makeOutgoingEdges,
makeIncomingEdges,
} from './helpers.js'
import { validateEdges, validateArgs, validateDag } from './validators.js'
export interface TopologicalOrder<T> {
sources: T[];
prev: Map<any, any[]>;
next: Map<any, any[]>;
graphs: {
nodes: T[];
sources: T[];
}[];
}
export function toposortExtra<T> (opts: { edges: T[][]; throwOnCycle?: boolean; nodes?: T[] }): TopologicalOrder<T> {
validateArgs(opts)
const nodes = opts.nodes || uniqueNodes(opts.edges)
const edges = opts.edges
validateEdges(nodes, edges)
const prev = new Map([...makeIncomingEdges(edges)].map(([node, neighborsSet]) => [node, [...neighborsSet]]))
const next = new Map([...makeOutgoingEdges(edges)].map(([node, neighborsSet]) => [node, [...neighborsSet]]))
const sources = getStartNodes(edges)
if (opts.throwOnCycle) {
validateDag({ edges, nodes, outgoing: next })
}
const topoOrder: TopologicalOrder<T> = {
sources,
prev,
next,
graphs: groupByComponents({ edges })
.map(graphNodesSet => {
return {
nodes: [...graphNodesSet],
sources: sources.filter(node => graphNodesSet.has(node))
}
})
}
return topoOrder
}
|