* The links minus the ones that close a cycle — those whose end is still open * on the way in, found by one walk from every link's source in order, so the * walk's own order decides which way round a cycle is the forward one. The * twin of the order reading's `withoutBackEdges`, over map links.
(links: readonly WireMapLink[])
| 661 | * twin of the order reading's `withoutBackEdges`, over map links. |
| 662 | */ |
| 663 | function forwardLinks(links: readonly WireMapLink[]): WireMapLink[] { |
| 664 | const out = new Map<string, WireMapLink[]>(); |
| 665 | const nodes = new Set<string>(); |
| 666 | for (const l of links) { |
| 667 | nodes.add(l.source); |
| 668 | nodes.add(l.target); |
| 669 | const list = out.get(l.source); |
| 670 | if (list) list.push(l); |
| 671 | else out.set(l.source, [l]); |
| 672 | } |
| 673 | /** 1 = open on the way in, 2 = done with. */ |
| 674 | const state = new Map<string, number>(); |
| 675 | const closes = new Set<WireMapLink>(); |
| 676 | const visit = (root: string): void => { |
| 677 | const stack: { id: string; next: number }[] = [{ id: root, next: 0 }]; |
| 678 | state.set(root, 1); |
| 679 | while (stack.length > 0) { |
| 680 | const top = stack[stack.length - 1]!; |
| 681 | const list = out.get(top.id) ?? []; |
| 682 | if (top.next >= list.length) { |
| 683 | state.set(top.id, 2); |
| 684 | stack.pop(); |
| 685 | continue; |
| 686 | } |
| 687 | const link = list[top.next++]!; |
| 688 | const seen = state.get(link.target) ?? 0; |
| 689 | if (seen === 1) { |
| 690 | closes.add(link); |
| 691 | continue; |
| 692 | } |
| 693 | if (seen === 2) continue; |
| 694 | state.set(link.target, 1); |
| 695 | stack.push({ id: link.target, next: 0 }); |
| 696 | } |
| 697 | }; |
| 698 | for (const id of nodes) if (!state.has(id)) visit(id); |
| 699 | return links.filter((l) => !closes.has(l)); |
| 700 | } |
| 701 | |
| 702 | /** |
| 703 | * The layout of a screen's picture: each region a small column of lines — |