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

VertexIDType A 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]	pregel	A Pregel instance over which to execute the program.
[out]	group_ids	The ID of the component the corresponding vertex belongs to.
[in]	max_steps	A 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_taken A 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_ID	On 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_message	A buffer for incoming messages to a vertex program.
[in]	outgoing_message	A buffer for outgoing messages to a vertex program.
[in]	parameters	Global algorithm parameters, currently an instance of an empty struct (no parameters).
[in,out]	pregel	The 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:

pregel_connected_components.hpp

Classes

Static Public Member Functions

Detailed Description

Member Function Documentation

◆ execute()

◆ program()