* 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>,
)
| 4341 | * it's a few hundred nodes × ~25 iterations — negligible cost. |
| 4342 | */ |
| 4343 | private computeGraphRelevance( |
| 4344 | nodeIds: string[], |
| 4345 | edges: Edge[], |
| 4346 | seedIds: Set<string>, |
| 4347 | ): Map<string, number> { |
| 4348 | const out = new Map<string, number>(); |
| 4349 | const n = nodeIds.length; |
| 4350 | if (n === 0) return out; |
| 4351 | const idx = new Map<string, number>(); |
| 4352 | for (let i = 0; i < n; i++) idx.set(nodeIds[i]!, i); |
| 4353 | |
| 4354 | const RANK_EDGES = new Set<string>([ |
| 4355 | 'calls', 'references', 'extends', 'implements', 'overrides', |
| 4356 | 'instantiates', 'returns', 'type_of', 'imports', 'navigates', |
| 4357 | ]); |
| 4358 | const adj: number[][] = Array.from({ length: n }, () => []); |
| 4359 | for (const e of edges) { |
| 4360 | if (!RANK_EDGES.has(e.kind)) continue; |
| 4361 | const i = idx.get(e.source); |
| 4362 | const j = idx.get(e.target); |
| 4363 | if (i === undefined || j === undefined || i === j) continue; |
| 4364 | adj[i]!.push(j); |
| 4365 | adj[j]!.push(i); // undirected — reachable either direction |
| 4366 | } |
| 4367 | |
| 4368 | // Restart vector: uniform over seeds present in the candidate set. (Falls |
| 4369 | // back to uniform-over-all if no seed landed in the set, so we never return |
| 4370 | // all-zero.) |
| 4371 | const r = new Array<number>(n).fill(0); |
| 4372 | let rsum = 0; |
| 4373 | for (const id of seedIds) { |
| 4374 | const i = idx.get(id); |
| 4375 | if (i !== undefined) { r[i] = 1; rsum += 1; } |
| 4376 | } |
| 4377 | if (rsum === 0) { for (let i = 0; i < n; i++) r[i] = 1; rsum = n; } |
| 4378 | for (let i = 0; i < n; i++) r[i]! /= rsum; |
| 4379 | |
| 4380 | const alpha = 0.25; |
| 4381 | let s = r.slice(); |
| 4382 | for (let iter = 0; iter < 25; iter++) { |
| 4383 | const next = new Array<number>(n).fill(0); |
| 4384 | for (let i = 0; i < n; i++) { |
| 4385 | const si = s[i]!; |
| 4386 | if (si === 0) continue; |
| 4387 | const d = adj[i]!.length; |
| 4388 | if (d === 0) { next[i]! += si; continue; } // dangling: keep its mass |
| 4389 | const share = si / d; |
| 4390 | for (const j of adj[i]!) next[j]! += share; |
| 4391 | } |
| 4392 | for (let i = 0; i < n; i++) s[i] = (1 - alpha) * next[i]! + alpha * r[i]!; |
| 4393 | } |
| 4394 | for (let i = 0; i < n; i++) out.set(nodeIds[i]!, s[i]!); |
| 4395 | return out; |
| 4396 | } |
| 4397 | |
| 4398 | /** |
| 4399 | * Handle codegraph_explore — deep exploration in a single call |