PageRank< IOType, localConverge > Struct Template Reference

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

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

IOType	The type of the PageRank scores (e.g., double).
localConverge	Whether 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

PregelType

The 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]	pregel	The Pregel instance that this program should execute on.
[out]	scores	A 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_taken	How many rounds the program took until termination.

The following arguments are optional:

Parameters

[in]	parameters	The algorithm parameters. If not given, default values will be substituted.
[in]	max_steps	The 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_score	The current rank corresponding to this vertex.
[in]	incoming_message	Neighbour contributions to our score.
[out]	outgoing_message	The score contribution to send to our neighbours.
[in]	parameters	The algorithm parameters.
[in,out]	pregel	The 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:

• pregel_pagerank.hpp