ALP User Documentation 0.7.alpha
Algebraic Programming User Documentation
Loading...
Searching...
No Matches
pregel_pagerank.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_PAGERANK
28#define _H_GRB_PREGEL_PAGERANK
29
31
32
33namespace grb {
34
35 namespace algorithms {
36
37 namespace pregel {
38
53 template< typename IOType, bool localConverge >
54 struct PageRank {
55
59 struct Data {
60
64 IOType alpha = 0.15;
65
69 IOType tolerance = 0.00001;
70
71 };
72
87 static void program(
88 IOType &current_score,
89 const IOType &incoming_message,
90 IOType &outgoing_message,
91 const Data &parameters,
93 ) {
94 // initialise
95 if( pregel.round == 0 ) {
96 current_score = static_cast< IOType >( 1 );
97 }
98
99#ifdef _DEBUG
100 // when in debug mode, probably one does not wish to track the state of
101 // each vertex individually, hence we include a simple guard by default:
102 const bool dbg = pregel.vertexID == 0;
103 if( dbg ) {
104 std::cout << "ID: " << pregel.vertexID << "\n"
105 << "\t active: " << pregel.active << "\n"
106 << "\t round: " << pregel.round << "\n"
107 << "\t previous score: " << current_score << "\n"
108 << "\t incoming message: " << incoming_message << "\n";
109 }
110#endif
111
112 // compute
113 if( pregel.round > 0 ) {
114 const IOType old_score = current_score;
115 current_score = parameters.alpha +
116 (static_cast< IOType >(1) - parameters.alpha) * incoming_message;
117 if( fabs(current_score-old_score) < parameters.tolerance ) {
118#ifdef _DEBUG
119 std::cout << "\t\t vertex " << pregel.vertexID << " converged\n";
120#endif
121 if( localConverge ) {
122 pregel.active = false;
123 } else {
124 pregel.voteToHalt = true;
125 }
126 }
127 }
128
129 // broadcast
130 if( pregel.outdegree > 0 ) {
131 outgoing_message =
132 current_score /
133 static_cast< IOType >(pregel.outdegree);
134 }
135
136#ifdef _DEBUG
137 if( dbg ) {
138 std::cout << "\t current score: " << current_score << "\n"
139 << "\t voteToHalt: " << pregel.voteToHalt << "\n"
140 << "\t outgoing message: " << outgoing_message << "\n";
141 }
142#endif
143
144 }
145
182 template< typename PregelType >
185 grb::Vector< IOType > &scores,
186 size_t &steps_taken,
187 const Data &parameters = Data(),
188 const size_t max_steps = 0
189 ) {
190 const size_t n = pregel.num_vertices();
191 if( grb::size( scores ) != n ) {
192 return MISMATCH;
193 }
194
195 grb::Vector< IOType > in( n );
196 grb::Vector< IOType > out( n );
200
201 return pregel.template execute<
204 > (
205 program,
206 scores,
207 parameters,
208 in, out,
209 steps_taken,
210 out_buffer,
211 max_steps
212 );
213 }
214
215 };
216
217 } //end namespace `grb::algorithms::pregel'
218
219 } // end namespace ``grb::algorithms''
220
221} // end namespace ``grb''
222
223#endif
224
A GraphBLAS vector.
Definition: vector.hpp:64
Standard identity for numerical addition.
Definition: identities.hpp:57
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 sum of the two input parameters and writes it to the output variable.
Definition: ops.hpp:174
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
This file defines a vertex-centric programming API called ALP/Pregel, which automatically translates ...
The algorithm parameters.
Definition: pregel_pagerank.hpp:59
IOType alpha
The probability of jumping to a random page instead of a linked page.
Definition: pregel_pagerank.hpp:64
IOType tolerance
The local convergence criterion.
Definition: pregel_pagerank.hpp:69
A Pregel-style PageRank-like algorithm.
Definition: pregel_pagerank.hpp:54
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.
Definition: pregel_pagerank.hpp:87
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.
Definition: pregel_pagerank.hpp:183
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
bool & active
Represents whether the current vertex is active.
Definition: pregel.hpp:282
const size_t & round
The current round the vertex-centric program is currently executing.
Definition: pregel.hpp:316
const size_t & vertexID
A unique ID of this vertex.
Definition: pregel.hpp:324
const size_t & outdegree
The out-degree of this vertex.
Definition: pregel.hpp:306