ALP User Documentation 0.7.alpha
Algebraic Programming User Documentation
Loading...
Searching...
No Matches
Classes | Static Public Member Functions | List of all members
ConnectedComponents< VertexIDType > Struct Template Reference

A vertex-centric Connected Components algorithm. More...

#include <pregel_connected_components.hpp>

Classes

struct  Data
 This vertex-centric Connected Components algorithm does not require any algorithm parameters. More...
 

Static Public Member Functions

template<typename PregelType >
static grb::RC execute (grb::interfaces::Pregel< PregelType > &pregel, grb::Vector< VertexIDType > &group_ids, const size_t max_steps=0, size_t *const steps_taken=nullptr)
 A convenience function that, given a Pregel instance, executes the program.
 
static void program (VertexIDType &current_max_ID, const VertexIDType &incoming_message, VertexIDType &outgoing_message, const Data &parameters, grb::interfaces::PregelState &pregel)
 The vertex-centric program for computing connected components.
 

Detailed Description

template<typename VertexIDType>
struct grb::algorithms::pregel::ConnectedComponents< VertexIDType >

A vertex-centric Connected Components algorithm.

Template Parameters
VertexIDTypeA type large enough to assign an ID to each vertex in the graph the algorithm is to run on.

Member Function Documentation

◆ execute()

static grb::RC execute ( grb::interfaces::Pregel< PregelType > &  pregel,
grb::Vector< VertexIDType > &  group_ids,
const size_t  max_steps = 0,
size_t *const  steps_taken = nullptr 
)
inlinestatic

A convenience function that, given a Pregel instance, executes the program.

Parameters
[in,out]pregelA Pregel instance over which to execute the program.
[out]group_idsThe ID of the component the corresponding vertex belongs to.
[in]max_stepsA maximum number of rounds the program is allowed to run. If 0, no maximum number of rounds will be in effect.

On succesful termination, the number of rounds is optionally written out:

Parameters
[out]steps_takenA pointer to where the number of rounds should be recorded. Will not be used if equal to nullptr.

◆ program()

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

The vertex-centric program for computing connected components.

On termination, the number of individual IDs in current_max_ID signifies the number of components, while the value at each entry signifies which component the vertex corresponds to.

Parameters
[in,out]current_max_IDOn input: each entry is set to an unique ID, corresponding to a unique ID for each vertex. On output: the ID of the component the corresponding vertex belongs to.
[in]incoming_messageA buffer for incoming messages to a vertex program.
[in]outgoing_messageA buffer for outgoing messages to a vertex program.
[in]parametersGlobal algorithm parameters, currently an instance of an empty struct (no parameters).
[in,out]pregelThe Pregel state the program may refer to.

This program 1) broadcasts its current ID to its neighbours, 2) checks if any received IDs are larger than the current ID, then 3a) if not, votes to halt; 3b) if yes, replaces the current ID with the received maximum. It is meant to be executed using a max monoid as message aggregator.


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