MCPcopy Create free account
hub / github.com/colbymchenry/codegraph / withoutBackEdges

Function withoutBackEdges

ui/src/lib/program-model.ts:285–317  ·  view source on GitHub ↗

* 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[])

Source from the content-addressed store, hash-verified

283 * is the forward one.
284 */
285function 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

Callers 1

rowsFunction · 0.85

Calls 5

pushMethod · 0.80
hasMethod · 0.80
getMethod · 0.65
setMethod · 0.45
addMethod · 0.45

Tested by

no test coverage detected