kcore_decomposition.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_KCORE_DECOMPOSITION
#define _H_GRB_KCORE_DECOMPOSITION

#include <graphblas.hpp>


namespace grb {

    namespace algorithms {

        template<
            Descriptor descr = descriptors::no_operation,
            bool criticalSection = false,
            typename IOType, typename NZType
        >
        RC kcore_decomposition(
            const Matrix< NZType > &A,
            Vector< IOType > &core,
            Vector< IOType > &distances,
            Vector< IOType > &temp,
            Vector< IOType > &update,
            Vector< bool >   &status,
            IOType &k
        ) {
            // Add constants/expressions
            Semiring<
                operators::add< IOType >, operators::mul< IOType >,
                identities::zero, identities::one
            > ring;
            Monoid<
                operators::logical_or< bool >,
                identities::logical_false
            > lorMonoid;

            // Runtime sanity checks
            const size_t n = nrows(A);
            {
                // Verify that A is square
                if( n != ncols( A )){
                    return ILLEGAL;
                }
                // Verify sizes of vectors
                if( size( core ) != n ||
                    size( distances ) != n ||
                    size( temp ) != n ||
                    size( update ) != n ||
                    size( status ) != n
                ) {
                    return MISMATCH;
                }
                // Verify capacity
                if( capacity( core ) != n ||
                    capacity( distances ) != n ||
                    capacity( temp ) != n ||
                    capacity( update ) != n ||
                    capacity( status ) != n
                ) {
                    return ILLEGAL;
                }
            }

            // Initialise
            IOType current_k = 0; // current coreness level

            // Set initial values
            RC ret = grb::SUCCESS;
            ret = ret ? ret : set( temp, static_cast< IOType >( 1 ) );
            ret = ret ? ret : set( distances,  static_cast< IOType >( 0 ) );
            ret = ret ? ret : set( core,  static_cast< IOType >( 0 ) );
            ret = ret ? ret : set( status, true );
            ret = ret ? ret : clear( update );
            assert( ret == SUCCESS );

            ret = ret ? ret : grb::mxv< descr | descriptors::dense >(
                distances, A, temp, ring );
            assert( ret == SUCCESS );

            if( SUCCESS != ret ) {
                std::cerr << " Initialization of k-core decomposition failed with error "
                    << grb::toString( ret ) << "\n";
                return ret;
            }

            size_t count = 0;
            while( count < n && SUCCESS == ret ) {
                bool flag = true;

                // Update filter to exclude completed nodes
                ret = ret ? ret : set( update, status, status );

                while( flag ) {
                    flag = false;

                    // Update nodes in parallel
                    if( criticalSection ) {
                        ret = ret ? ret : clear( temp );
                        ret = ret ? ret : eWiseLambda( [ &, current_k ]( const size_t i ) {
                                if( status[ i ] && distances[ i ] <= current_k ) {
                                    core[ i ] = current_k;
                                    // Remove node from checking
                                    status[ i ] = false;
                                    // Set update
                                    flag = true;
                                    #pragma omp critical
                                    {
                                        // Add node index to update neighbours
                                        setElement( temp, 1, i );
                                    }
                                }
                            }, update,
                            status, distances, core, temp
                        );
                        // WARN: even with the below, this variant does not auto-parallelise in
                        //       the distributed-memory sense. The reason is a performance
                        //       contract violation by the above critical section -- setElement
                        //       should be a collective call, but its use from within eWiseLambda
                        //       does not ensure a collective call. The result is that PANIC will
                        //       at some point be returned.
                        //ret = ret ? ret : collectives<>::allreduce( flag,
                        //  lorMonoid.getOperator() );
                    } else {
                        ret = ret ? ret : eWiseApply( temp, status, distances, current_k,
                            operators::leq< IOType >() );
                        ret = ret ? ret : foldl( core, temp, current_k,
                            operators::right_assign< IOType >() );
                        ret = ret ? ret : foldl( status, temp, false,
                            operators::right_assign< bool >() );
                        ret = ret ? ret : foldl( flag, temp, lorMonoid );
                        ret = ret ? ret : set( update, temp, 1 );
                        if( ret == SUCCESS ) {
                            std::swap( update, temp );
                        }
                    }
                    assert( ret == SUCCESS );

                    if( ret == SUCCESS && flag ) {
                        ret = clear( update );
                        assert( ret == SUCCESS );

                        // Increase number of nodes completed
                        count += nnz( temp );

                        // Get the neighbours of the updated nodes
                        ret = ret ? ret : grb::mxv< descr >( update, A, temp, ring );
                        assert( ret == SUCCESS );

                        // Decrease distances of the neighbours
                        ret = ret ? ret : grb::eWiseApply( distances, distances, update,
                            operators::subtract< IOType >() );
                        assert( ret == SUCCESS );
                    }
                }
                (void) ++current_k;
            }

            if( SUCCESS != ret ){
                std::cerr << " Excecution of k-core decomposition failed with error "
                    << grb::toString(ret) << "\n";
            } else {
                k = current_k;
            }

            return ret;
        }

    } // namespace algorithms

} // namespace grb

#endif // end _H_GRB_KCORE_DECOMPOSITION