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 | 80x 80x 80x 344x 80x 80x 344x 344x 80x 344x 86x 6x 80x 344x 344x 344x 344x 344x 277x 277x 277x 277x 277x 277x 258x 80x | import type { DirectedGraph } from './graph';
export function assignLayers(
graph: DirectedGraph,
feedbackEdges?: Set<string>
): Map<string, number> {
const ranks = new Map<string, number>();
const nodes = graph.getNodes();
for (const node of nodes) {
ranks.set(node.id, 0);
}
// Calculate in-degree ignoring feedback edges
const inDegree = new Map<string, number>();
for (const node of nodes) {
const validInEdges = graph.inEdges(node.id).filter((e) => !feedbackEdges?.has(e.id));
inDegree.set(node.id, validInEdges.length);
}
const queue: string[] = nodes
.filter((n) => inDegree.get(n.id)! === 0)
.map((n) => n.id)
.sort((a, b) => a.localeCompare(b));
while (queue.length > 0) {
queue.sort((a, b) => a.localeCompare(b));
const currId = queue.shift()!;
const currRank = ranks.get(currId)!;
const outEdges = graph.outEdges(currId).filter((e) => !feedbackEdges?.has(e.id));
for (const edge of outEdges) {
const targetId = edge.target;
const nextRank = Math.max(ranks.get(targetId)!, currRank + 1);
ranks.set(targetId, nextRank);
const remainingIn = inDegree.get(targetId)! - 1;
inDegree.set(targetId, remainingIn);
if (remainingIn === 0) {
queue.push(targetId);
}
}
}
return ranks;
}
|