| 1 | "use strict";
|
| 2 | Object.defineProperty(exports, "__esModule", { value: true });
|
| 3 | exports.CycleException = exports.topsort = void 0;
|
| 4 | const each = require("lodash.foreach");
|
| 5 | const size = require("lodash.size");
|
| 6 | function topsort(g) {
|
| 7 | const visited = {};
|
| 8 | const stack = {};
|
| 9 | const results = [];
|
| 10 | function visit(node) {
|
| 11 | if (node in stack) {
|
| 12 | throw new CycleException();
|
| 13 | }
|
| 14 | if (!(node in visited)) {
|
| 15 | stack[node] = true;
|
| 16 | visited[node] = true;
|
| 17 | each(g.predecessors(node), visit);
|
| 18 | delete stack[node];
|
| 19 | results.push(node);
|
| 20 | }
|
| 21 | }
|
| 22 | each(g.sinks(), visit);
|
| 23 | if (size(visited) !== g.nodeCount()) {
|
| 24 | throw new CycleException();
|
| 25 | }
|
| 26 | return results;
|
| 27 | }
|
| 28 | exports.topsort = topsort;
|
| 29 | class CycleException extends Error {
|
| 30 | }
|
| 31 | exports.CycleException = CycleException;
|
| 32 | |
| \ | No newline at end of file |