pregel_connected_components.hpp

Go to the documentation of this file.

/*
 *   Copyright 2021 Huawei Technologies Co., Ltd.
 *
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 *     http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */

#ifndef _H_GRB_PREGEL_CONNECTEDCOMPONENTS
#define _H_GRB_PREGEL_CONNECTEDCOMPONENTS

#include <graphblas/interfaces/pregel.hpp>


namespace grb {

    namespace algorithms {

        namespace pregel {

            template< typename VertexIDType >
            struct ConnectedComponents {

                struct Data {};

                static void program(
                    VertexIDType &current_max_ID,
                    const VertexIDType &incoming_message,
                    VertexIDType &outgoing_message,
                    const Data &parameters,
                    grb::interfaces::PregelState &pregel
                ) {
                    (void) parameters;
                    if( pregel.round > 0 ) {
                        if( pregel.indegree == 0 ) {
                            pregel.voteToHalt = true;
                        } else if( current_max_ID < incoming_message ) {
                            current_max_ID = incoming_message;
                        } else {
                            pregel.voteToHalt = true;
                        }
                    }
                    if( pregel.outdegree > 0 ) {
                        outgoing_message = current_max_ID;
                    } else {
                        pregel.voteToHalt = true;
                    }
                }

                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
                ) {
                    const size_t n = pregel.numVertices();
                    if( grb::size( group_ids ) != n ) {
                        return MISMATCH;
                    }

                    grb::RC ret = grb::set< grb::descriptors::use_index >( group_ids, 1 );
                    if( ret != SUCCESS ) {
                        return ret;
                    }

                    grb::Vector< VertexIDType > in( n );
                    grb::Vector< VertexIDType > out( n );
                    grb::Vector< VertexIDType > out_buffer = interfaces::config::out_sparsify
                        ? grb::Vector< VertexIDType >( n )
                        : grb::Vector< VertexIDType >( 0 );

                    size_t steps;

                    ret = pregel.template execute<
                        grb::operators::max< VertexIDType >,
                        grb::identities::negative_infinity
                    > (
                        program,
                        group_ids,
                        Data(),
                        in, out,
                        steps,
                        out_buffer,
                        max_steps
                    );

                    if( ret == grb::SUCCESS && steps_taken != nullptr ) {
                        *steps_taken = steps;
                    }

                    return ret;
                }

            };

        } //end namespace `grb::algorithms::pregel'

    } // end namespace ``grb::algorithms''

} // end namespace ``grb''

#endif