Spaces:
Build error
Build error
File size: 963 Bytes
c211499 |
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 |
import * as _ from 'lodash-es';
export { tarjan };
function tarjan(g) {
var index = 0;
var stack = [];
var visited = {}; // node id -> { onStack, lowlink, index }
var results = [];
function dfs(v) {
var entry = (visited[v] = {
onStack: true,
lowlink: index,
index: index++,
});
stack.push(v);
g.successors(v).forEach(function (w) {
if (!_.has(visited, w)) {
dfs(w);
entry.lowlink = Math.min(entry.lowlink, visited[w].lowlink);
} else if (visited[w].onStack) {
entry.lowlink = Math.min(entry.lowlink, visited[w].index);
}
});
if (entry.lowlink === entry.index) {
var cmpt = [];
var w;
do {
w = stack.pop();
visited[w].onStack = false;
cmpt.push(w);
} while (v !== w);
results.push(cmpt);
}
}
g.nodes().forEach(function (v) {
if (!_.has(visited, v)) {
dfs(v);
}
});
return results;
}
|