Strongly connected components of three or more modules, in the drawn graph.
(ids: readonly string[], edges: readonly MapEdgeLayout[])
| 659 | |
| 660 | /** Strongly connected components of three or more modules, in the drawn graph. */ |
| 661 | function moduleCycles(ids: readonly string[], edges: readonly MapEdgeLayout[]): string[][] { |
| 662 | const out = new Map<string, string[]>(ids.map((id) => [id, []])); |
| 663 | for (const edge of edges) out.get(edge.source)?.push(edge.target); |
| 664 | for (const list of out.values()) list.sort(); |
| 665 | |
| 666 | const index = new Map<string, number>(); |
| 667 | const low = new Map<string, number>(); |
| 668 | const onStack = new Set<string>(); |
| 669 | const stack: string[] = []; |
| 670 | const found: string[][] = []; |
| 671 | let counter = 0; |
| 672 | |
| 673 | const strongconnect = (id: string): void => { |
| 674 | index.set(id, counter); |
| 675 | low.set(id, counter); |
| 676 | counter += 1; |
| 677 | stack.push(id); |
| 678 | onStack.add(id); |
| 679 | for (const next of out.get(id) ?? []) { |
| 680 | if (!index.has(next)) { |
| 681 | strongconnect(next); |
| 682 | low.set(id, Math.min(low.get(id) ?? 0, low.get(next) ?? 0)); |
| 683 | } else if (onStack.has(next)) { |
| 684 | low.set(id, Math.min(low.get(id) ?? 0, index.get(next) ?? 0)); |
| 685 | } |
| 686 | } |
| 687 | if (low.get(id) === index.get(id)) { |
| 688 | const component: string[] = []; |
| 689 | for (;;) { |
| 690 | const popped = stack.pop(); |
| 691 | if (popped === undefined) break; |
| 692 | onStack.delete(popped); |
| 693 | component.push(popped); |
| 694 | if (popped === id) break; |
| 695 | } |
| 696 | if (component.length > 2) found.push(component.sort()); |
| 697 | } |
| 698 | }; |
| 699 | |
| 700 | for (const id of [...ids].sort()) if (!index.has(id)) strongconnect(id); |
| 701 | return found.sort((a, b) => b.length - a.length || (a[0] ?? '').localeCompare(b[0] ?? '')); |
| 702 | } |
no test coverage detected