ClusterSnnGraph.hpp

Go to the documentation of this file.

#ifndef SCRAN_SNNGRAPHCLUSTERING_HPP
#define SCRAN_SNNGRAPHCLUSTERING_HPP
 
#include "../utils/macros.hpp"
 
#include "BuildSnnGraph.hpp"
 
#include <vector>
#include <algorithm>
 
#include "igraph.h"
#include "igraph_utils.hpp"
 
namespace scran {
 
class ClusterSnnGraphMultiLevel {
public:
    struct Defaults {
        static constexpr double resolution = 1;
 
        static constexpr int seed = 42;
    };
 
private:
    double resolution = Defaults::resolution;
    int seed = Defaults::seed;
 
public:
    ClusterSnnGraphMultiLevel& set_seed(int s = Defaults::seed) {
        seed = s;
        return *this;
    }
 
    ClusterSnnGraphMultiLevel& set_resolution(double r = Defaults::resolution) {
        resolution = r;
        return *this;
    }
 
public:
    struct Results {
        int status = 0;
        
        size_t max = 0;
 
        std::vector<std::vector<int> > membership;
 
        std::vector<double> modularity;
    };
 
    Results run(const BuildSnnGraph::Results& store) const {
        return run(store.to_igraph(), store.weights.data());
    }
 
    Results run(const igraph::Graph& graph, const igraph_real_t* weights) const {
        igraph::IntegerVector membership_holder;
        igraph::RealVector modularity_holder;
        igraph::IntegerMatrix memberships_holder;
        igraph::RNGScope rngs(seed);
 
        auto& modularity = modularity_holder.vector;
        auto& membership = membership_holder.vector;
        auto& memberships = memberships_holder.matrix;
 
        // No need to free this, as it's just a view.
        igraph_vector_t weight_view;
        igraph_vector_view(&weight_view, weights, igraph_ecount(graph.get_graph()));
 
        Results output;
        output.status = igraph_community_multilevel(graph.get_graph(), &weight_view, resolution, &membership, &memberships, &modularity);
 
        if (!output.status) {
            output.max = igraph_vector_which_max(&modularity);
 
            size_t nmods = igraph_vector_size(&modularity);
            output.modularity.resize(nmods);
            for (size_t i = 0; i < nmods; ++i) {
                output.modularity[i] = VECTOR(modularity)[i];
            }
 
            size_t ncells = igraph_vcount(graph.get_graph());
            size_t nlevels = igraph_matrix_int_nrow(&memberships);
            output.membership.resize(nlevels);
            
            for (size_t i = 0; i < nlevels; ++i) {
                auto& current = output.membership[i];
                current.resize(ncells);
                for (size_t j = 0; j < ncells; ++j) {
                    current[j] = MATRIX(memberships, i, j);
                }
            }
        }
 
        return output;
    }
};
 
class ClusterSnnGraphWalktrap {
public:
    struct Defaults {
        static constexpr int steps = 4;
    };
 
private:
    int steps = Defaults::steps;
 
public:
    ClusterSnnGraphWalktrap& set_steps(int s = Defaults::steps) {
        steps = s;
        return *this;
    }
 
public:
    struct Results {
        int status = 0;
        
        std::vector<int> membership;
 
        std::vector<std::pair<int, int> > merges;
 
        std::vector<double> modularity;
    };
 
    Results run(const BuildSnnGraph::Results& store) const {
        return run(store.to_igraph(), store.weights.data());
    }
 
    Results run(const igraph::Graph& graph, const igraph_real_t* weights) const {
        igraph::IntegerMatrix merges_holder;
        igraph::RealVector modularity_holder;
        igraph::IntegerVector membership_holder;
 
        auto& modularity = modularity_holder.vector;
        auto& membership = membership_holder.vector;
        auto& merges = merges_holder.matrix;
 
        // No need to free this, as it's just a view.
        igraph_vector_t weight_view;
        igraph_vector_view(&weight_view, weights, igraph_ecount(graph.get_graph()));
 
        Results output;
        output.status = igraph_community_walktrap(graph.get_graph(), &weight_view, steps, &merges, &modularity, &membership);
 
        if (!output.status) {
            size_t nmods = igraph_vector_size(&modularity);
            output.modularity.resize(nmods);
            for (size_t i = 0; i < nmods; ++i) {
                output.modularity[i] = VECTOR(modularity)[i];
            }
 
            size_t nmerges = igraph_matrix_int_nrow(&merges);
            output.merges.resize(nmerges);
            for (size_t i = 0; i < nmerges; ++i) {
                output.merges[i].first = MATRIX(merges, i, 0);
                output.merges[i].second = MATRIX(merges, i, 1);
            }
 
            size_t ncells = igraph_vcount(graph.get_graph());
            output.membership.resize(ncells);
            for (size_t i = 0; i < ncells; ++i) {
                output.membership[i] = VECTOR(membership)[i];
            }
        }
 
        return output;
    }
};
 
class ClusterSnnGraphLeiden {
public:
    struct Defaults {
        static constexpr double resolution = 1;
 
        static constexpr double beta = 0.01;
 
        static constexpr int iterations = 2;
 
        static constexpr bool modularity = false;
 
        static constexpr int seed = 42;
    };
 
private:
    double resolution = Defaults::resolution;
    double beta = Defaults::beta;
    int iterations = Defaults::iterations;
    bool modularity = Defaults::modularity;
    int seed = Defaults::seed;
 
public:
    ClusterSnnGraphLeiden& set_seed(int s = Defaults::seed) {
        seed = s;
        return *this;
    }
 
    ClusterSnnGraphLeiden& set_resolution(double r = Defaults::resolution) {
        resolution = r;
        return *this;
    }
 
    ClusterSnnGraphLeiden& set_beta(double b = Defaults::beta) {
        beta = b;
        return *this;
    }
 
    ClusterSnnGraphLeiden& set_iterations(int i = Defaults::iterations) {
        iterations = i;
        return *this;
    }
 
    ClusterSnnGraphLeiden& set_modularity(bool m = Defaults::modularity) {
        modularity = m;
        return *this;
    }
 
public:
    struct Results {
        int status = 0;
        
        std::vector<int> membership;
 
        double quality = 0;
    };
 
    Results run(const BuildSnnGraph::Results& store) const {
        return run(store.to_igraph(), store.weights.data());
    }
 
    Results run(const igraph::Graph& graph, const igraph_real_t* weights) const {
        igraph::IntegerVector membership_holder;
        auto& membership = membership_holder.vector;
        igraph_integer_t nb_clusters;
        igraph_real_t quality;
 
        igraph::RNGScope rngs(seed);
        Results output;
 
        // No need to free this, as it's just a view.
        igraph_vector_t weight_view;
        size_t nedges = igraph_ecount(graph.get_graph());
        igraph_vector_view(&weight_view, weights, nedges);
 
        if (!modularity) {
            output.status = igraph_community_leiden(graph.get_graph(), &weight_view, NULL, resolution, beta, false, iterations, &membership, &nb_clusters, &quality);
        } else {
            // More-or-less translated from igraph::cluster_leiden in the R package,
            // but with the iterations moved into igraph_community_leiden itself.
            igraph::RealVector strength_holder(igraph_vcount(graph.get_graph()));
            auto& strength = strength_holder.vector;
            igraph_strength(graph.get_graph(), &strength, igraph_vss_all(), IGRAPH_ALL, 1, &weight_view);
 
            double total_weights = std::accumulate(weights, weights + nedges, 0.0);
            double mod_resolution = resolution / total_weights;
 
            output.status = igraph_community_leiden(graph.get_graph(), &weight_view, &strength, mod_resolution, beta, false, iterations, &membership, &nb_clusters, &quality);
        }
 
        if (!output.status) {
            size_t ncells = igraph_vcount(graph.get_graph());
            output.membership.resize(ncells);
            for (size_t i = 0; i < ncells; ++i) {
                output.membership[i] = VECTOR(membership)[i];
            }
            output.quality = quality;
        }
 
        return output;
    }
};
 
}
 
#endif