Add PageRank algorithm
- Vorherrschende Sprache
- C++
- Sterne
- 413
- Forks
- 67
- Ø Merge
- 7 Std. 24 Min.
- Gemergte PRs (30 T.)
- 53
Beschreibung
## Summary
Graaf has no PageRank implementation, or any other iterative graph-ranking algorithm.
## Current state
A search across `include/graaflib/` for "pagerank"/"page_rank" returns no results, and there is no `algorithm/ranking/` (or similar) category. There is a related historical request, [#90 "[ALGO] Page Rank"](../issues/90), which was closed without being implemented (closed due to inactivity, not as "won't do").
## Why this matters
PageRank (and the broader family of iterative eigenvector-based ranking algorithms it represents) is one of the most widely recognized graph algorithms outside of pure computer science — used for web ranking, recommendation systems, citation analysis, and influence scoring in social/organizational networks. Its absence is a notable gap for anyone evaluating the library specifically for graph-analytics use cases (as opposed to pathfinding/traversal use cases, which are already well covered).
## Suggested resolution
- Implement PageRank (the standard damping-factor, iterative-until-convergence formulation) for directed graphs, under a new `include/graaflib/algorithm/ranking/` (or similarly named) category.
- Expose the damping factor, convergence tolerance, and max-iteration count as parameters.
- Add corresponding documentation under `docs/docs/algorithms/`, including complexity and convergence behavior.
## Acceptance criteria
- [ ] PageRank is implemented for directed graphs.
- [ ] Damping factor, convergence tolerance, and iteration limit are configurable.
- [ ] Documentation added, including complexity and convergence characteristics.
- [ ] Unit tests cover a known small graph with hand-verifiable expected rankings, dangling nodes (no outgoing edges), and disconnected components.
Beitragsleitfaden
Rechercherichtung
The issue specifies implementing PageRank in a new directory `include/graaflib/algorithm/ranking/`. Start by examining the existing algorithm implementations in `include/graaflib/algorithm/` to understand the library's patterns. Review the directed graph structure to understand adjacency representation. The algorithm needs to handle damping factor, convergence tolerance, and max iterations. Write unit tests for small graphs with known rankings, dangling nodes, and disconnected components as acceptance criteria require.
Vom Indexierungsmodell aus dem Issue-Text verfasst.
Bewertung
- Tech-Stack
- cpp
- Issue-Typ
- Feature
- Schwierigkeit
- 4/5
- Geschätzter Aufwand
- 3-5 Tage
- Aktivitätsstatus
- Aktiv
- Klarheit
- Klar beschrieben
- Anfängerfreundlichkeit
- 45/100