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 | 10x 10x 10x 17x 1x 16x 15x 15x 15x 11x 11x 10x 8x 4x 4x | import Graph from '../Graph';
export class CycleException extends Error {}
function topsort<NodeIDType>(graph: Graph<NodeIDType>) {
var visited = new Set<NodeIDType>();
var stack = new Set<NodeIDType>();
var results: NodeIDType[] = [];
function visit(node: NodeIDType) {
if (stack.has(node)) {
throw new CycleException();
}
if (!visited.has(node)) {
stack.add(node);
visited.add(node);
graph.predecessors(node)?.forEach(visit);
stack.delete(node);
results.push(node);
}
}
graph.sinks().forEach(visit);
if (visited.size !== graph.nodeCount()) {
throw new CycleException();
}
return results;
}
export default topsort;
|