Disclose how far down the PageRank order is provably correct
- Dominant language
- C++
- Stars
- 2.1k
- Forks
- 125
- Avg merge
- 5h 28m
- Merged PRs (30d)
- 163
Description
## What is missing
ripwire's maps are ordered by a PageRank power iteration that stops at a tolerance, so every score
carries a small, knowable error — and near the bottom of a list, neighbouring rows can sit closer
together than that error. Today the output says how many iterations ran (`pr_iters=`) and whether
they stopped short (`pr_converged="0"`), but nothing says where the order stops being certain. The
ask is a conservative bound derived from the code, measured against real rankings, and disclosed as
an attribute in the same spirit as floors and disclosed caps: an honest "this far, the order is
certain".
## The evidence
Facts read from the code, each of which the derivation has to respect:
- `PageRankConfig` defaults to tolerance `1e-6` and a 100-iteration ceiling; the loop stops on the
L1 residual between successive iterates and returns the newer one.
- The `α` the loop actually receives is `double( 0.85f )` = 0.850000023841857910…, **not** 0.85,
because `rankGraphTeleport` takes a `float alpha`. At that value `α·τ/(1 − α)` is about
**5.667e-6**.
- `PageRankRun` returns the iteration count and a converged flag — **not** the final residual.
- The rank vector is narrowed to `float` before the sort, which orders by score descending and id
ascending; `k=` prints four decimals.
- Emission order is **not** rank order: the default map buckets by file, `--stable` emits path
order, and important-last reverses.
- MCP `tools/list` is 42,177 B against a 42,200 B ceiling — about 23 bytes of headroom for any
tool-description change.
## Size
**Medium** end to end: the derivation, the measurement, the attribute across every PageRank-ordered
surface, and the gate. **The measurement on its own is small**, and is the recommended first pull
request — the distribution of the certified prefix against rows shown, on real corpora, before any
attribute exists. The name and the absence convention get agreed in that discussion.
## Prerequisites
Comfort with a contraction-mapping argument and floating-point error bounds, plus C++ in this
repository's style (`CONTRIBUTING.md` §3). At least two external corpora of different sizes plus one
large one.
## Where to start
`prompts/help-wanted/certified-ranking-order.md` is a self-contained prompt for a coding agent. It
carries the arithmetic sketched against the code (what the loop returns, why it is a contraction,
the a posteriori bound, how an L1 bound becomes a certified prefix), the error sources that bound
does **not** cover, the measure-first step, the naming and absence decisions, near-tie fixtures with
an exact rational oracle, the acceptance criteria and the traps. Like every prompt in `prompts/`,
**it ends by writing a plan and stopping** — a maintainer agrees the plan before any code is
written.
Comment here to claim it.
Contributor guide
Research direction
Start with prompts/help-wanted/certified-ranking-order.md and read CONTRIBUTING.md §3 for the repository’s C++ style. Run the prompt’s measure-first step against at least two external corpora and one large corpus, including near-tie fixtures with the exact rational oracle. Done for this scope means a measured certified-prefix distribution and an agreed plan for the derivation, naming, absence convention, attribute, and gate; stop for maintainer review before coding.
Written by the indexing model from the issue text.
Assessment
- Tech stack
- cpp
- Domain
- cli, tooling
- Issue type
- Feature
- Difficulty
- 5/5
- Estimated time
- Over a week
- Activity status
- Active
- Clarity
- Mostly clear
- Newbie friendliness
- 35/100