* The edges minus the ones that close a cycle — those whose end is still open * on the way in, found by one walk from the anchor (then from anything it * does not reach), so the reading's own order decides which way round a cycle * is the forward one.
(anchor: string, nodes: ReadonlySet<string>, edges: readonly OrderEdge[])
| 283 | * is the forward one. |
| 284 | */ |
| 285 | function withoutBackEdges(anchor: string, nodes: ReadonlySet<string>, edges: readonly OrderEdge[]): OrderEdge[] { |
| 286 | const out = new Map<string, OrderEdge[]>(); |
| 287 | for (const e of edges) { |
| 288 | const list = out.get(e.from); |
| 289 | if (list) list.push(e); |
| 290 | else out.set(e.from, [e]); |
| 291 | } |
| 292 | /** 1 = open on the way in, 2 = done with. */ |
| 293 | const state = new Map<string, 1 | 2>(); |
| 294 | const back = new Set<OrderEdge>(); |
| 295 | for (const root of [anchor, ...nodes]) { |
| 296 | if (state.has(root)) continue; |
| 297 | state.set(root, 1); |
| 298 | const stack: Array<{ id: string; next: number }> = [{ id: root, next: 0 }]; |
| 299 | while (stack.length > 0) { |
| 300 | const top = stack[stack.length - 1]!; |
| 301 | const list = out.get(top.id) ?? []; |
| 302 | if (top.next >= list.length) { |
| 303 | state.set(top.id, 2); |
| 304 | stack.pop(); |
| 305 | continue; |
| 306 | } |
| 307 | const edge = list[top.next++]!; |
| 308 | const seen = state.get(edge.to); |
| 309 | if (seen === 1) back.add(edge); |
| 310 | else if (seen === undefined) { |
| 311 | state.set(edge.to, 1); |
| 312 | stack.push({ id: edge.to, next: 0 }); |
| 313 | } |
| 314 | } |
| 315 | } |
| 316 | return edges.filter((e) => !back.has(e)); |
| 317 | } |
| 318 | |
| 319 | /* ----------------------------------------------------------------- build -- */ |
| 320 |