* 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>,
)
| 3186 | * it's a few hundred nodes × ~25 iterations — negligible cost. |
| 3187 | */ |
| 3188 | private computeGraphRelevance( |
| 3189 | nodeIds: string[], |
| 3190 | edges: Edge[], |
| 3191 | seedIds: Set<string>, |
| 3192 | ): Map<string, number> { |
| 3193 | const out = new Map<string, number>(); |
| 3194 | const n = nodeIds.length; |
| 3195 | if (n === 0) return out; |
| 3196 | const idx = new Map<string, number>(); |
| 3197 | for (let i = 0; i < n; i++) idx.set(nodeIds[i]!, i); |
| 3198 | |
| 3199 | const RANK_EDGES = new Set<string>([ |
| 3200 | 'calls', 'references', 'extends', 'implements', 'overrides', |
| 3201 | 'instantiates', 'returns', 'type_of', 'imports', |
| 3202 | ]); |
| 3203 | const adj: number[][] = Array.from({ length: n }, () => []); |
| 3204 | for (const e of edges) { |
| 3205 | if (!RANK_EDGES.has(e.kind)) continue; |
| 3206 | const i = idx.get(e.source); |
| 3207 | const j = idx.get(e.target); |
| 3208 | if (i === undefined || j === undefined || i === j) continue; |
| 3209 | adj[i]!.push(j); |
| 3210 | adj[j]!.push(i); // undirected — reachable either direction |
| 3211 | } |
| 3212 | |
| 3213 | // Restart vector: uniform over seeds present in the candidate set. (Falls |
| 3214 | // back to uniform-over-all if no seed landed in the set, so we never return |
| 3215 | // all-zero.) |
| 3216 | const r = new Array<number>(n).fill(0); |
| 3217 | let rsum = 0; |
| 3218 | for (const id of seedIds) { |
| 3219 | const i = idx.get(id); |
| 3220 | if (i !== undefined) { r[i] = 1; rsum += 1; } |
| 3221 | } |
| 3222 | if (rsum === 0) { for (let i = 0; i < n; i++) r[i] = 1; rsum = n; } |
| 3223 | for (let i = 0; i < n; i++) r[i]! /= rsum; |
| 3224 | |
| 3225 | const alpha = 0.25; |
| 3226 | let s = r.slice(); |
| 3227 | for (let iter = 0; iter < 25; iter++) { |
| 3228 | const next = new Array<number>(n).fill(0); |
| 3229 | for (let i = 0; i < n; i++) { |
| 3230 | const si = s[i]!; |
| 3231 | if (si === 0) continue; |
| 3232 | const d = adj[i]!.length; |
| 3233 | if (d === 0) { next[i]! += si; continue; } // dangling: keep its mass |
| 3234 | const share = si / d; |
| 3235 | for (const j of adj[i]!) next[j]! += share; |
| 3236 | } |
| 3237 | for (let i = 0; i < n; i++) s[i] = (1 - alpha) * next[i]! + alpha * r[i]!; |
| 3238 | } |
| 3239 | for (let i = 0; i < n; i++) out.set(nodeIds[i]!, s[i]!); |
| 3240 | return out; |
| 3241 | } |
| 3242 | |
| 3243 | /** |
| 3244 | * Handle codegraph_explore — deep exploration in a single call |