bobluppes / bobluppes/graaf

Add PageRank algorithm

Offen
#336 0 Kommentare 0 Reaktionen 0 zugewiesene Personen Auf GitHub ansehen
enhancement good first issue help wanted
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

Beitragsleitfaden öffnen

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

Neue Issues direkt in Ihr Postfach

Eine kurze Übersicht über anfängerfreundliche GitHub-Issues.