ALP User Documentation 0.7.0
Algebraic Programming User Documentation
Classes | Static Public Member Functions | List of all members
PageRank< IOType, localConverge > Struct Template Reference

A Pregel-style PageRank-like algorithm. More...

#include <pregel_pagerank.hpp>

Classes

struct  Data
 The algorithm parameters. More...
 

Static Public Member Functions

template<typename PregelType >
static grb::RC execute (grb::interfaces::Pregel< PregelType > &pregel, grb::Vector< IOType > &scores, size_t &steps_taken, const Data &parameters=Data(), const size_t max_steps=0)
 A convenience function for launching a PageRank algorithm over a given Pregel instance. More...
 
static void program (IOType &current_score, const IOType &incoming_message, IOType &outgoing_message, const Data &parameters, grb::interfaces::PregelState &pregel)
 The vertex-centric PageRank-like program. More...
 

Detailed Description

template<typename IOType, bool localConverge>
struct grb::algorithms::pregel::PageRank< IOType, localConverge >

A Pregel-style PageRank-like algorithm.

This vertex-centric program does not correspond to the canonical PageRank algorithm by Brin and Page. In particular, it misses corrections for dangling nodes and does not perform convergence checks in any norm.

Template Parameters
IOTypeThe type of the PageRank scores (e.g., double).
localConvergeWhether vertices become inactive once their local scores have converged, or whether to terminate only when all vertices have converged.

Member Function Documentation

◆ execute()

static grb::RC execute ( grb::interfaces::Pregel< PregelType > &  pregel,
grb::Vector< IOType > &  scores,
size_t &  steps_taken,
const Data parameters = Data(),
const size_t  max_steps = 0 
)
inlinestatic

A convenience function for launching a PageRank algorithm over a given Pregel instance.

Template Parameters
PregelTypeThe nonzero type of an edge in the Pregel instance.

This convenience function materialises the buffers expected to be passed into the Pregel instance, and selects the expected monoid for executing this program.

Warning
In performance-critical code, one may want to pre-allocate the buffers instead of having this convenience function allocate those. In such cases, please call manually the Pregel execute function, i.e., grb::interfaces::Pregel< PregelType >::execute.

The following arguments are mandatory:

Parameters
[in]pregelThe Pregel instance that this program should execute on.
[out]scoresA vector that corresponds to the scores corresponding to each vertex. It must be of size equal to the number of vertices \( n \) in the pregel instance, and must have \( n \) capacity and values. The initial contents are ignored by this algorithm.
[out]steps_takenHow many rounds the program took until termination.

The following arguments are optional:

Parameters
[in]parametersThe algorithm parameters. If not given, default values will be substituted.
[in]max_stepsThe maximum number of rounds this program may take. If not given, the number of rounds will be unlimited.

◆ program()

static void program ( IOType &  current_score,
const IOType &  incoming_message,
IOType &  outgoing_message,
const Data parameters,
grb::interfaces::PregelState pregel 
)
inlinestatic

The vertex-centric PageRank-like program.

Parameters
[out]current_scoreThe current rank corresponding to this vertex.
[in]incoming_messageNeighbour contributions to our score.
[out]outgoing_messageThe score contribution to send to our neighbours.
[in]parametersThe algorithm parameters.
[in,out]pregelThe state of the Pregel interface.

The Pregel program expects incoming messages to be aggregated using a plus monoid over elements of IOType.


The documentation for this struct was generated from the following file: