A vertex-centric Connected Components algorithm.
More...
|
| struct | Data |
| | This vertex-centric Connected Components algorithm does not require any algorithm parameters. More...
|
| |
|
| 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. More...
|
| |
| static void | program (VertexIDType ¤t_max_ID, const VertexIDType &incoming_message, VertexIDType &outgoing_message, const Data ¶meters, grb::interfaces::PregelState &pregel) |
| | The vertex-centric program for computing connected components. More...
|
| |
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. |
◆ execute()
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:
