ALP User Documentation 0.7.alpha
Algebraic Programming User Documentation
Loading...
Searching...
No Matches
pregel_connected_components.hpp
Go to the documentation of this file.
1
2/*
3 * Copyright 2021 Huawei Technologies Co., Ltd.
4 *
5 * Licensed under the Apache License, Version 2.0 (the "License");
6 * you may not use this file except in compliance with the License.
7 * You may obtain a copy of the License at
8 *
9 * http://www.apache.org/licenses/LICENSE-2.0
10 *
11 * Unless required by applicable law or agreed to in writing, software
12 * distributed under the License is distributed on an "AS IS" BASIS,
13 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
14 * See the License for the specific language governing permissions and
15 * limitations under the License.
16 */
17
27#ifndef _H_GRB_PREGEL_CONNECTEDCOMPONENTS
28#define _H_GRB_PREGEL_CONNECTEDCOMPONENTS
29
31
32
33namespace grb {
34
35 namespace algorithms {
36
37 namespace pregel {
38
47 template< typename VertexIDType >
49
54 struct Data {};
55
81 static void program(
82 VertexIDType &current_max_ID,
83 const VertexIDType &incoming_message,
84 VertexIDType &outgoing_message,
85 const Data &parameters,
87 ) {
88 (void) parameters;
89 if( pregel.round > 0 ) {
90 if( pregel.indegree == 0 ) {
91 pregel.voteToHalt = true;
92 } else if( current_max_ID < incoming_message ) {
93 current_max_ID = incoming_message;
94 } else {
95 pregel.voteToHalt = true;
96 }
97 }
98 if( pregel.outdegree > 0 ) {
99 outgoing_message = current_max_ID;
100 } else {
101 pregel.voteToHalt = true;
102 }
103 }
104
124 template< typename PregelType >
128 const size_t max_steps = 0,
129 size_t * const steps_taken = nullptr
130 ) {
131 const size_t n = pregel.num_vertices();
132 if( grb::size( group_ids ) != n ) {
133 return MISMATCH;
134 }
135
136 grb::RC ret = grb::set< grb::descriptors::use_index >( group_ids, 1 );
137 if( ret != SUCCESS ) {
138 return ret;
139 }
140
146
147 size_t steps;
148
149 ret = pregel.template execute<
152 > (
153 program,
154 group_ids,
155 Data(),
156 in, out,
157 steps,
158 out_buffer,
159 max_steps
160 );
161
162 if( ret == grb::SUCCESS && steps_taken != nullptr ) {
163 *steps_taken = steps;
164 }
165
166 return ret;
167 }
168
169 };
170
171 } //end namespace `grb::algorithms::pregel'
172
173 } // end namespace ``grb::algorithms''
174
175} // end namespace ``grb''
176
177#endif
178
A GraphBLAS vector.
Definition: vector.hpp:64
Standard identity for the maximum operator.
Definition: identities.hpp:124
A Pregel run-time instance.
Definition: pregel.hpp:340
size_t num_vertices() const noexcept
Queries the maximum vertex ID for programs running on this Pregel instance.
Definition: pregel.hpp:928
This operator takes the maximum of the two input parameters and writes the result to the output varia...
Definition: ops.hpp:241
size_t size(const Vector< DataType, backend, Coords > &x) noexcept
Request the size of a given vector.
Definition: io.hpp:235
constexpr const SparsificationStrategy out_sparsify
What sparsification strategy should be applied to the outgoing messages.
Definition: pregel.hpp:242
The ALP/GraphBLAS namespace.
Definition: graphblas.hpp:450
RC
Return codes of ALP primitives.
Definition: rc.hpp:47
@ MISMATCH
One or more of the ALP/GraphBLAS objects passed to the primitive that returned this error have mismat...
Definition: rc.hpp:90
@ SUCCESS
Indicates the primitive has executed successfully.
Definition: rc.hpp:54
This file defines a vertex-centric programming API called ALP/Pregel, which automatically translates ...
This vertex-centric Connected Components algorithm does not require any algorithm parameters.
Definition: pregel_connected_components.hpp:54
A vertex-centric Connected Components algorithm.
Definition: pregel_connected_components.hpp:48
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.
Definition: pregel_connected_components.hpp:125
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.
Definition: pregel_connected_components.hpp:81
The state of the vertex-center Pregel program that the user may interface with.
Definition: pregel.hpp:266
bool & voteToHalt
Represents whether this (active) vertex votes to terminate the program.
Definition: pregel.hpp:291
const size_t & indegree
The in-degree of this vertex.
Definition: pregel.hpp:311
const size_t & round
The current round the vertex-centric program is currently executing.
Definition: pregel.hpp:316
const size_t & outdegree
The out-degree of this vertex.
Definition: pregel.hpp:306