* Graph-connectivity relevance via Random-Walk-with-Restart (personalized * PageRank) from the query's matched SEED nodes over the call/reference graph. * * This is the ranking signal text search (FTS/bm25) CANNOT provide, and it's * codegraph's home turf: relevance by STRUCTURE, not wor
(
nodeIds: string[],
edges: Edge[],
seedIds: Set<string>,
)
| 4387 | * it's a few hundred nodes × ~25 iterations — negligible cost. |
| 4388 | */ |
| 4389 | private computeGraphRelevance( |
| 4390 | nodeIds: string[], |
| 4391 | edges: Edge[], |
| 4392 | seedIds: Set<string>, |
| 4393 | ): Map<string, number> { |
| 4394 | const out = new Map<string, number>(); |
| 4395 | const n = nodeIds.length; |
| 4396 | if (n === 0) return out; |
| 4397 | const idx = new Map<string, number>(); |
| 4398 | for (let i = 0; i < n; i++) idx.set(nodeIds[i]!, i); |
| 4399 | |
| 4400 | const RANK_EDGES = new Set<string>([ |
| 4401 | 'calls', 'references', 'extends', 'implements', 'overrides', |
| 4402 | 'instantiates', 'returns', 'type_of', 'imports', 'navigates', |
| 4403 | ]); |
| 4404 | const adj: number[][] = Array.from({ length: n }, () => []); |
| 4405 | for (const e of edges) { |
| 4406 | if (!RANK_EDGES.has(e.kind)) continue; |
| 4407 | const i = idx.get(e.source); |
| 4408 | const j = idx.get(e.target); |
| 4409 | if (i === undefined || j === undefined || i === j) continue; |
| 4410 | adj[i]!.push(j); |
| 4411 | adj[j]!.push(i); // undirected — reachable either direction |
| 4412 | } |
| 4413 | |
| 4414 | // Restart vector: uniform over seeds present in the candidate set. (Falls |
| 4415 | // back to uniform-over-all if no seed landed in the set, so we never return |
| 4416 | // all-zero.) |
| 4417 | const r = new Array<number>(n).fill(0); |
| 4418 | let rsum = 0; |
| 4419 | for (const id of seedIds) { |
| 4420 | const i = idx.get(id); |
| 4421 | if (i !== undefined) { r[i] = 1; rsum += 1; } |
| 4422 | } |
| 4423 | if (rsum === 0) { for (let i = 0; i < n; i++) r[i] = 1; rsum = n; } |
| 4424 | for (let i = 0; i < n; i++) r[i]! /= rsum; |
| 4425 | |
| 4426 | const alpha = 0.25; |
| 4427 | let s = r.slice(); |
| 4428 | for (let iter = 0; iter < 25; iter++) { |
| 4429 | const next = new Array<number>(n).fill(0); |
| 4430 | for (let i = 0; i < n; i++) { |
| 4431 | const si = s[i]!; |
| 4432 | if (si === 0) continue; |
| 4433 | const d = adj[i]!.length; |
| 4434 | if (d === 0) { next[i]! += si; continue; } // dangling: keep its mass |
| 4435 | const share = si / d; |
| 4436 | for (const j of adj[i]!) next[j]! += share; |
| 4437 | } |
| 4438 | for (let i = 0; i < n; i++) s[i] = (1 - alpha) * next[i]! + alpha * r[i]!; |
| 4439 | } |
| 4440 | for (let i = 0; i < n; i++) out.set(nodeIds[i]!, s[i]!); |
| 4441 | return out; |
| 4442 | } |
| 4443 | |
| 4444 | /** |
| 4445 | * Handle codegraph_explore — deep exploration in a single call |