Chapter 3

The Algorithms

This is the heart of travsr, and the heart of its first principle: “algorithms first, LLM last.” When you ask a question, classic graph algorithms find the answer. The AI only rephrases your question going in and formats the answer coming out. Here are the five algorithms that actually ship, each animated, each with the real numbers from the code.

PageRank → relevance Knapsack → fit the budget PCST → connect two points K-core → find the core BM25 → keyword ranking

① Personalized PageRank (PPR): “what’s relevant to this?”

This is the workhorse. Same math Google used to rank web pages, but “personalized” to a starting point. The question it answers: “If I start at this function and wander the call-graph, preferring strong roads (calls) over weak ones (imports), which other functions do I keep ending up at?” Those are the most relevant ones.

Explain like I’m 5 Stand on one function and shout. The shout travels along the “calls” and gets louder where lots of code is connected. The loudest spots are what matters most for your question.
Analogy

Drop a thousand walkers on charge(). At every step they either follow an outgoing road (bigger roads more likely) or, with a 15% chance, teleport back to the start. Count where the crowd piles up. That pile-up is the relevance score.

PageRank converging from a seed
low score → → high score

Pick a seed and step through. Brighter = higher PageRank score = more relevant.

The real knobs (from the code)

ALPHA (damping)0.85
EPSILON (stop when change <)1e-6
MAX_ITERATIONS50
crates/travsr-retrieval/src/ppr.rs

All three are overridable at runtime via TRAVSR_PPR_ALPHA / TRAVSR_PPR_EPSILON / TRAVSR_PPR_MAX_ITER.

One iteration, in words

For every node, its new score = 85% of the score flowing in along edges (split by each road’s weight) + 15% teleported back to the seed. Repeat until the scores stop moving (≈ 15–30 rounds). A recent upgrade, ppr_weighted, lets you start from several seeds, each with its own confidence, that’s how semantic search plugs in (Chapter 4).

② 0/1 Knapsack: “fit the best answer in the token budget”

PageRank gives you a ranked pile of relevant functions. But an AI has a limited “context window”, you can only send it so many words (tokens). Which subset do you send? The one with the most total relevance that still fits. That’s the classic knapsack problem.

Explain like I’m 5 Your backpack only holds so much. Each function has a “usefulness” and a “size”. Pack the most usefulness without overflowing, that’s what gets sent to the AI.
Analogy

You’re packing a suitcase with a strict weight limit. Each item has a value (PageRank score) and a weight (how many tokens it costs). Maximize value without going over. travsr literally solves this to build the AI’s context.

Packing the token budget

Drag the budget. Green = packed (sent to the AI). Grey = left out. The solver maximizes total relevance under the limit.

The real details (from the code)

  • Token cost of a node ≈ (signature + kind + path) length ÷ 4 characters-per-token.
  • Exact 2-D dynamic programming when the table (items × budget) ≤ 500,000 cells; otherwise a fast greedy value/cost fallback.
  • Hard cap MAX_CONTEXT_BUDGET = 32,000 tokens (Claude’s practical limit).
crates/travsr-retrieval/src/knapsack.rs

③ PCST: “connect these two functions cheaply”

The get_execution_path(source, sink) tool answers: “how does data/control flow get from A to B?” travsr finds the cheapest chain of edges linking them. It’s a practical approximation of a “Prize-Collecting Steiner Tree” (PCST).

Explain like I’m 5 Like GPS directions between two functions. It finds the shortest chain of calls from A to B, treating strong direct calls as fast roads and weak links as slow detours.
Analogy

Cheapest route between two landmarks. Strong roads (direct calls) are “cheap” to travel; weak roads cost more. The route it returns is the most likely real execution path.

Shortest cost path: source → sink

Pick a start and end. The highlighted chain is the lowest-cost path, where cost = 1 − edge weight.

The real details (from the code)

  • Builds a bidirectional BFS bubble around source & sink (depth ≤ 5, ≤ 2000 nodes).
  • Runs Dijkstra over it with edge cost = 1.0 − ppr_weight (strong calls are cheapest).
  • If no path is found (endpoint unreachable within the bubble), it safely falls back to a depth-3 BFS. An earlier wall-clock timeout was deliberately removed: a post-hoc check can't interrupt already-completed work, and it made results nondeterministic.
crates/travsr-retrieval/src/pcst.rs

④ K-core: “find the structural backbone”

Some code is peripheral (a one-off helper); some is central (everything leans on it). K-core decomposition assigns every node a “shell number”: how deep into the densely-connected core it sits. travsr uses this to boost central code in results.

Explain like I’m 5 Peel the graph like an onion, lonely functions fall off first, the tightly-linked center stays last. Whatever survives to the middle is the most important “downtown” code.
Analogy

Peel an onion from the outside in. Loosely-connected nodes peel off first (low shell). The tightly-interwoven center survives longest (high shell), that’s your downtown.

Peeling the graph into shells

Repeatedly remove the least-connected nodes. The round a node is removed in = its shell number.

The real details (from the code)

  • Batagelj–Zaveršnik bucket-peeling, runs in O(V + E) (linear, very fast).
  • Two phases: peel to get raw shells, then propagate a package’s shell down to the symbols it contains, so a function in a central module inherits that centrality.
  • Recomputed after every index so it’s always current.
crates/travsr-retrieval/src/kcore.rs

⑤ BM25: “rank by keyword match”

Before any graph walk, travsr has to find a good starting node from your words. BM25 is the classic search-engine ranking that librarians and Elasticsearch use: it scores how well a query’s words match each symbol’s text, rewarding rare words and not over-rewarding long documents.

Explain like I’m 5 It’s how a search box decides which results go first. If you search for a rare word and a function has it, that function jumps to the top. Common words count for less.
Analogy

A librarian ranking books for your search. A book that mentions a rare word you asked for ranks higher than one full of common words. Length is accounted for so thick books don’t win by bulk.

BM25 ranking symbols for a query

Type words found in the function names. Bars show BM25 relevance scores. Tokenizer splits camelCase & snake_case, like the real one.

The real details (from the code)

  • Okapi BM25 with K1 = 1.2, B = 0.75 (textbook defaults).
  • Robertson–Spärck-Jones IDF with +1 smoothing so scores stay positive.
  • Same tokenizer as the search index: splits camelCase & snake_case, drops tokens shorter than 3 chars.
crates/travsr-retrieval/src/bm25.rs

How they combine: the get_context pipeline

When an AI calls get_context("how are payments charged?", budget=2000), all five cooperate, alongside one neural step, a cross-encoder reranker (travsr-rerank, RFC-021) that judges relevance directly rather than by graph position:

Find & fuse seeds (RRF)

Three candidate lists, exact/anchor matches, lexical full-text (BM25-style FTS), and, if enabled, semantic KNN, are merged with Reciprocal-Rank Fusion (constant k = 60). A node that ranks high in several lists wins. If nothing scores well enough, travsr abstains rather than return noise.

Rerank the seeds

The cross-encoder scores each fused seed against the query directly. Its score feeds the seed's PPR personalization weight (RFC-022), so it shapes where PageRank starts rather than just re-sorting a finished list. Skipped entirely if the model is absent.

Walk the graph

Weighted PageRank (ppr_weighted) spreads relevance out from those seeds along the call edges, higher-confidence seeds pull harder.

Boost the backbone

K-core shells nudge structurally-central code up the ranking.

Pack the budget

Knapsack selects the most-relevant subset that fits the token budget.

Return clean context

The AI gets exact file:line references, real structure, no hallucinated links.

crates/travsr-mcp/src/seed.rs (rrf_fuse, k=60) · travsr-rerank/src/lib.rs · query.rs
Next: the newest piece, semantic search →