Program Listing for File CoreDecomposition.hpp¶

/*
 * CoreDecomposition.hpp
 *
 *  Created on: Oct 28, 2013
 *      Author: Lukas Barth, David Weiss, Christian Staudt
 */

#ifndef NETWORKIT_CENTRALITY_CORE_DECOMPOSITION_HPP_
#define NETWORKIT_CENTRALITY_CORE_DECOMPOSITION_HPP_

#include <list>
#include <string>
#include <vector>

#include <networkit/centrality/Centrality.hpp>
#include <networkit/graph/Graph.hpp>
#include <networkit/structures/Cover.hpp>
#include <networkit/structures/Partition.hpp>

namespace NetworKit {

class CoreDecomposition : public Centrality {

public:
    CoreDecomposition(const Graph &G, bool normalized = false,
                      bool enforceBucketQueueAlgorithm = false, bool storeNodeOrder = false);

    void run() override;

    Cover getCover() const;

    Partition getPartition() const;

    index maxCoreNumber() const;

    double maximum() override;

    const std::vector<node> &getNodeOrder() const;

private:
    index maxCore; // maximum core number of any node in the graph

    bool enforceBucketQueueAlgorithm; // in case one wants to switch to the alternative algorithm

    bool canRunInParallel; // signifies if a parallel algorithm can be used

    bool storeNodeOrder; // signifies if the node order shall be stored

    std::vector<node> nodeOrder; // Stores the node order, i.e., all nodes sorted by core number

    void runWithParK();

    void runWithBucketQueues();

    void scan(index level, const std::vector<count> &degrees, std::vector<node> &curr);

    void scanParallel(index level, const std::vector<count> &degrees, std::vector<node> &curr,
                      std::vector<char> &active);

    void processSublevel(index level, std::vector<count> &degrees, const std::vector<node> &curr,
                         std::vector<node> &next);

    void processSublevelParallel(index level, std::vector<count> &degrees,
                                 const std::vector<node> &curr, std::vector<node> &next,
                                 std::vector<char> &active);
};

} /* namespace NetworKit */
#endif // NETWORKIT_CENTRALITY_CORE_DECOMPOSITION_HPP_