[ALGO] Page Rank

[bobluppes]

Page Rank

The PageRank algorithm calculates the importance of each node in a graph based on the structure of incoming links. Originally designed for ranking web pages, it's widely applicable in various network analysis tasks. The algorithm iteratively distributes "rank" across nodes and converges to a steady state.

See the wikipedia entry for more details.

Syntax

The algorithm should have the following syntax:

 * @brief Computes the PageRank of each node in the graph.
 * 
 * This function calculates the PageRank values for each node in a given graph
 * based on the transition probabilities between nodes. The method iteratively
 * updates the rank values until they converge or reach the maximum number of iterations.
 *
 * @tparam GraphType Type of the graph
 * @param graph The graph object.
 * @param damping_factor The damping factor usually set between 0.8 to 0.9. Default is 0.85.
 * @param max_iterations The maximum number of iterations before the algorithm terminates. Default is 100.
 * @param tolerance The value to check for convergence of the PageRank values. Default is 1.0e-6.
 * 
 * @return std::optional<std::unordered_map<Vertex, double>> An optional containing the
 *         unordered map of PageRank values for each vertex if the algorithm converged,
 *         otherwise std::nullopt.
 */
template <typename GRAPH>
std::optional<std::unordered_map<vertex_id_t, double>> compute_pagerank(
    const GRAPH& graph,
    double damping_factor = 0.85,
    unsigned int max_iterations = 100,
    double tolerance = 1.0e-6
);

This should live in the graaf::algorithm namespace under include/graaflib/algorithm/page_rank.h.

Definition of Done

This issue is done when:

• The algorithm is implemented
• The new function has a javadoc-style comment explaining the interface
• Appropriate tests are added under test/graaflib/algorithm/page_rank_test.cpp
• A test coverage of at least 95% is reached
• A documentation entry is added under docs/docs/algorithms under the appropriate category
  • Just adding a short description and the algorithm syntax here is fine
  • See the wiki on how to build the documentation locally
• The algorithm is added to the list of algorithms in README.md

[sracha4355]

May I be assigned to this?

[bobluppes]

May I be assigned to this?

As discussed, we are currently limiting the number of [ALGO] tickets to one per person at a time; this in order to give everyone a fair chance to pick them up. Would be happy to assign it after #87 :)

[R055A]

Sure, I can do this task @bobluppes

[bobluppes]

Sure, I can do this task @bobluppes

Very nice, looking forward to your contribution :)

[bobluppes]

Hi @R055A, setting this to "open" for now.
Let me know if you still want to pick it up and I would be happy to re-assign :)

[R055A]

Hi @R055A, setting this to "open" for now.
Let me know if you still want to pick it up and I would be happy to re-assign :)

Hi. Sorry for the delay. I had planned to make a PR before end of October

[bobluppes]

Hi. Sorry for the delay. I had planned to make a PR before end of October

No problem! I will re-assign the ticket then.
And no rush, just trying to keep the issues up to date

[github-actions]

Stale issue message